LP-duality, LP-complimentarity, and Generality of Graphical Parameters

Dr. Peter J. Slater

Department of Mathematical Sciences
University of Alabama in Huntsville

February 16, 1996

Abstract

The global objective of some work over the last several years has been the application of linear programming and linear algebraic techniques and results to graph theory. In this talk the matrix/optimization forms for many graph theoretic subset problems such as domination, packing, covering, and independence will be presented.

Graph theoretic minimization (respectively, maximization) problems expressed as linear programming problems had dual maximaization (respectively, minimization) problems. Many of them also have interesting "complementary" problems, as described herein. As is the case for duality, complementarity involves one minimization and one maximization problem. The complementation theorem applied to specific pairs of complementary problems produces results including Gallai's covering/independence theorem

and the domination/enclaveless theorem

Also, the matrix formulations suggest "generalized" parameters for which vertices can be assigned values in some arbitarily specified subset Y of the reals. A generalized theory is introduced.