# Domination Polynomials ofk-Tree Related Graphs

Authors: Somayeh Jahari; Saeid Alikhani
Journal: International Journal of Combinatorics
 (2014)

---

## Abstract

LetG be a simple graph of order n. The domination polynomial of G is the polynomial DG,x=∑i=γ(G)nd(G,i)xi, where d(G, i) is the number of dominating sets of G of size i and γ(G) is the domination number of G. In this paper, we study the domination polynomials of several classes of k-tree related graphs. Also, we present families of these kinds of graphs, whose domination polynomials have no nonzero real roots.


---

## Body

## 1. Introduction

Throughout this paper, we will consider only simple graphs. LetG=(V,E) be a simple graph. For F⊆V(G) we use F for the subgraph induced by F. For any vertex v∈V(G), theopen neighborhood of v is the set N(v)={u∈VG∣{u,v}∈E(G)} and theclosed neighborhood of v is the set N[v]=N(v)∪{v}. For a set S⊆V(G), the open neighborhood of S is N(S)=⋃v∈S‍N(v) and the closed neighborhood of S is N[S]=N(S)∪S. For every vertex v∈V(G), thedegree of v is the number of edges incident with v and is denoted by dG(v)=|N(v)|. Let di,1≤i≤n, be the degrees of the vertices vi of a graph in any order. The sequence {di}1n is called thedegree sequence of the graph. Aclique in a graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. We use Kn, Pn, Cn, and S1,n-1 for a clique, a path, a cycle, and a star, all of order n, respectively.A setS⊆V(G) is adominating set if N[S]=V or, equivalently, every vertex in V(G)∖S is adjacent to at least one vertex in S. Thedomination numberγ(G) is the minimum cardinality of a dominating set in G. A dominating set with cardinality γ(G) is called a γ-set. For a detailed treatment of these parameters, the reader is referred to [1]. Let D(G,i) be the family of dominating sets of a graph G with cardinality i and let d(G,i)=|D(G,i)|. Thedomination polynomialD(G,x) of G is defined as D(G,x)=∑i=γ(G)|V(G)|‍d(G,i)xi, where γ(G) is the domination number of G (see [2, 3]). Thus, D(G,x) is the generating polynomial for the number of dominating sets of G of any cardinality. A root of D(G,x) is called adomination root of G.In [4], it is shown that computing the domination polynomial D(G,x) of a graph G is NP-hard and some examples for graphs for which D(G,x) can be computed efficiently are given. The vertex contraction G/u of a graph G by a vertex u is the operation under which all vertices in N(u) are pairwise joined to each other and then u is deleted (see [5]). The following theorem is useful for finding the recurrence relations for the domination polynomials of arbitrary graphs.Theorem 1 (see [4, 6]).
LetG be a graph. For any vertex u in G, one has
(1)DG,x=xDGu,x+D(G-u,x)+xD(G-N[u],x)-(1+x)pu(G,x),
where pu(G,x) is the polynomial counting the dominating sets of G-u which do not contain any vertex of N(u) in G.Using Theorem1 we are able to obtain an easier formula for a graph with at least one vertex of degree 1. Since every tree has at least two vertices of degree 1, we can use the following recurrence to obtain the domination polynomials of trees.Corollary 2 (see [4]).
LetG=(V,E) be a graph, let v be a vertex of degree 1 in G, and let u be its neighbor. Then,
(2)D(G,x)=xDGu,x+DG-u-v,x+DG-Nu,x.IfG1 and G2 are disjoint graphs of orders n1 and n2, respectively, then D(G1∪G2,x)=D(G1,x)D(G2,x) and
(3)DG1+G2,x=(1+xn1-1)(1+xn2-1)+D(G1,x)+D(G2,x),
where G1+G2 is the join of G1 and G2, formed from G1∪G2 by adding in all edges between a vertex of G1 and a vertex of G2 (see [2]).The domination polynomials of trees, aside from path graph, have not been studied and there is no study for coefficients ofD(T,x) for trees T with n vertices. In this paper, k-trees, a generalization of trees, are considered. We study, similar to [7], k-tree related graphs and study their domination polynomials. An interesting study of the roots of domination polynomials is done in [8, 9]. Classification of the roots of domination polynomials is difficult to do, as well as finding graphs with no nonzero real roots. In this paper, we present k-tree related families which have this prementioned property.In Section2, we study the domination polynomials for some k-tree related graphs. In Section 3, we present some families of these kinds of graphs whose domination polynomials have no nonzero real roots.


