# Graphs Whose Certain Polynomials Have Few Distinct Roots

Authors: Saeid Alikhani
Journal: ISRN Discrete Mathematics
 (2013)

---

## Abstract

LetG=(V,E) be a simple graph. Graph polynomials are a well-developed area useful for analyzing properties of graphs. We consider domination polynomial, matching polynomial, and edge cover polynomial of G. Graphs which their polynomials have few roots can sometimes give  surprising information about the structure of the graph. This paper is primarily a survey of graphs whose domination polynomial, matching polynomial, and edge cover polynomial have few distinct roots. In addition, some new unpublished results and questions are concluded.


---

## Body

## 1. Introduction

LetG=(V,E) be a simple graph. Graph polynomials are a well-developed area useful for analyzing properties of graphs.We consider the domination polynomial, the matching polynomial (and the independence polynomial), and the edge cover polynomial of  graphG. For convenience, the definition of these polynomials will be given in the following sections.Thecorona of two graphs G1 and G2, as defined by Frucht and Harary in [1], is the graph G=G1∘G2 formed from one copy of G1 and |V(G1)| copies of G2, where the ith vertex of G1 is adjacent to every vertex in the ith copy of G2. The corona G∘K1, in particular, is the graph constructed from a copy of G, where for each vertex v∈V(G), a new vertex v′ and a pendant edge vv′ are added. The join of two graphs G1 and G2, denoted by G1∨G2 is a graph with vertex set V(G1)∪V(G2) and edge set E(G1)∪E(G2)∪{uv∣u∈V(G1) and v∈V(G2)}.The decycling number (or the feedback vertex number) of a graphG is the minimum number of vertices that need to be removed in order to eliminate all its cycles.The study of graphs whose polynomials have few roots can sometimes give surprising information about the structure of the graph. IfA is the adjacency matrix of G, then the eigenvalues of A, λ1≥λ2≥⋯≥λn are said to be the eigenvalues of the graph G. These are the roots of the characteristic polynomial ϕ(G,λ)=∏i=1n‍(λ-λi). For more details on the characteristic polynomials, see [2]. The characterization of graphs with few distinct roots of characteristic polynomials (i.e., graphs with few distinct eigenvalues) have been the subject of many researches. Graphs with three adjacency eigenvalues have been studied by Bridges and Mena [3] and Muzychuk and Klin [4]. Also van Dam studied graphs with three and four distinct eigenvalues [5–9]. Graphs with three distinct eigenvalues and index less than 8 were studied by Chuang and Omidi in [10].This paper is primarily a survey of graphs whose polynomial domination, matching polynomial, and edge cover polynomial have few distinct roots. In addition, some new unpublished results and questions are concluded. In Section2, we investigate graphs with few domination roots. In Section 3, we study graphs whose matching polynomials have few roots. Using these results we characterize line graphs whose independence polynomials have few roots. In Section 4, we characterize graphs with few edge cover roots. Finally in Section 5, we state conjectures and open problems.As usual, we use⌊x⌋, ⌈x⌉ for the largest integer less than or equal to x, and for the smallest integer greater than or equal to x, respectively.


## 2. Graphs with Few Domination Roots

