Domination Chains in Graphs

Articles in Press

Document Type : Original paper

Authors

1 LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria

2 Professor Emeritus, School of Computing, Clemson University, Clemson, South Carolina 29634, USA

Abstract

In the study of domination in graphs the following Domination Chain of inequalities is well known and well studied: ir(G)≤gamma(G)≤i(G)≤alpha(G)≤Gamma(G)≤(G)≤IR(G), where ir(G) and IR(G) denote the irredundance number and upper irredundance number, gamma(G) and Gamma(G) denote the domination number and upper domination number, and i(G) and alpha(G) denote the independent domination number and vertex independence number of a graph G. The Domination Chain is a consequence of the facts that (i) every maximal independent set is a minimal dominating set and every minimal dominating set is a maximal irredundant set and (ii) the property of being an independent set is hereditary (every subset of an independent set is also an independent set), the property of being a dominating set is superhereditary (every superset of a dominating set is also a dominating set), and the property of being an irredundant set is hereditary. In this paper we consider several other hereditary properties and superhereditary properties which give rise to similar domination chains.

Keywords

Main Subjects

References

[1] M. Chellali and O. Favaron, On k-star-forming sets in graphs, J. Combin. Math. Combin. Comput. 68 (2009), 205–214.
[2] E.J. Cockayne, P.J.P. Grobler, Hedetniemi, and A.A. McRae, What makes an irredundant set maximal?, J. Combin. Math. Combin. Comput. 25 (1997), 213–224.
[3] E.J. Cockayne, J.H. Hattingh, S.M. Hedetniemi, S.T. Hedetniemi, and A.A. McRae, Using maximality and minimality conditions to construct inequality  chains, Discrete Math. 176 (1997), no. 1-3, 43–61. https://doi.org/10.1016/S0012-365X(96)00356-1
[4] E.J. Cockayne, S.T. Hedetniemi, and D.J. Miller, Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull. 21 (1978), no. 4, 461–468.  https://doi.org/10.4153/CMB-1978-079-5
[5] A.M. Farley and A. Proskurowski, Computing the maximum order of an open irredundant set in a tree, Congr. Numer. 41 (1984), 219–228.
[6] A.M. Farley and N. Schacham, Senders in broadcast networks: open irredundancy in graphs, Congr. Numer. 38 (1983), 47–57.
[7] O. Favaron, A note on the open irredundance number in a graph, Congr. Numer. 66 (1988), 316–318.
[8] J. F. Fink and M. S. Jacobson, n-domination in graphs, Graph Theory with Applications to Algorithms and Computer Science, John Wiley & Sons, Inc.,  USA, 1985, p. 283–300.
[9] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, CRC press, 1998.
[10] S.M. Hedetniemi, S.T. Hedetniemi, and D.P. Jacobs, Total irredundance in graphs: theory and algorithms, Ars Combin. 35 (1993), 271–284.
[11] S.T. Hedetniemi, A.A. McRae, and R. Mohan, The private neighbor concept, Structures of Domination in Graphs (S.T. Haynes, T.W.and Hedetniemi and M.A. Henning, eds.), Springer International Publishing, Cham, 2021, pp. 183–218.
[12] M.A Henning, Distance domination in graphs, Domination in Graphs (S.T. Haynes, T.W.and Hedetniemi and P.J. Slater, eds.), Routledge, 1998, pp. 321–350.
[13] M.A. Henning, Distance domination in graphs, Topics in Domination in Graphs (S.T. Haynes, T.W.and Hedetniemi and M.A. Henning, eds.), Springer International Publishing, Cham, 2020, pp. 205–250.
[14] C.M. Mynhardt and A. Roux, Irredundance, Structures of Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer International  Publishing, Cham, 2021, pp. 135–181. 
[15] P.J. Slater, r-domination in graphs, J. ACM 23 (1976), no. 3, 446–450. https://doi.org/10.1145/321958.321964
[16] P.J. Slater, Enclaveless sets and MK-systems, J. Research National Bureau of Standards 82 (1977), no. 3, 197–202. https://doi.org/10.6028/jres.082.019
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 22 March 2025

Files

Share

How to cite

Statistics