International Journal of Combinatorics
Volume 2012 (2012), Article ID 780765, 8 pages
http://dx.doi.org/10.1155/2012/780765
Research Article

Algebraic Integers as Chromatic and Domination Roots

Saeid Alikhani1 and Roslan Hasni2

1Department of Mathematics, Yazd University, Yazd 89195-741, Iran
2Department of Mathematics, Faculty of Science and Technology, University Malaysia Terengganu, 21030 Kuala Terengganu, Malaysia

Received 19 January 2012; Accepted 7 March 2012

Academic Editor: Xueliang Li

Copyright © 2012 Saeid Alikhani and Roslan Hasni. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Let 𝐺 be a simple graph of order 𝑛 and 𝜆 ∈ ℕ . A mapping 𝑓 ∶ 𝑉 ( 𝐺 ) → { 1 , 2 , … , 𝜆 } is called a 𝜆 -colouring of 𝐺 if 𝑓 ( 𝑢 ) ≠ 𝑓 ( 𝑣 ) whenever the vertices 𝑢 and 𝑣 are adjacent in 𝐺 . The number of distinct 𝜆 -colourings of 𝐺 , denoted by 𝑃 ( 𝐺 , 𝜆 ) , is called the chromatic polynomial of 𝐺 . The domination polynomial of 𝐺 is the polynomial ∑ 𝐷 ( 𝐺 , 𝜆 ) = 𝑛 𝑖 = 1 𝑑 ( 𝐺 , 𝑖 ) 𝜆 𝑖 , where 𝑑 ( 𝐺 , 𝑖 ) is the number of dominating sets of 𝐺 of size 𝑖 . Every root of 𝑃 ( 𝐺 , 𝜆 ) and 𝐷 ( 𝐺 , 𝜆 ) is called the chromatic root and the domination root of 𝐺 , 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.