LetG=(V,E) be a graph of order |V|=n. For any vertex v∈V, the open neighborhood of v is the set N(v)={u∈V∣uv∈E}, and the closed neighborhood of v is the set N[v]=N(v)∪{v}. For a set S⊆V, the open neighborhood of S is N(S)=⋃v∈S‍N(v), and the closed neighborhood of S is N[S]=N(S)∪S. A set S⊆V is a dominating set if N[S]=V, or equivalently, every vertex in V∖S is adjacent to at least one vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set in G. For a detailed treatment of this parameter, the reader is referred to [11]. Let 𝒟(G,i) be the family of dominating sets of a graph G with cardinality i, and let d(G,i)=|𝒟(G,i)|. The domination polynomialD(G,x) of G is defined as D(G,x)=∑i=0|V(G)|‍d(G,i)xi [12–14]. The path P4 on 4 vertices, for example, has one dominating set of cardinality 4, four dominating sets of cardinality 3, and four dominating sets of cardinality 2; its domination polynomial is D(P4,x)=x4+4x3+4x2.A root ofD(G,x) is called a domination root of G. In this section, the set of distinct roots of D(G,x) is denoted by Z(D(G,x)).A setS⊆V is called an independent set if no pair of vertices of S is adjacent. The independence number of graph G is the size of a maximum independent set of G and is denoted by α(G).The following theorem prove that we have real domination roots of arbitrarily large modulus.Theorem 1 (see [15]).
The domination polynomial of the star graph,D(K1,n,x), where n∈ℕ, has a real root in the interval (-2n,-ln(n)), for n sufficiently large.The domination roots ofK1,n for 1≤n≤60 was shown in Figure 1.Figure 1
Domination roots ofK1,n for 1≤n≤60.In [12, 16] we have characterized graphs with one, two and three distinct domination roots. Since 0 is a root of any domination polynomial of graph G, we have the following theorem.Theorem 2 (see [17]).
A graphG has one domination root if and only if G is a union of isolated vertices.It is interesting that all characterized graphs with two, three, and four distinct domination roots have special structures. As we will see, the structures of these graphs are the form of corona of two graphs. The following theorem characterizes graphs with two distinct domination roots.Theorem 3 (see [12]).
LetG be a connected graph with exactly two distinct domination roots. Then there exists natural number n such that D(G,x)=xn(x+2)n. Indeed G=H∘K1 for some graph H of order n. Moreover, for every graph H of order n, D(H∘K1,x)=xn(x+2)n.Theorem 4 (see [12]).
LetG be a connected graph of order n. Then, Z(D(G,x))={0,(-3±5)/2}, if and only if G=H∘K¯2, for some graph H. Indeed D(G,x)=xn/3(x2+3x+1)n/3.Theorem4 characterizes graphs with Z(D(G,x))={0,(-3±5)/2}. These graphs are of the form H∘K¯2, for some graph H (see Figure 2).Figure 2
Graph withD(G,x)=x⌈n/3⌉(x2+3x+1)⌈n/3⌉.For classifying all graphs with three distinct domination roots, we need to know that the value of the domination polynomial of every graph at-1 is nonzero (see [18] and Theorem 5).Theorem 5 (see [19]).
LetG be a graph. Then D(G,r) is odd for every odd integer r. In particular, D(G,-1) is odd.The following corollary is an immediate consequence of Theorem5.Corollary 6 (see [19]).
Every integer domination root of a graphG is even.The following theorem shows that roots of graphs with exactly three distinct domination roots cannot be any number.Theorem 7 (see [12]).
For every graphG with exactly three distinct domination roots
(1)Z(D(G,x))⊆{0,-3±52,-2±2i,-3±3i2}.Remark 8.
SinceZ(D(K3,x))={0,(-3±3i)/2}, Z(D(P3,x))={0,(-3±5)/2}, and Z(D(C4,x))={0,-2±2i}, for every number of set {0,(-3±5)/2,-2±2i,(-3±3i)/2}, there exist a graph whose domination polynomials have exactly three distinct roots. Since cycles are determined by their domination polynomials [20], so graphs with exactly three domination roots from {0,(-3±5)/2,-2±2i} are C4 and are graphs of the form H∘K¯2, for graph H.By Theorems2, 3 and, 7, we have the following corollary.Corollary 9 (see [16]).
For every graphG with at most three distinct domination roots
(2)Z(D(G,x))⊆{0,-2,-3±52,-2±2i,-3±3i2}.Now we will study graphs with exactly four distinct domination roots.LetGn be an arbitrary graph of order n. Let it denote the graph Gn∘K1 simply by Gn*. Here we consider the labeled Gn* as shown in Figure 3 (the graph in this figure is Pn* which is called centipede). We denote the graph obtained from Gn* by deleting the vertex labeled 2n as Gn*-{2n}.Figure 3
Labeled centipede,Pn*.The following theorem states a recursive formula for the domination polynomial ofGn*-{2n}.Theorem 10 (see [21]).
For everyn≥5,
(3)D(Gn*-{2n},x)=x[D(Gn-1*,x)+D(Gn-2*,x)]+x2D(Gn-2*,x).The following theorem gives the formula forD(Gn*-{2n},x).Theorem 11 (see [21]).
For everyn≥2, D(Gn*-{2n},x)=(x2+3x+1)xn-1(x+2)n-2.The following theorem characterizes graphs with four domination roots-2, 0, (-3±5)/2.Theorem 12 (see [21]).
LetG be a connected graph of order n. Then, Z(D(G,x))={-2,0,(-3±5)/2}, if and only if G=Gn/2*-{n}, for some graph Gn/2 of order n/2. Indeed
(4)D(G,x)=(x2+3x+1)x(n/2)-1(x+2)(n/2)-2.Since domination polynomial is monic polynomial with integer coefficients, its zeros are algebraic integers. This naturally raises the question: which algebraic integers can occur as zeros of domination polynomials? (see [22]). Using tables of domination polynomials (see [23]), we think that the number of algebraic integers which can be roots of graphs with exactly four distinct domination roots are about nine numbers, but we are not able to prove it. So complete characterization of graphs with exactly four distinct domination roots remains as an open problem. In other words, we have the following question.Question 1.
Which algebraic integers are domination roots of graphs with exactly four distinct domination roots?All real roots of the domination polynomial are necessarily negative, but it is not surprising that for some graphs there exists imaginary roots with positive real parts [24]. Surprisingly, in [15] it has shown that the domination roots are in fact dense in ℂ.Theorem 13 (see [15]).
The closure of the domination roots is the whole complex plane.


