# Algebraic Integers as Chromatic and Domination Roots

Authors: Saeid Alikhani; Roslan Hasni
Journal: International Journal of Combinatorics
 (2012)

---

## Abstract

LetG be a simple graph of order n and λ∈ℕ. A mapping f:V(G)→{1,2,…,λ} is called a λ-colouring of G if f(u)≠f(v) whenever the vertices u and v are adjacent in G. The number of distinct λ-colourings of G, denoted by P(G,λ), is called the chromatic polynomial of G. The domination polynomial of G is the polynomial D(G,λ)=∑i=1nd(G,i)λi, where d(G,i) is the number of dominating sets of G of size i. Every root of P(G,λ) and D(G,λ) is called the chromatic root and the domination root of G, respectively. Since chromatic polynomial and domination polynomial are monic polynomial with integer coefficients, its zeros are algebraic integers. This naturally raises the question: which algebraic integers can occur as zeros of chromatic and domination polynomials? In this paper, we state some properties of this kind of algebraic integers.


---

## Body

## 1. Introduction

LetG be a simple graph and λ∈ℕ. A mapping f:V(G)→{1,2,…,λ} is called a λ-colouring of G if f(u)≠f(v) whenever the vertices u and v are adjacent in G. The number of distinct λ-colourings of G, denoted by P(G,λ), is called the chromatic polynomial of G. A zero of P(G,λ) is called a chromatic zero of G. For a complete survey on chromatic polynomial and chromatic root, see [1].For any vertexv∈V, the open neighborhood of v is the set N(v)={u∈V∣uv∈E}, and the closed neighborhood is the set N[v]=N(v)∪{v}. For a set S⊆V, the open neighborhood of S is N(S)=⋃v∈SN(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. An i-subset of V(G) is a subset of V(G) of cardinality i. Let 𝒟(G,i) be the family of dominating sets of G which are i-subsets and let d(G,i)=|𝒟(G,i)|. The polynomial D(G,x)=∑i=1|V(G)|d(G,i)xi is defined as domination polynomial of G [2, 3]. A root of D(G,x) is called a domination root of G. We denote the set of all roots of D(G,x) by Z(D(G,x)). For more information and motivation of domination polynomial and domination roots, refer to [2–6].We recall that a complex numberζ is called an algebraic number (respectively, algebraic integer) if it is a zero of some monic polynomial with rational (resp., integer) coefficients (see [7]). Corresponding to any algebraic number ζ, there is a unique monic polynomial p with rational coefficients, called the minimal polynomial of ζ (over the rationals), with the property that p divides every polynomial with rational coefficients having ζ as a zero. (The minimal polynomial of ζ has integer coefficients if and only if ζ is an algebraic integer.)Since the chromatic polynomial and domination polynomial are monic polynomial with integer coefficients, its zeros are algebraic integers. This naturally raises the question: which algebraic integers can occur as zeros of chromatic and domination polynomials?In Sections2 and 3, we study algebraic integers as chromatic roots and domination roots, respectively.As usual, we denote the complete graph of ordern and the complement of G, by Kn and G¯, respectively.


## 2. Algebraic Integers as Chromatic Roots

Since chromatic polynomial is monic polynomial with integer coefficients, its zeros are algebraic integers. An interval is called azero-free interval for a chromatic (domination) polynomial, if G has no chromatic (domination) zero in this interval. It is well known that (-∞,0) and (0,1) are two maximal zero-free intervals for chromatic polynomials of the family of all graphs (see [8]). Jackson [8] showed that (1,32/27] is another maximal zero-free interval for chromatic polynomials of the family of all graphs and the value 32/27 is best possible.For chromatic polynomials clearly those roots lying in(-∞,0)∪(0,1)∪(1,32/27] are forbidden. Tutte [9] proved that B5=(3+5)/2=1+τ, where τ=(1+5)/2 is the golden ratio, cannot be a chromatic zero. Salas and Sokal in [10] extended this result to show that the numbers Bn(k)=4cos⁡2(kπ/n) for n=5,7,8,9 and n≥11, with k coprime to n, are never chromatic zeros. For n=10 they showed the weaker result that B10=(5+5)/2 and B10*=(5-5)/2 are not chromatic zeros of any plane near-triangulation.Alikhani and Peng [11] have obtained the following theorem.Theorem 2.1.
τn(n∈ℕ), where  τ=(1+5)/2 is the golden ratio, cannot be zeros of any chromatic polynomials.Also they extended this result to show thatϕ2n and all their natural powers cannot be chromatic zeros, where ϕn is called n-annaci constant [12].For some times it was thought that chromatic roots must have nonnegative real part. This is true for graphs with fewer than ten vertices. But Sokal showed the following.Theorem 2.2 (see [13]).
Complex chromatic roots are dense in the complex plane.Theorem 2.3.
The set of chromatic roots of a graphG is not a semiring.Proof.
The set of chromatic roots is not closed under either addition or multiplication, because it suffices to considerα+α* and αα*, where α is nonreal and close to the origin.Theorem 2.4.
Suppose thata,b are rational numbers,  r≥2 is an integer that is not a perfect square, and  a-|b|r<32/27. Then  a+br is not the root of any chromatic polynomial.Proof.
Ifλ=a+br is a root of some polynomial with integer coefficients (e.g., a chromatic polynomial), then so is λ*=a-br. But λ or λ* cannot belong to (-1,0)∪(0,1)∪(1,32/27], a contradiction.Corollary 2.5.
Letb be a rational number, and let  r be a positive rational number such that  r is irrational. Then  br cannot ba a root of any chromatic polynomial.We know that for every graphG with edge e=xy, P(G,λ)=P(G+e,λ)+P(G·e,λ), where G·e is the graph obtained from G by contracting x and y and removing any loop. By applying this recursive formula repeatedly, we arrive at(2.1)P(G,λ)=∑i≥1biP(Ki,λ)=∑i≥1bi(λ)i,
where bi’s are some constants and(2.2)(λ)i=λ(λ-1)⋯(λ-i+1).
Let us recall the definition of join of two graphs. 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)}.Theorem 2.6 (see [14]).
LetG1 and  G2 be any two graphs with  P(Gi,λ) expressed in factorial form,  i=1,2. Then
(2.3)P(G1+G2,λ)=P(G1,λ)⊗P(G2,λ),
where ⊗ is called umbral product, and acts as powers (i.e., (λ)i⊗(λ)j=(λ)i+j).Here we state and prove the following theorem.Theorem 2.7.
For any graphH,
(2.4)P(H+Kn,λ)=λ(λ-1)⋯(λ-n+1)P(H,λ-n).Proof.
It suffices to prove it forn=1. Assume that P(H,λ)=∑i≥1bi(λ)i. By Theorem 2.6,
(2.5)P(H+K1,λ)=P(H,λ)⊗(λ)1=∑i≥1bi(λ)i+1=λ∑i≥1bi(λ-1)i=λP(H,λ-1).Here we state and prove the following theorem.Theorem 2.8.
Ifα is a chromatic root, then for any natural number  n,  α+n is a chromatic root.Proof.
Since(2.6)P(G+Kn,λ)=λ(λ-1)⋯(λ-n+1)P(G,λ-n),
we have the result.By Theorem2.1, τ and τ+1=τ2 are not chromatic roots. However τ+3 is a chromatic root (see Theorem 2.14). Therefore by Theorem 2.8 we have the following corollary:Corollary 2.9.
For every natural numbern≥3,  τ+n is a chromatic root.There are the following conjectures.Conjecture 2.10 (see [15]).
Letα be an algebraic integer. Then there exists a natural number  n such that  α+n is a chromatic root.Conjecture 2.11 (see [15]).
Letα be a chromatic root. Then  nα is a chromatic root for any natural number  n.Definition 2.12 (see [15]).
A ring of cliques is the graphR(a1,…,an) whose vertex set is the union of n+1 complete subgraphs of sizes 1,a1,…,an, where the vertices of each clique are joined to those of the cliques immediately preceding or following it modn+1.Theorem 2.13 (see [15]).
The chromatic polynomial ofR(a1,…,an) is a product of linear factors and the polynomial
(2.7)1q(∏i=1n(q-ai)-∏i=1n(-ai)).We call the polynomial in Theorem2.13 the interesting factor.Theorem 2.14.
τ+3 is a chromatic root.Proof.
Consider the graphR(1,1,5). Obviously this graph has eight vertices and by Theorem 2.13 its interesting factor is q2-7q+11, with roots (7±5)/2. Therefore the graph R(1,1,5) has τ+3 as chromatic root.Remark 2.15.
We observed thatτ+n is a chromatic root for every n≥3. Also we saw that τ+1 is not a chromatic root, but we do not know whether τ+2 is a chromatic root or not. Therefore this remains as an open problem.


