RUS  ENG
Full version
JOURNALS // Algebra and Discrete Mathematics // Archive

Algebra Discrete Math., 2019 Volume 28, Issue 2, Pages 248–259 (Mi adm729)

RESEARCH ARTICLE

Domination polynomial of clique cover product of graphs

Somayeh Jahari, Saeid Alikhani

Department of Mathematics, Yazd University, 89195-741, Yazd, Iran

Abstract: Let $G$ be a simple graph of order $n$. We prove that the domination polynomial of the clique cover product $G^\mathcal{C} \star H^{V(H)}$ is
$$ 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 $C_i \in \mathcal{C}$ has $n_i$ vertices. As an application, we study the $\mathcal{D}$-equivalence classes of some families of graphs and, in particular, describe completely the $\mathcal{D}$-equivalence classes of friendship graphs constructed by coalescing $n$ copies of a cycle graph of length $3$ with a common vertex.

Keywords: domination polynomial, $\mathcal{D}$-equivalence class, clique cover, friendship graphs.

MSC: 05C60, 05C69

Received: 02.02.2017
Revised: 11.08.2017

Language: English



© Steklov Math. Inst. of RAS, 2024