ABSTRACT
This chapter describes in matrix form many graph theoretic subset problems such as domination, packing, covering, and independence. Graph theoretic minimization (respectively, maximization) problems expressed as linear programming problems have dual maximization (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 α(G) + β(G) = |V(G)| and the domination/enclaveless theorem γ(G) + |Ψ(G) = |V(G)|. Also, the matrix formulations suggest “generalized” parameters for which vertices can be assigned values in some arbitrarily specified subset Y of the reals. A generalized theory is introduced.