## 3. Algebraic Integers as Domination Roots

For domination polynomial of a graph, it is clear that(0,∞) is zero-free interval. Brouwer [16] has shown that −1 cannot be domination root of any graph G. For more details of the domination polynomial of a graph at −1 refer to [17]. We also have shown that every integer domination root is even [18].Let us recall the corona of two graphs. Thecorona of two graphs G1 and G2, as defined by Frucht and Harary in [19], 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.Here we state the following theorem.Theorem 3.1 (see [2]).
LetG be a graph. Then  D(G,x)=xn(x+2)n if and only if  G=H∘K1 for some graph  H of order  n.By above theorem there are infinite classes of graphs which have −2 as domination roots. Since −1 is not domination root of any graph, so we do not have result for domination roots similar to Theorem2.8. Also we think that the following conjecture is correct.Conjecture 3.2 (see [18]).
Ifr is an integer domination root of a graph, then  r=0 or  r=-2.Now we recall the following theorem.Theorem 3.3 (see [2]).
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(H∘K¯2,x)=xn/3(x2+3x+1)n/3.The following corollary is an immediate consequence of above theorem.Corollary 3.4.
All graphs of the formH∘K¯2, have  -τ2 as domination roots.The following theorem state that-τ cannot be a domination root.Theorem 3.5.
-τ cannot be a domination root.Proof.
LetG be any graph. Since D(G,-τ) is a polynomial with integral coefficients, we have D(G,(-1+5)/2)=0. But (-1+5)/2>0, a contradiction.The following theorem is similar to Theorem3.6 for domination roots.Theorem 3.6.
Suppose thata,b are rational numbers,  r≥2 is an integer that is not a perfect square, and  a-|b|r<0. Then  -a-br is not the root of any domination polynomial.Proof.
Ifλ=-a-br is a root of some polynomial with integer coefficients (e.g., a domination polynomial), then so is λ*=-a+br. But λ*∈(0,∞), a contradiction.Corollary 3.7.
Letb be a rational number, and let  r be a positive rational number such that  r is irrational. Then  -|b|r cannot ba a root of any domination polynomial.Here we will prove that-τn for odd n, cannot be a domination root. We need some theorems.Theorem 3.8 (see [20]).
For every natural numbern,
(3.1)Fn=15(τn-(1-τ)n).Corollary 3.9.
For every natural numbern(3.2)FnFn-1{<τifniseven,>τifnisodd.Proof.
This follows from Theorem3.8Now, we recall the Cassini’s formula.Theorem 3.10 (Cassini’s formula [20]).
One has(3.3)Fn-1Fn+1-Fn2=(-1)n,
where n≥1.Using this formula, we prove another property of golden ratio and Fibonacci numbers which is needed for the proof of Theorem3.13.Theorem 3.11.
(3.4)Fn-1-τ-1Fn∈{(0,1Fn-1)ifniseven,(-1Fn-1,0)ifnisodd.Proof.
Suppose thatn is even, therefore n-1 is odd, and by Corollary 3.9, we have
(3.5)Fn-1Fn-2>τ>FnFn-1.
Hence,
(3.6)Fn-1Fn>τ-1>Fn-2Fn-1,
and by multiplying Fn in this inequality, we have
(3.7)Fn-1>τ-1Fn>Fn-2FnFn-1.
Thus,
(3.8)0>τ-1Fn-Fn-1>(-1)n-1Fn-1.
By Theorem 3.10, we have
(3.9)(-1)nFn-1>Fn-1-τ-1Fn>0.
Hence, for even n,
(3.10)0<Fn-1-τ-1Fn<1Fn-1.
Similarly, the result holds when n is odd.Theorem 3.12 (see [20, page 78]).
For everyn≥2, τn=Fnτ+Fn-1(n≥2).Now we are ready to prove the following theorem.Theorem 3.13.
Letn be an odd natural number. Then  -τn cannot be domination roots.Proof.
By Theorem3.12, we can write
(3.11)τn=Fnτ+Fn-1=(Fn2+Fn-1)+(5Fn2).
Suppose that D(G,-τn)=0, that is
(3.12)D(G,(-Fn+1+Fn-12-5Fn2))=0.
Then
(3.13)D(G,(-Fn+1+Fn-12+5Fn2))=0
(see page  187 in [21]), but we can write
(3.14)-Fn+1+Fn-12+5Fn2=-(-τ-1Fn+Fn-1).
By Theorem 3.11, -(-τ-1Fn+Fn-1)∈(-1,0) when n is even and -(-τ-1Fn+Fn-1)∈(0,1) when n is odd. Since n is odd, we have -(-τ-1Fn+Fn-1)∈(0,1). But we know that (0,∞) is zero-free interval for domination polynomial of any graph. Hence we have a contradiction.



---

*Source: 780765-2012-05-14.xml*