zbMATH — the first resource for mathematics

Characterization of graphs using domination polynomials. (English) Zbl 1207.05092
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 \({\mathcal D}\)-equivalent, written as \(G\sim H\), if \(D(G,x)= D(H,x)\). The \({\mathcal D}\)-equivalence class of \(G\) is \([G]= \{H: H\sim G\}\). A graph \(G\) is said to be \({\mathcal 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 \({\mathcal D}\)-equivalence classes of some certain graphs. It is shown that if \(n\equiv 0,2\pmod 3\), then \(C_n\) is \({\mathcal D}\)-unique, and if \(n\equiv 0\pmod 3\), then \([P_n]\) consists of exactly two graphs.

05C31 Graph polynomials
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: DOI arXiv
[1] S. Alikhani, Y.H. Peng, Introduction to domination polynomial of a graph, Ars Combin. (in press). · Zbl 1324.05138
[2] Alikhani, S.; Peng, Y.H., Dominating sets and domination polynomial of cycles, Glob. J. pure appl. math., 4, 2, 151-162, (2008)
[3] S. Alikhani, Y.H. Peng, Dominating sets and domination polynomials of paths, Int. J. Math. Math. Sci., 2009, Article ID 542040. · Zbl 1177.05081
[4] Frucht, R.; Harary, F., On the corona of two graphs, Aequationes math., 4, 322-324, (1970) · Zbl 0198.29302
[5] Haynes, T.W.; Hedetniemi, S.T.; Slater, P.J., Fundamentals of domination in graphs, (1998), Marcel Dekker New York · Zbl 0890.05002
[6] Payan, C.; Xuong, N.H., Domination-balanced graphs, J. graph theory, 6, 23-32, (1982) · Zbl 0489.05049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.