Fractional Domination, Fractional Packings, and Fractional Isomorphisms of Graphs

Abstract

The fractional analogues of domination and packing in a graph form an interesting pair of dual linear programs, in that the feasible vectors for both LPs 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. The fractional analogue of graph isomorphism plays a role in both investigations. Finally, various military strategies are discussed, as well as their fractional analogues.