Minimality and convexity of dominating and related functions in graphs: A unifying theory

Abstract

A (total) dominating function of a graph is a feasible solution to the linear programming relaxation of the minimum (total) dominating set integer programme. Other functions (sometimes called fractional functions) on graphs such as covering, matching, packing, irredundant and independent functions are analogously defined from their corresponding sets of vertices or edges. The question of which convex combinations of extremal graph functions are themselves extremal, has been extensively studied for various specific functions and common properties have been observed in several of these emerging theories. In this paper we generalize and define functions on graphs, of which some of the above functions are special cases. The theory of minimality and convexity of functions is developed and is seen to unify portions of the corresponding theories for specific functions. In particular, we define and investigate universal minimal η-functions. We obtain necessary conditions and (slightly different) sufficient conditions for a minimal η-function to be universal. Under certain restrictions this leads to a characterization of universal minimal η-functions of a large class of graphs.