## 2. Domination Polynomials ofk-Tree Related Graphs

In this section, we study the domination polynomials for somek-tree related graphs. The class of k-trees is a very important subclass of triangulated graphs. Harary and Palmer [10] first introduced 2-trees in 1968. Beineke and Pippert [11] gave the definition of a k-tree in 1969. In the literature on k-trees, there are interesting applications to the study of computational complexity.Definition 3.
For a positive integerk, a k-tree, denoted by Tnk, is defined recursively as follows. The smallest k-tree is the k-clique Kk. If G is a k-tree with n≥k vertices and a new vertex v of degree k is added and joined to the vertices of a k-clique in G, then the larger graph is a k-tree with n+1 vertices.Anindependent set in a graph G is a set of pairwise nonadjacent vertices.Definition 4.
LetKk be a k-clique and let S be an independent set of n-k vertices. A (k,n)-star, denoted by Sk,n-k, is defined as Sk,n-k=Kk+S.Definition 5.
A(k,n)-path, denoted by Pnk, begins with k-clique on {v1,v2,…,vk}. For i=k+1 to n, let vertex vi be adjacent to vertices {vi-1,vi-2,…,vi-k} only (see Figure 1).Figure 1
The 3-star and 3-path on 7 vertices, respectively.A helpful characteristic of the(k,n)-path Pnk is that we may order the vertices v1,v2,…,vn such that Pnk∖{v1,…,vi} is a k-path on n-i vertices for 1≤i≤n-k-1; such a vertex ordering is referred to as a presentation.Definition 6.
A(k,n)-cycle, denoted by Cnk, consists of a (k,n)-path on {v1,v2,…,vn} defined as above and an edge joining v1 to vn, where n≥k+2.Definition 7.
IfG is a (k,n)-cycle of order n and v is a vertex not in G, then G+v is called a (k,n)-wheel and is denoted by Wnk.Notice thatPn1, Cn1, Wn1, and S1,n-1 are just the standard path, cycle, wheel, and star, respectively. It follows easily from the domination polynomial of join of two graphs that, for the star graph S1,n-1, we have D(S1,n-1,x)=x(1+x)n-1+xn-1. The following are recurrences for the domination polynomials of paths and cycles [12].Theorem 8.
For the natural numbern≥3, (i)
D(Pn+1,x)=x(D(Pn,x)+D(Pn-1,x)+D(Pn-2,x)), where D(P1,x)=x, D(P2,x)=x2+2x, and D(P3,x)=x3+3x2+x;(ii)
D(Cn+1,x)=x(D(Cn,x)+D(Cn-1,x)+D(Cn-2,x)), where D(C1,x)=x, D(C2,x)=x2+2x, and D(C3,x)=x3+3x2+3x.Note that both(k,n)-cycles and (k,n)-wheels are not k-trees. But they are closely related to k-trees. We begin with a simple lemma which was proven in [7] as Proposition 2.Lemma 9.
For anyk-tree Tnk, |E(Tnk)|=kn-(1/2)k(k+1)=(2nk-k2-k)/2.Theindependence number is the size of a maximum independent set in a graph and is denoted by α(G). The following lemma gives independence numbers for k-tree related graphs.Lemma 10 (see [7]).
For each natural numberk≤n, one has (i)
α(Pnk)=(n+k)/(k+1),(ii)
αCnk=(n+k-1)/(k+1),(iii)
α(Wnk)=α(Cnk),(iv)
α(Sk,n-k)=n-k.Now, we present the following domination numbers fork-tree related graphs.Theorem 11.
For each natural numberk≤n, one has (i)
γ(Pnk)=n/(2k+1),(ii)
γ(Cnk)=n/(2k+1),(iii)
γ(Wnk)=1,(iv)
γ(Sk,n-k)=1.Proof.
(i) Sincek≤n, by the definition of Pnk, the degree sequence in this graph is
(4)k,k+1,…,2k-1,2k,…,2k,2k-1,…,k+1,k;
we have γ(Pnk)=1 for n≤2k+1 and γ(Pnk)=2 for 2k+2≤n≤4k+2. Thus, (i) holds for k≤n≤4k+2. Now, assume n≥4k+3. We use induction on n. Since any γ-set of Pnk contains only one vertex of the {vn,vn-1,…,vn-k,…,vn-2k-1} and Pnk-{vn,vn-1,…,vn-k,…,vn-2k-1} is a k-path with n-2k-1 vertices, by induction, γ(Pnk)=1+γ(Pn-2k-1k)=1+(n-2k-1)/(2k+1)=n/(2k+1). Hence, (i) holds.
(ii) Sincek≤n, by the definition of Cnk, the degree sequence in this graph is
(5)k+1,k+1,k+2,…,2k-1,2k,…,h2k,2k-1,…,k+1,k+1;
we have γ(Cnk)=1 for n≤2k+1 and γ(Cnk)=2 for 2k+2≤n≤4k+2. Thus, (ii) holds for k≤n≤4k+2. Now, assume n≥4k+3 and use induction on n. Since any γ-set of Cnk contains only one vertex of the {vn,vn-1,…,vn-k,…,vn-2k-1} and Cnk-{vn,vn-1,…,vn-k,…,vn-2k-1} is a k-path with n-2k-1 vertices, by induction, γ(Cnk)=1+γ(Pn-2k-1k)=1+(n-2k-1)/(2k+1)=n/(2k+1). Hence, (ii) holds.
(iii) Since the(k,n)-wheel Wnk has a vertex v of degree n-1, (iii) holds.
(iv) Since thek-star graph Sk,n-k has k vertices of degree n-1, (iv) holds.The following theorem gives a recurrence formula for the domination polynomial of(k,n)-path graphs.Theorem 12.
Ifn≤k+1, then D(Pnk,x)=D(Kn,x). For every k+2≤n,
(6)DPnk,x=(1+x)D(Pn-1k,x)+xD(Pn-k-1k,x)-(1+x)pu(Pnk,x),
where
(7)pu(Pnk,x)=x1+xn-k-2;k+2≤n≤2k+2,x(1+xn-k-2-1+xn-2k-3);2k+3≤n≤2k+6,pu(Pnk,x);2k+7≤n.Proof.
Ifn≤k+1, then Pnk≅Kn. For every k+2≤n, we use Theorem 1 for the last vertex of Pnk and since (by the definition of Pnk) the first k+1 and the last k+1 vertices form two cliques, we have Pnk/u≅Pnk-u. It is clear that D(Pnk-N[u],x)=D(Pn-k-1k,x). Obviously, pu(Pnk,x) is the polynomial counting the dominating sets of Pn-k-1k and contains the vertex vn-k-1. However, finding this polynomial involves complex calculations. We therefor give this polynomial only for n≤2k+6. Therefore, we have the result.In general, finding the domination polynomial of a graph is a very difficult problem. In [4], Kotek et al. showed that there exist recurrence relations for the domination polynomial which allow for efficient schemes to compute the polynomial for some types of graphs. Consider the (k,n)-cycle graphs. If n≤k+2, then Cnk≅Kn. Consequently, in this case, D(Cnk,x)=D(Kn,x). Until now, for every k+3≤n, all attempts to find formulas for D(Cnk,x) have failed.The following theorem gives a formula for the domination polynomial of(k,n)-wheel graphs.Theorem 13.
For a(k,n)-wheel Wnk, one has
(8)D(Wnk,x)=x1+xn+D(Cnk,x).Proof.
SinceWnk=Cnk+K1, then
(9)DWnk,x=((1+x)-1)(1+xn-1)+x+D(Cnk,x)=x1+xn+D(Cnk,x).The following theorem gives a formula for the domination polynomial ofk-star graphs, which is derived from the fact that the k-star graph is the join of complete graph Kk and independent set S (empty graph On-k).Theorem 14.
For everyk∈N and n>k,
(10)D(Sk,n-k,x)=1+xn-k(1+xk-1)+xn-k.Proof.
LetSk,n-k be the k-star graph with vertex set V(Sk,n-k)={v1,v2,…,vk,vk+1,…,vn}. It suffices to show that every dominating set of size j=1,…,n is accounted for exactly once in the above statement. Clearly, every nonempty subset of {v1,v2,…,vk} is a dominating set of k-star graphs. These sets can be extended with any number of vertices {vk+1,…,vn}. Also, obviously, the set {vk+1,…,vn} is a dominating set of k-star graphs. It is easy to see that there is no other method to form a dominating set for k-star graphs. Therefore, we have the result.Remark 15.
It is easy to see that another approach for proving Theorem14 is using the formula for the domination polynomial of join of two graphs.
The value of a graph polynomial at a specific point can give sometimes a surprising information about the structure of the graph [3, 13]. The following simple results give the domination polynomial of k-tree related graphs at -1.Corollary 16.
For each natural numberk≤n, the following hold: (i)
D(Pnk,-1)=(-1)α(Pnk),(ii)
D(Wnk,-1)=D(Cnk,-1),(iii)
D(Sk,n-k,-1)=(-1)α(Sk,n-k).Proof.
(i) Using the domination polynomial of a(k,n)-path in Theorem 12, for k≤n≤k+1, yields D(Pnk,-1)=D(Kn,-1)=-1. For every k+2≤n, D(Pnk,-1)=-D(Pn-k-1k,-1). We use induction on n. Suppose that the statement is true for every k-path with n-k vertices; by induction and Lemma 10,
(11)DPnk,-1=-D(Pn-k-1k,-1)=--1α(Pn-k-1k)=--1(n-1)/(k+1)=-11+(n-1)/(k+1)=-1(n+k)/(k+1).
Hence, (i) holds.
(ii) Follows from Theorem13.
(iii) Follows from Theorem14 and Lemma 10.


