Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 1207.05092
Akbari, Saieed; Alikhani, Saeid; Peng, Yee-Hock
Characterization of graphs using domination polynomials.
(English)
[J] Eur. J. Comb. 31, No. 7, 1714-1724 (2010). ISSN 0195-6698

Summary: Let $G$ be a simple graph of order $n$. The domination polynomial of $G$ is the polynomial $$D(G,x)=\sum^n_{i=1} d(G,i)^i,$$ where $d(G,i)$ is the number of dominating sets of $G$ of size $i$. A root of $D(G,x)$ is called a domination root of $G$. We denote the set of distinct domination roots by $Z(D(G,x))$. Two graphs $G$ and $H$ are said to be ${\Cal D}$-equivalent, written as $G\sim H$, if $D(G,x)= D(H,x)$. The ${\Cal D}$-equivalence class of $G$ is $[G]= \{H: H\sim G\}$. A graph $G$ is said to be ${\Cal D}$-unique if $[G]= \{G\}$.\par In this paper, we show that if a graph $G$ has two distinct domination roots, then $Z(D(G,x))= \{-2, 0\}$. Also, if $G$ is a graph with no pendant vertex and has three distinct domination roots, then $$Z(D(G,x))\subseteq \Biggl\{0,-2\pm\sqrt{2}i,{-3+ \sqrt{3}i\over 2}\Biggr\}.$$ Also, we study the ${\Cal D}$-equivalence classes of some certain graphs. It is shown that if $n\equiv 0,2\pmod 3$, then $C_n$ is ${\Cal D}$-unique, and if $n\equiv 0\pmod 3$, then $[P_n]$ consists of exactly two graphs.
MSC 2000:
*05C31
05C69 Dominating sets, independent sets, cliques

Highlights
Master Server