کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419241 | 683758 | 2016 | 6 صفحه PDF | دانلود رایگان |
Let GG be a graph of order nn. A dominating set of GG is a subset of vertices of GG, say SS, such that every vertex in V(G)∖SV(G)∖S is adjacent to at least one vertex of SS. The domination polynomial of GG is the polynomial D(G,x)=∑i=1nd(G,i)xi, where d(G,i)d(G,i) is the number of dominating sets of GG of size ii. A root of D(G,x)D(G,x) is called a domination root of GG. Let δ=δ(G)δ=δ(G) be the minimum degree of vertices of GG. We prove that all roots of D(G,x)D(G,x) lies in the set {z:|z+1|≤2n−1δ+1}. We show that D(G,x)D(G,x) has at least δ−1δ−1 non-real roots. In particular, we prove that if all roots of D(G,x)D(G,x) are real, then δ=1δ=1. We construct an infinite family of graphs such that all roots of their polynomials are real. Motivated by a conjecture (Akbari, et al. 2010) which states that every integer root of D(G,x)D(G,x) is −2−2 or 0, we prove that if δ≥2n3−1, then every integer root of D(G,x)D(G,x) is −2−2 or 0. Also we prove that the conjecture is valid for trees and unicyclic graphs. Finally we characterize all graphs that their domination roots are integer.
Journal: Discrete Applied Mathematics - Volume 205, 31 May 2016, Pages 126–131