## 3. Graphs with Few Matching Roots

In this section, we study graphs whose matching polynomials have few roots. First, we state the definition of matching polynomial. LetG=(V,E) be a graph of order n and size m. An r-matching of G is a set of r edges of G where no two of them have common vertex. The maximum number of edges in the matching of a graph G is called the matching number of G and is denoted by α′(G). The matching polynomial is defined by
(5)μ(G,x)=∑k=0⌊n/2⌋‍(-1)km(G,k)xn-2k,
where m(G,k) is the number of k-matching of G, and m(G,0)=1. The roots of μ(G,x) are called the matching roots of G. As an example, the matching polynomial of path P5 is μ(P5,x)=(x-1)x(x+1)(x2-3). For more details of this polynomial refer to [25–27].Two following theorems are the first results on matching roots.Theorem 14 (see [28]).
The roots of matching polynomial of any graph are all real numbers.Theorem 15 (see [29]).
IfG has a Hamiltonian path, then all roots of its matching polynomial are simple (have multiplicity 1).We need the following definition to study graphs with few matching roots.Add a single vertexu to the graph rK1,k∪tK1 and join u to the other vertices by p+q edges so that the resulting graph is connected and u is adjacent with q centers of the stars (for K1,1 either of the vertices may be considered as a center). We denote the resulting graph by 𝒮(r,k,t;p,q) (see Figure 4). Clearly r+t≤p+q≤r(k+1)+t and 0≤q≤r (see [30]).Figure 4
A typical graph in the family𝒮(r,k,t;p,q): the central vertex has degree p and it is joined to q centers of the stars K1,k.For anyG∈𝒮(r,3,t;p,q), we add s copies of K3 to G and join them by l edges to the vertex u of G. Clearly s≤l≤3s. We denote the set of these graphs by ℋ(r,s,t;p,q,l).The following theorem gives the matching polynomial of graphG in the family 𝒮(r,k,t;p,q).Theorem 16 (see [30]).
For everyG∈𝒮(r,k,t;p,q),
(6)μ(G,x)=xr(k-1)+t-1(x2-k)r-1×(x4-(p+k)x2+(p-q)(k-1)+t).Theorem 17 (see [30]).
For everyG∈ℋ(r,s,t;p,q,l),
(7)μ(G,x)=x2r+s+t-1(x2-3)r+s-1×(x4-(p+l+3)x2+3t+2(p-t-q)+l).Similar to [30], we distinguish some special graphs in the families S and H which are important for our study.We denote the family𝒮(r,1,0;s,q) which consists of a single graph by S(r,s). Note that in this case q is determined by r and s; namely, q=s-r. Its matching polynomial is
(8)μ(S(r,s),x)=x(x2-s-1)(x2-1)r-1.
The family 𝒮(r,k,0;r,r) consists of a single graph which is denoted by T(r,k). Its matching polynomial is
(9)μ(T(r,k),x)=xr(k-1)+1(x2-r-k)(x2-k)r-1.
We also denote the unique graphs in 𝒮(1,k,t;l+t,0) and 𝒮(1,k,t;l+t+1,1) by K(k,t;l) and K′(k,t;l), respectively. Their matching polynomials are
(10)μ(K(k,t;l),x)=xk+t-2(x4-(k+t+l)x2+(l+t)(k-1)+t),μ(K′(k,t;l),x)=xk+t-2(x4-(k+t+l+1)x2+(l+t)(k-1)+t).
Moreover, we denote the unique graph in ℋ(0,1,t;t,0,l) by L(t,l) for l=1,2,3. We have μ(L(t,l),x)=xt(x4-(t+l+3)x2+3t+l). Typical graphs from the above families are shown in Figure 5.Figure 5
The graphsK(k,t;l), K′(k,t;l), L(t,l), T(r,k), and S(r,s), respectively.Theorem 18 (see [30]).
LetG be a connected graph, and let z(G) be the number of its distinct matching roots. (i)
Ifz(G)=2, then G≃K2.(ii)
Ifz(G)=3, then G is either a star or K3.(iii)
Ifz(G)=4, then G is a nonstar graph with 4 vertices.(iv)
Ifz(G)=5, then G is one of the graphs K(k,t;l), K′(k,t;l), L(t;l), T(r,k), and S(r,s), for some integers k, r, s, t, and l or a connected nonstar graph with 5 vertices.Using the previous theorem we would like to study graphs with few independence roots. First, we recall the definition of independence polynomial.An independent set of a graphG is a set of vertices where no two vertices are adjacent. The independence number is the size of a maximum independent set in the graph and is denoted by α(G). For a graph G, let ik denote the number of independent sets of cardinality k in G(k=0,1,…,α). The independence polynomial of G,
(11)I(G,x)=∑k=0α‍ikxk,
is the generating polynomial for the independent sequence (i0,i1,i2,…,iα). For further studies on independence polynomial and independence root refer to [31–33].The pathP4 on 4 vertices, for example, has one independent set of cardinality 0 (the empty set), four independent sets of cardinality 1, and three independent sets of cardinality 2; its independence polynomial is then I(P4,x)=1+4x+3x2.Here we recall the definition of line graph. Given a graphH=(V,E), the line graph of H, denoted by L(H), is a graph with vertex set E; two vertices of L(H) are adjacent if and only if the corresponding edges in H share at least one endpoint. We say that G is a line graph if there is a graph H for which G=L(H).Theorem 19 (see [34]).
For every graphG, μ(G,x)=xnI(L(G),-1/x2).The following corollary is an immediate consequence of Theorem19.Corollary 20.
Ifα≠0 is a matching root of G, then -1/α2 is an independence root of L(G).Now we are ready to state a theorem for graphs whose independence polynomials have few roots. The following theorem follows from Theorem19 and Corollary 20.Theorem 21.
LetG be a connected graph and z(L(G)) be the number of distinct independence nonzero roots of L(G). (i)
Ifz(L(G))=2, then L(G)≃K2.(ii)
Ifz(L(G))=3, then L(G) is either a star or K3.(iii)
Ifz(L(G))=4, then L(G) is a nonstar graph with 4 vertices.(iv)
Ifz(L(G))=5, then L(G) is one of the graphs and G is one of the graphs K(k,t;l), K′(k,t;l), L(t;l), T(r,k), and S(r,s), for some integers k, r, s, t, and l or a connected nonstar graph with 5 vertices.Here we bring the independence roots of families of paths and cycles. In the next section, we compare these roots with roots of edge cover polynomials of paths and cycles.Theorem 22 (see [31]).
(i) For any integern, I(Pn,x) has the following zeros,
(12)ps(n)=-12(1+cos(2sπ/(n+2))),s=1,2,…,⌊n+12⌋.
(ii) For any integern≥3, I(Cn,x) has the following zeros,
(13)cs(n)=-12(1+cos(((2s-1)π)/n)),s=1,2,…,⌊n2⌋.Corollary 23 (see [31]).
The independence roots of the family{Pn} and {Cn} are real and dense in (-∞,-1/4].In [35] the authors studied graphs whose independence roots are rational.Theorem 24 (see [35]).
LetG be a graph with rational polynomial I(G,x). If i(G,r-1)>i(G,r), for some r, 1≤r≤α(G), then G has an independence root in the interval (-1,-1/α(G)].The following theorem characterizes graphs with exactly one independence root.Theorem 25 (see [35]).
LetG be a graph of order n. Then I(G,x) has exactly one root if and only if G=rKs, where n=rs for some natural r, s.Theorem 26 (see [36]).
For any graphG, |I(G,-1)|≤2ν(G), where ν(G) is the decycling number of G.


