Institutional Repository

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

Show simple item record Cockayne E.J. en Mynhardt C.M. en 2012-11-01T16:31:40Z 2012-11-01T16:31:40Z 1997 en
dc.identifier.citation Utilitas Mathematica en
dc.identifier.citation 51 en
dc.identifier.issn 3153681 en
dc.description.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. en
dc.language.iso en en
dc.title Minimality and convexity of dominating and related functions in graphs: A unifying theory en
dc.type Article en

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search UnisaIR


My Account