Discontinuity, Nonlinearity, and Complexity
Domination Polynomials of Certain Hexagon Lattice Graphs
Discontinuity, Nonlinearity, and Complexity 10(4) (2021) 723731  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 $nbook$ 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.2020ZJ924, NSFC No.11701311, NSFGD No.2016A030310307.
References

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


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


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


[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, 273282.


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


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


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


[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] 
Alikhani, S. (2009), Dominating sets and domination polynomials of graphs [Ph.D. thesis], Universiti Putra Malaysia.


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


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