## 4. Graphs with Few Edge-Cover Roots

In this section, we characterize graphs whose edge cover polynomials have one and two distinct roots. First, we state the definition of edge-cover polynomial of a graph.For every graphG with no isolated vertex, an edge covering of G is a set of edges of G such that every vertex is incident to at least one edge of the set. A minimum edge covering is an edge cover of the smallest possible size. The edge covering number of G is the size of a minimum edge cover of G and is denoted by ρ(G). The edge cover polynomial of G is the polynomial E(G,x)=∑i=1m‍e(G,i)xi, where e(G,i) is the number of edge covering sets of G of size i. Note that if graph G has isolated vertex then we put E(G,x)=0 and if V(G)=E(G)=∅, then E(G,x)=1. For more detail on this polynomial refer to [37, 38].As an example, the edge cover polynomial of pathP5 is E(P5,x)=2x3+x4. Also E(K1,n,x)=xn. As usual we use δ(G) to denote the minimum degree of graph G.The following theorem is a recursive formula for edge cover polynomial of a graph.Theorem 27 (see [37]).
LetG be a graph, u,v∈V(G) and uv be an edge of G. Then
(14)E(G,x)=(x+1)E(G∖uv,x)+x(E(G∖u,x)+E(G∖v,x)+E(G∖{u,v})).The following results are about edge cover polynomial of a graph.Lemma 28 (see [37]).
LetG be a graph of order n and size m with no isolated vertex. If the edge cover polynomial of G is E(G,x)=∑i=ρ(G)m‍e(G,i)xi, then the following hold:(i)
n≤2ρ(G).(ii)
Ifi0=min{i∣e(G,i)=(mi)}, then δ=m-i0+1.(iii)
IfG does not have connected component isomorphic to K2, then aδ(G)=(mm-δ)-e(G,m-δ).Theorem 29 (see [38]).
LetG be a graph. Then E(G,x) has at least δ(G)-2 nonreal roots (not necessary distinct). In particular, when δ(G)=3, E(G,x) has at least two distinct nonreal roots.Now, we will characterize graphs with few edge cover roots. Note that zero is one of the roots ofE(G,x) with multiplicity ρ(G). The next theorem characterizes all graph G whose edge cover polynomials have exactly one distinct root. Note that E(K1,n,x)=xn.Theorem 30 (see [38]).
LetG be a graph. Then E(G,x) has exactly one distinct root if and only if every connected component of G is star.We need the following definition to study graphs with two distinct edge cover roots.LetH be a graph of order n and size m. Suppose {v1,…,vn} is the vertex set of H. By H(r) we mean the graph obtained by joining ri≥1 pendant vertices to vertex vi, for i=1,…n such that ∑‍ri=r. If m is the size of H, then H(r) is a graph of order n+r and size m+r. The graph C4(9) shown in Figure 6.Figure 6
The graphC4(9).Theorem 31 (see [38]).
LetG be a graph. Then E(G,x)=xr(x+1)m, for some natural numbers r and m, if and only if there exists a graph H with size m such that G=H(r).The next theorem characterizes all graphsG for which E(G,x) has exactly two distinct roots.Theorem 32 (see [38]).
LetG be a connected graph whose edge cover polynomial has exactly two distinct roots. Then one of the following holds: (i)
G=H(r), for some connected graph H and natural number r.(ii)
G=K3.(iii)
δ(G)=1, E(G,x)=x(m+s)/2(x+2)(m-s)/2, where s is the number of pendant vertices of G.(iv)
δ(G)=2, E(G,x)=xm/2(x+2)m/2,  a2(G)=m/2, and G has cycle of length 3 or 5.By Theorems31 and 32 we have the following corollaries.Corollary 33 (see [37]).
LetG be a connected graph. If E(G,x) has exactly two distinct roots, then Z(E(G,x))={-1,0}, Z(E(G,x))={-2,0}, or Z(E(G,x))={-3,0}. Also δ(G)=1 or δ(G)=2.Corollary 34 (see [37]).
LetG be a connected graph. If Z(E(G,x))=Z(E(K3,x))={-3,0} if and only if G=K3.We have the following corollary.Corollary 35.
LetG be a graph with at most two distinct edge cover roots. Then Z(E(G,x))⊆{-3,-2,-1,0}.There are infinite graphsG with δ(G)=1 and Z(E(G,x))⊆{-2,-1,0}. To see some algorithms for the constructing of these kind of graphs refer to [37]. For the case δ(G)=2, we can see that if G is a graph with δ(G)=2 and Z(E(G,x))={-2,0}, then G has cycle with length 3 or 5 (see [37]). For this case there is the following conjecture.Conjecture 1 (see [37]).
There isn't any graphG with δ(G)=2 and Z(E(G,x))={-2,0}.It is proven that ifG is a graph without cycle of length 3 or 5 and δ(G)=2, then E(G,x) has at least three distinct roots (see [37]). Theorem 32 and previous conjecture implies that if δ(G)=2 and G≠K3, then E(G,x) has at least three distinct roots.The following theorem gives the roots of edge cover polynomial of paths and cycles.Theorem 36 (see [38]).
(i) For any integern, E(Pn,x) has the following nonzero roots:
(15)-2(1+cos2sπn-1),s=1,2,…,⌊n2⌋-1.
(ii) For any integern≥3, E(Cn,x) has the following zeros:
(16)cs(n)=-2(1+cos(2s+1)πn),s=0,1,…,⌊n2⌋-1.Also we have the following theorem for roots ofE(Pn,x) and E(Cn,x).Theorem 37 (see [38]).
The roots of the family{E(Pn,x)} and {E(Cn,x)} are real and dense in (-4,0].Remark 38.
It is interesting that the nonzeros roots ofI(Cn,x) are exactly the inverse of (nonzeros) roots of E(Cn,x).Note that in [38], it is proved that if every block of the graph G is K2 or a cycle, then all real roots of E(G,x) are in the interval (-4,0].Since for everyn, n is a root of the characteristic polynomial of K1,n, we can conclude that there is no constant bound for the roots of the characteristic polynomials and matching polynomials. Sokal in [39], proved that for every graph G, the absolute value of any root of the chromatic polynomial of G is at most 8Δ(G), where Δ(G) denotes the maximum degree of G. On the other hand, χ(G)-1 is clearly a root of the chromatic polynomial of G, where χ(G) denotes the chromatic number of G. Therefore, there is no constant bound for the roots of chromatic polynomials. For more details on the chromatic polynomials, see [40]. Surprisingly, in the following theorem we observe that there is a constant bound for the roots of the edge cover polynomials.Theorem 39 (see [38]).
All roots of the edge cover polynomial lie in the ball(17){z∈ℂ:|z|<(2+3)21+3≃5.099}.Here, we would like to study the edge cover polynomial of a graphG at -1. We need the following theorem.Theorem 40 (see [38]).
LetG be a graph. Then E(G,x)=∑S⊆V(G)‍(-1)|S|(x+1)|E(G∖S)|.Theorem 41.
LetG be a graph of order n. Then E(G,-1)=(-1)nI(G,-1).Proof.
Clearly,E(G∖S)=0 implies that V(G)∖S is an independent set of G and vice versa. So by Theorem 40, E(G,-1)=(-1)nI(G,-1).By Theorems26 and 41 we have the following result.Theorem 42 (see [37]).
For every graphG, |E(G,-1)|≤2ν(G), where ν(G) is the decycling number of G.


