Domination polynomial of clique cover product of graphs

preprint2016arXivOpen access

Abstract

Let GG be a simple graph of order nn. The domination polynomial of GG is the polynomial D(G,x)=∑i=1nd(G,i)xiD(G, x)=\sum_{i=1}^n d(G,i) x^i, where d(G,i)d(G,i) is the number of dominating sets of GG of size ii. For two graphs GG and HH, let C={C1,C2,⋯ ,Ck}\mathcal{C} = \{C_1,C_2, \cdots, C_k\} be a clique cover of GG and U⊆V(H)U\subseteq V(H). We consider clique cover product which denoted by GC⋆HUG^\mathcal{C} \star H^U and obtained from GG as follows: for each clique Ci∈CC_i \in \mathcal{C}, add a copy of the graph HH and join every vertex of CiC_i to every vertex of UU. We prove that the domination polynomial of clique cover product GC⋆HV(H)G^\mathcal{C} \star H^{V(H)} or simply GC⋆HG^\mathcal{C} \star H is D(GC⋆H,x)=∏i=1k[((1+x)ni−1)(1+x)∣V(H)∣+D(H,x)], D(G^\mathcal{C} \star H,x)=\prod_{i=1}^k\Big [\big((1+x)^{n_i}-1\big)(1+x)^{|V(H)|}+D(H,x)\Big], where each clique Ci∈CC_i \in \mathcal{C} has nin_i vertices. As results, we study the D\mathcal{D}-equivalence classes of some families of graphs. Also we completely describe the D\mathcal{D}-equivalence classes of friendship graphs constructed by coalescence nn copies of the cycle graph of length three with a common vertex.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.