More on the Enumeration of Some Kind of Dominating Sets in Cactus Chains

Document Type : Original Scientific Paper

Authors

Department of Mathematical Sciences, Yazd University, Yazd, Iran

10.22052/mir.2022.246437.1352

Abstract

A non-empty set SV is a dominating set, if every vertex not in S is adjacent to at least one vertex in S, and S is a total dominating set, if every vertex of V is adjacent to some vertices of S. We enumerate dominating sets, non-split dominating sets and total dominating sets in several classes of cactus chains.

Keywords


 [1] S. Akbari, S. Alikhani and Y. H. Peng, Characterization of graphs using domination polynomial of a graph, European J. Combin. 31 (7) (2010) 1714-1724.
 [2] S. Alikhani, M. H. Akhbari, R. Hasni and C. Eslahchi, On the number of outer connected dominating sets of graphs, Utilitas Math. 91 (2013) 99-107.
[3] S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph,
Ars Combin. 114 (2014) 257 - 266.
[4] S. Alikhani and Y. H. Peng, Domination polynomials of cubic graphs of order
10, Turkish J. Math. 35 (3) (2011) 355 - 366.
[5] B. M. Anthony and M. E. Picollelli, Complete
r-partite graphs determined by their domination polynomial, Graphs Combin. 31 (6) (2015) 1993 - 2002.
[6] I. Averbouch, B. Godlin and J. A. Makowsky, An extension of the bivariate chromatic polynomial,
European J. Combin. 31 (1) (2010) 1 - 17.
[7] K. Borissevich and T. Doslić, Counting dominating sets in cactus chains,
Filomat 29 (8) (2015) 1847 - 1855.
[8] M. Chellali, Bounds on the
2-domination number in cactus graphs, Opuscula Math. 26 (1) (2006) 5 - 12.
[9] M. Dod, Graph products of the trivariate total domination polynomial and related polynomials,
Discrete Appl. Math. 209 (2016) 92 - 101.
[10] M. Dod, The independent domination polynomial, arXiv:1602.08250, (2016).
[11] K. Dohmen and P. Tittmann, Domination reliability,
Elect. J. Combin. 19 (1) (2012) 15.
[12] T. Doslić and F. Maloy, Chain hexagonal cacti: Matchings and independent sets,
Discrete Math. 310 (1) (2010) 1676 - 1690.
[13] F. Harary and B. Uhlenbeck, On the number of Husimi trees, I,
Proc. Nat. Aca. Sci. USA 39 (4) (1953) 315 - 322.
[14] T. W. Haynes, S. T. Hedetniemi and P. J. Slater,
Fundamentals of Domination in Graphs, Marcel Dekker Inc., NewYork, 1998.
[15] H. Hosoya and K. Balasubramanian, Exact dimer statistics and characteristic polynomials of cacti lattices,
Theor. Chim. Acta 76 (1989) 315 - 329.
[16] K. Husimi, Note on Mayers theory of cluster integrals,
J. Chemical Phys. 18 (1950) 682 - 684.
[17] T. Kotek, J. Preen, F. Simon, P. Tittmann and M. Trinks, Recurrence relations and splitting formulas for the domination polynomial,
Electron. J. Combin. 19 (3) (2012) 47.
 [18] S. Kijima, Y. Okamoto and T. Uno, Dominating set counting in graph classes, In: B. Fu, DZ. Du, (eds) Computing and combinatorics, 13–24, Lecture Notes in Comput. Sci., 6842, Springer, Heidelberg, 2011.
[19] V. R. Kulli and B. Janakiram, The nonsplit domination number of a graph,
Indian J. Pure Appl. Math. 31 (4) (2000) 545 - 550.
[20] R. J. Riddell,
Contributions to the Theory of Condensation, Ph.D. Thesis, Univ. of Michigan, Ann Arbor, 1951.
[21] B. Zmazek and J. Žerovnik, The obnoxious center problem on weighted cactus graphs,
Discrete Appl. Math. 136 (2004) 377 - 386.
[22] B. Zmazek and J. Žerovnik, Computing the weighted Wiener and Szeged number on weighted cactus graphs in linear time,
Croatica Chem. Acta 76 (2) (2003) 137 - 143.