Towards a theory of 〈r, s〉-domination in graphs
Abstract
This work is concerned with a facilities location problem in networks modelled by n-vertex undirected graphs G = (V,E), where V = {u 1,⋯,un}. Let r = (r1,⋯,r n) and s = (s1,⋯,sn) be n-tuples of nonnegative integers. Suppose that at most ri units of some commodity may be located at the vertex ui, while there must be at least s i units in the vicinity (i.e. in the closed neighbourhood) of u i. Consider the function f :V → N (the set of nonnegative integers) where f(ui) is the number of units placed at ui. If f satisfies the above requirements, then f is called an s-dominating r-function of G. In this paper we initiate the theory (called 〈r, s〉-domination) of such functions. Special cases include (basic) domination, k-tuple domination and {k}-domination. Extensions of the graph-theoretic concepts of independence, irredundance, packing and domatic numbers are also considered. The well-studied inequality chain for independence, domination and irredundance parameters is generalised. I dedicate this work to my great friend and colleague, Professor Stephen Hedetniemi, in the year of his retirement. A chance meeting at a conference almost 40 years ago led to a lifelong friendship, continuous collaboration in mathematics, sport and music, and to some of the most hilarious moments in my life. Thank you Hedet. for everything (including DIDSIG)!
