RUS  ENG
Полная версия
ЖУРНАЛЫ // Algebra and Discrete Mathematics // Архив

Algebra Discrete Math., 2019, том 28, выпуск 2, страницы 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

Аннотация: 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.

Ключевые слова: domination polynomial, $\mathcal{D}$-equivalence class, clique cover, friendship graphs.

MSC: 05C60, 05C69

Поступила в редакцию: 02.02.2017
Исправленный вариант: 11.08.2017

Язык публикации: английский



© МИАН, 2024