## 5. Open Problems and Conjectures

In this section, we state and review some open problems and conjectures related to the subject of this paper.We have characterized all graphs with exactly three distinct domination roots and proved that for any graphG with exactly three distinct domination roots, we have
(18)Z(D(G,x))⊆{0,-3±52,-2±2i,-3±3i2}.
The following problem remains as an open problem.Problem 1 (see [16]).
Characterize all graphs with exactly three distinct domination roots{0,(-3±3i)/2}.We characterized graphs with four distinct rootsZ(D(G,x))={-2,0,(-3±5)/2}. We think that the number of algebraic integers which can be roots of graphs with exactly four distinct domination roots are about nine numbers, but we couldn't prove it yet. So complete characterization of graphs with exactly four distinct domination roots remains as an open problem. In other words, we have two following questions regarding graphs with exactly four distinct domination roots.Problem 2.
Which algebraic integers are domination roots of graphs with exactly four distinct domination roots?Problem 3 (see [21]).
Characterize all graphs with exactly four distinct domination roots.There are graphs with no nonzero real domination roots except zero. As examples for every evenn, no nonzero real numbers are domination roots of Kn,n, and no nonzero real numbers are domination roots of Dutch Windmill graphs (see [24]). So the following question is an interesting problem.Problem 4 (see [16]).
Characterize all graphs with no real domination roots except zero.Corollary6 implies that every integer domination root of a graph is even. We recall the following conjecture.Conjecture 2 (see [16]).
Ifr is an integer domination root of a graph, then r=0 or r=-2.Conjecture 3.
Real roots of the familiesD(Pn,x) and D(Cn,x) are dense in the interval [-2,0], for n≥4.Theorem25 implies that for a graph of order n, I(G,x) has exactly one root if and only if G=rKs, where n=rs for some natural r, s. Also Theorem 21 characterizes line graphs whose independence polynomials have at most five distinct roots. Therefore, complete characterization of graphs with few independence roots remains as an open problem.Problem 5.
Characterize all graphs with few independence roots.The following conjectures are related to the roots of edge cover polynomial of a graph.Conjecture 4 (see [37]).
Ifδ(G)=2 and G≠K3, then E(G,x) has at least three distinct roots.Conjecture 5 (see [37]).
LetG be a graph. Then E(G,x) has at least δ(G) distinct roots.Conjecture 6 (see [38]).
LetG be a graph with δ(G)=2. If E(G,x) has only real roots, then all connected components of G are cycles.



---

*Source: 195818-2013-09-12.xml*