Minimum Fractional Dominating Functions and Maximum Fractional Packing Functions

Dr. Robert Rubalcaba

Department of Mathematics and Statistics
Auburn University

April 22, 2005
202 Madison Hall
3:00 PM (Coffee and Cookies at 2:30)

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. The fractional analogue of graph isomorphism and the theory of efficient domination both play an important role in the investigation.