History

Please fill in your query. A complete syntax description you will find on the General Help page.
Characterization of graphs using domination polynomials. (English)
Eur. J. Comb. 31, No. 7, 1714-1724 (2010).
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\}$. 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.