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
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.
- Hits: 93