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

Abstract

A non-empty set S ⊆ V 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

References

 [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.
Mathematics Interdisciplinary Research
Volume 7, Issue 3
September 2022
Pages 217-237

Files

Share

How to cite

Statistics