Loading...

Characterization of graphs using domination polynomials

Akbari, S ; Sharif University of Technology | 2010

112 Viewed
  1. Type of Document: Article
  2. DOI: 10.1016/j.ejc.2010.03.007
  3. Publisher: 2010
  4. Abstract:
  5. Let G be a simple graph of order n. The domination polynomial of G is the polynomial D(G,x)=σi=1 nd(G,i)xi, 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 D-equivalent, written as G~H, if D(G,x)=D(H,x). The D-equivalence class of G is [G]={H:H~G}. A graph G is said to be 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)). Also, we study the D-equivalence classes of some certain graphs. It is shown that if n≡0,2(mod3), then Cn is D-unique, and if n≡0(mod3), then [Pn] consists of exactly two graphs
  6. Keywords:
  8. Source: European Journal of Combinatorics ; Volume 31, Issue 7 , October , 2010 , Pages 1714-1724 ; 01956698 (ISSN)
  9. URL: http://www.sciencedirect.com/science/article/pii/S0195669810000442