UAH > Math > Colloquia > 2/28/2006
The fractional analogues of domination and closed neighborhood packing in a graph form an interesting pair of dual linear programs: min 1Ty subject to: Ny ≥ 1, y ≥ 0 and its linear dual: max 1Ty subject to: NTy ≤ 1, y ≥ 0, in that the feasible vectors for both linear programs have interpretations as functions from the vertices of the graph to the unit interval. The relationships between the solution sets of these dual problems are investigated. Another pair of dual linear programs, the fractional analogues of total domination and open packing in a graph, also both have interpretations as functions from the vertices to the unit interval. The relationships between the solution sets of these dual problems are also investigated. Two graphs G and H with adjacency matrices A and B respectively are fractionally isomorphic if there exists a doubly stochastic matrix S so that SA = BS. This fractional analogue of graph isomorphism plays an important role in both of the above investigations. Finally, we give several new integer programming formulations of existing graph parameters as well as their linear programming relaxations and discover new fractional isomorphism invariants in the process.