Lower Bounds on the Distance Domination Number of a Graph

Randy Ryan Davila, Caleb Fast, Michael Henning, Franklin Kenter


For an integer $k \ge 1$, a (distance) $k$-dominating set of a connected graph $G$ is a set $S$ of vertices of $G$ such that every vertex of $V(G) \setminus S$ is at distance at most~$k$ from some vertex of $S$. The $k$-domination number, $\gamma_k(G)$, of $G$ is the minimum cardinality of a $k$-dominating set of $G$. In this paper, we establish lower bounds on the $k$-domination number of a graph in terms of its diameter, radius, and girth. We prove that for connected graphs $G$ and $H$, $\gamma_k(G \times H) \ge \gamma_k(G) + \gamma_k(H) -1$, where $G \times H$ denotes the direct product of $G$ and $H$.


Mathematics; Discrete Mathematics; Graph Theory; Domination Number

Full Text:



E. DeLaVina, Written on the Wall II, Web

address: http://cms.dt.uh.edu/faculty/delavinae/research/wowII

J. Cyman, M. Lemanska and J. Raczek, Lower bound on the distance $k$-domination number of a tree. Math. Slovaca 56(2) (2006), 235-243.

E. E. DeLaVi~{n}a, R. Pepper, B. Waller, Lower bounds for the domination number. Discuss. Math. Graph Theory 30(3) (2010), 475-487

P. Fraisse, A note on distance dominating cycles. Discrete Math. 71 (1988), 89--92.

R. Hammack, W. Imrich, and S. Klavvzar, Handbook of Product Graphs, Second Edition CRC Press (June 3, 2011) ISBN: 9781439813041.

A. Hansberg, D. Meierling, and L. Volkmann, Distance domination and distance irredundance in graphs. Electronic J. Combin. 14 (2007), #R35.

T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York, 1998.

T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (eds), Domination in Graphs: Advanced Topics, Marcel Dekker, Inc. New York, 1998.

M. A. Henning, Distance domination in graphs. Domination in Graphs: Advanced Topics, T.W. Haynes, S.T. Hedetniemi, and P.J. Slater (eds), Marcel Dekker, Inc. New York, 1998, 335--365.

M. A. Henning and N. Lichiardopol, Distance domination in graphs with given minimum and maximum degree, manuscript.

M. A. Henning, O. R. Oellermann, and H. C. Swart, Bounds on distance domination parameters. J. Combin. Comput. Inf. Sys. Sciences textbf{16} (1991), 11--18.

M. A. Henning and A. Yeo, Total domination in graphs (Springer Monographs in Mathematics). ISBN-13: 978-1461465249 (2013).

D. Lichtenstein, Planar satisfiability and its uses. SIAM J. Comput. textbf{11} (1982), 329-343.

D. Meierling and L. Volkmann, A lower bound for the distance $k$-domination number of trees. Result. Math. 47 (2005), 335-339.

A. Meir and J. W. Moon, Relations between packing and covering number of a tree. Pacific J. Math. 61 (1975), 225-233.

G. Mekis, Lower bounds for the domination number and the total domination number of direct product graphs. Discrete Math. 310 (2010), 3310--3317.

P. J. Slater, R-domination in graphs. J. Association Computer Machinery 23(3) (1976), 446--450.

F. Tian and J. M. Xu, A note on distance domination numbers of graphs. Australasian J. Combin. 43 (2009), 181-190.

J. Topp and L. Volkmann, On packing and covering numbers of graphs. Discrete Math. 96 (1991), 229--238.

Contributions to Discrete Mathematics. ISSN: 1715-0868