---

Discontinuity, Nonlinearity, and Complexity 10(4) (2021) 723--731 | DOI:10.5890/DNC.2021.12.011

Caibing Chang, Haizhen Ren, Zijian Deng, Bo Deng

School of Mathematics and Statistics, Qinghai Normal University, Xining, Qinghai 810008, China Academy of Plateau, Science and Sustainability, Xining, Qinghai 810008, China

Download Full Text PDF

 

Abstract

Let $G$ be a simple graph with order $n$. The domination polynomial of graph $G$ is defined by $D(G,x)=\sum_{i=|\gamma(G)|}^{n}d(G,i)x^{i}$, where $d(G,i)$ is the number of dominating sets of $G$ of size $i$ and $\gamma(G)$ is the domination number of $G$. Calculating the domination polynomial of $G$ is difficult in general, as determining whether $\gamma(G)\leq k$ is known to be $NP$-complete. This has led to an emphasis on studying this problem in particular classes of graphs. In this paper, we consider the following two kinds of graphs. One is the benzene graph $F_{6,n}$ which constructed by selecting one vertex in each of $n$ benzenes$(i.e \ C_{6})$ and identifying them. The other is the $n-book$ hexagon lattice graph $B_{n,6}$ which identifying $n$-copies of the $C_{6}$ with three common edges. Their closed form expressions for domination polynomial are all given.

Acknowledgments

Supported by NSFQH No.2020-ZJ-924, NSFC No.11701311, NSFGD No.2016A030310307.

References

1. [1]	Haynes, T.W., Hedetniemi, S.T., and Slater, P.J. (1998), Fundamentals of Domination in Graphs, Marcel Dekker, NewYork.

2. [2]	Alikhani, S. and Peng, Y.H. (2010), Dominating sets and domination polynomials of certain graphs. II, Opuscula Mathematica, 30(1), 37-51.

3. [3]	Akbari, S., Alikhani, S., and Peng, Y.H. (2010), Characterization of graphs using domination polynomial, Europ. J. Combin., 31, 1714-1724.

4. [4]	Brown, J.I., Hickman, C.A., and Nowakowski, R.J. (2004), On the location of roots of independence polynomials, Journal of Algebraic Combinatorics, 19, 273-282.

5. [5]	Brown, J.I., Dilcher, K., and Nowakowski, R.J. (2000), Roots of independence polynomials of well covered graphs, Journal of Algebraic Combinatorics, 11, 197-210.

6. [6]	Alikhani, S., Brown, J.I., and Jahari, S. (2016), On the domination polynomials of friendship graphs, J. Filomat, 30(1), 169-178.

7. [7]	Alikhani, S. (2013), On the domination polynomials of non $P_{4}$-free graphs, Iran. J. Math. Sci.Informatics, 8(2), 49-55.

8. [8]	Kotek, T., Preen, J., Simon, F., Tittmann, P. and Trinks, M. (2012), Recurrence relations and splitting formulas for the domination polynomial, Elec. J. Combin., 19(3).

9. [9]	Alikhani, S. (2009), Dominating sets and domination polynomials of graphs [Ph.D. thesis], Universiti Putra Malaysia.

10. [10]	Jahari, S. and Alikhani, S. (2015), Domination polynomial of generalized friendship and generalized book graphs[J], mathematics, 10(3).

11. [11]	Frucht, R. and Harary, F. (1970), On the corona of two graphs, Aequationes Mathematicae, 4, 322-325.