## 3. Some Families of Graphs with No Nonzero Real Domination Roots

In [8], the authors asked the question: “Which graphs have no nonzero real domination roots?”In this section, we obtain more results related to this question. We need some preliminaries.For two graphsG=(V,E) and H=(W,F), the corona G∘H is the graph arising from the disjoint union of G with |V| copies of H, by adding edges between the ith vertex of G and all vertices of ith copy of H [14]. It is easy to see that the corona operation of two graphs does not have the commutative property.We need the following theorem which will be used to find the domination polynomial of the corona products of two graphs.Theorem 17 (see [4, 15]).
LetG=(V,E) and H=(W,F) be nonempty graphs of orders n and m, respectively. Then,
(12)D(G∘H,x)=x1+xm+DH,xn.Ak-star, Sk,n-k, has vertex set {v1,…,vn} where <{v1,v2,…,vk}>≅Kk and N(vi)={v1,…,vk} for k+1≤i≤n.Now, we will discuss the roots of the domination polynomial of thek-star graphs.Theorem 18.
(i)
For odd naturaln and even natural k, no nonzero real number is the domination root of Sk,n-k.
(ii)
For even naturaln and even natural k, there is at least one nonzero real domination root of Sk,n-k.Proof.
By Theorem14, for every n>k, D(Sk,n-k,x)=(1+x)n-k((1+x)k-1)+xn-k. If D(Sk,n-k,x)=0, then we have
(13)1+xk-1=-x1+xn-k.
Now we prove the two cases of this theorem. (i)
First, suppose thatx≥0. Obviously, equality (13) is true just for 0, since for nonzero real number the left side of equality is positive but the right side is negative. If -1<x<0, then the left side of equality is negative but the right side is positive. Now, suppose that x<-1. In this case, the left side is greater than -1 and the right side -(1/(1+1/x))n-k is less than -1, a contradiction. Therefore, in any cases, we have the result.(ii)
Letx≥0. Similar to Case (i), equality (13) is true only for 0, since for nonzero real number the left side of equality is positive but the right side is negative. Now, suppose that x<-1. In this case, the right side is less than -1 and the left side is greater than -1, a contradiction. It remains to consider -1<x<0. It is easy to see that lim⁡x→0-D(Sk,n-k,x)<0, and D(Sk,n-k,-1)=(-1)n-k>0. So D(Sk,n-k,x) has at least one real root in (-1,0).Remark. Using Maple, we have shown the domination roots of S4,n-4 for 5≤n≤44 in Figure 2.Figure 2
Domination roots of graphsS4,n-4 for 5≤n≤44.Here, we construct a sequence of graphs, of which the domination roots are the same as the domination roots of thek+1-star graphs.Theorem 19.
The domination roots of every graphH in the family
(14)G∘Sk,n-k,G∘Sk,n-k∘Sk,n-k,G∘Sk,n-k∘Sk,n-k∘Sk,n-k,…hG∘Sk,n-k∘Sk,n-k∘Sk,n-k,…
have the same behavior as the domination roots of k+1-star graphs.Proof.
By Theorem17, we can deduce that, for each arbitrary graph G,
(15)D(G∘Sk,n-k,x)=x1+xn+1+xn-k1+xk-1+xn-k|V(G)|=1+xn-k1+xk+1-1+xn-k|V(G)|=DSk+1,n-k,x|V(G)|.
Therefore, we have the result.



---

*Source: 390170-2014-11-11.xml*