The difference between the domination number and the minus domination number of a cubic graph

✍ Scribed by Xiaofan Yang; Qibin Hou; Xiangsheng Huang; Hengnong Xuan

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 325 KB
• Volume: 16
• Category: Article
• ISSN: 0893-9659
• DOI: 10.1016/s0893-9659(03)90099-1

✦ Synopsis

The closed neighborhood of a vertex subset S of a graph G = (V,E), denoted as N[Sj, is defined ss the union of S and the set of all the vertices adjacent to some vertex of S. A dominating set of a graph G = (V, E) is defined as a set S of vertices such that N[q = V. The domination number of a graph G, denoted as y(G), is the minimum possible size of a dominating set of G. A minus dominating function on a graph G = (V, E) is a function 9 : V + {-l,O, I} such that g(N[v]) 2 1 for all vertices. The weight of a minus dominating function g is defined as s(V) = c vEV g(v). The minus domination number of a graph G, denoted ss r-(G), is the minimum possible weight of a minus dominating function on G. It is well known that r-(G) _< y(G). This paper is focused on the difference between 7(G) and y-(G) for cubic graphs. We first present a graph-theoretic description of r-(G). Based on this, we give a necessary and sufllcient condition for r(G) -7-(G) > k. Further, we present an infinite family of cubic graphs of order 18k + 16 and with -y(G) -y-(G) 2 k.