Domination Polynomials of Certain Hexagon Lattice Graphs

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.