آمار
| تعداد نشریات | 6 |
| تعداد شماره‌ها | 131 |
| تعداد مقالات | 1,631 |
| تعداد مشاهده مقاله | 1,879,788 |
| تعداد دریافت فایل اصل مقاله | 1,741,101 |
Domination Chains in Graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 9، دوره 12، شماره 1، خرداد 2027، صفحه 115-125 اصل مقاله (387.36 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2025.29853.2192 | ||
| نویسندگان | ||
| Mustapha Chellali* 1؛ Stephen T. Hedetniemi2؛ Nacéra Meddah1 | ||
| 1LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria | ||
| 2Professor Emeritus, School of Computing, Clemson University, Clemson, South Carolina 29634, USA | ||
| چکیده | ||
| 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. | ||
| کلیدواژه‌ها | ||
| hereditary property؛ superhereditary property؛ domination Chain | ||
| مراجع | ||
|
[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 | ||
|
آمار تعداد مشاهده مقاله: 418 تعداد دریافت فایل اصل مقاله: 452 |
||