Let be a simple graph of order and . A mapping 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 , 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. 1. Introduction Let be a simple graph and . A mapping 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 . A zero of is called a chromatic zero of . For a complete survey on chromatic polynomial and chromatic root, see [1]. For any vertex , the open neighborhood of is the set , and the closed neighborhood is the set . For a set , the open neighborhood of is , and the closed neighborhood of is . A set is a dominating set if , or, equivalently, every vertex in is adjacent to at least one vertex in . An -subset of is a subset of of cardinality . Let be the family of dominating sets of which are -subsets and let . The polynomial is defined as domination polynomial of [2, 3]. A root of is called a domination root of . We denote the set of all roots of by . 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 with rational coefficients, called the minimal polynomial of (over the rationals), with the property that 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 Sections 2 and 3, we study algebraic integers as chromatic roots and domination roots,
References
[1]
F. M. Dong, K. M. Koh, and K. L. Teo, Chromatic Polynomials and Chromaticity of Graphs, World Scientific Publishing, 2005.
[2]
S. Akbari, S. Alikhani, and Y.-H. Peng, “Characterization of graphs using domination polynomials,” European Journal of Combinatorics, vol. 31, no. 7, pp. 1714–1724, 2010.
[3]
S. Alikhani and Y. H. Peng, “Introduction to domination polynomial of a graph,” Ars Combinatoria, In press, http://arxiv.org/abs/0905.2251.
[4]
S. Alikhani and Y.-H. Peng, “Dominating sets and domination polynomials of certain graphs—II,” Opuscula Mathematica, vol. 30, no. 1, pp. 37–51, 2010.
[5]
S. Alikhani and Y.-H. Peng, “Dominating sets and domination polynomials of paths,” International Journal of Mathematics and Mathematical Sciences, vol. 2009, Article ID 542040, 10 pages, 2009.
[6]
S. Alikhani and Y.-H. Peng, “Domination polynomials of cubic graphs of order 10,” Turkish Journal of Mathematics, vol. 35, no. 3, pp. 355–366, 2011.
[7]
I. Stewart and D. Tall, Algebraic Number Theory, Chapman & Hall, London, UK, 2nd edition, 1987.
[8]
B. Jackson, “A zero-free interval for chromatic polynomials of graphs,” Combinatorics, Probability and Computing, vol. 2, no. 3, pp. 325–336, 1993.
[9]
W. T. Tutte, “On chromatic polynomials and the golden ratio,” Journal of Combinatorial Theory, vol. 9, pp. 289–296, 1970.
[10]
J. Salas and A. D. Sokal, “Transfer matrices and partition-function zeros for antiferromagnetic Potts models—I. General theory and square-lattice chromatic polynomial,” Journal of Statistical Physics, vol. 104, no. 3-4, pp. 609–699, 2001.
[11]
S. Alikhani and Y.-H. Peng, “Chromatic zeros and the golden ratio,” Applicable Analysis and Discrete Mathematics, vol. 3, no. 1, pp. 120–122, 2009.
[12]
S. Alikhani and Y.-H. Peng, “Chromatic zeros and generalized Fibonacci numbers,” Applicable Analysis and Discrete Mathematics, vol. 3, no. 2, pp. 330–335, 2009.
[13]
A. D. Sokal, “Chromatic roots are dense in the whole complex plane,” Combinatorics, Probability and Computing, vol. 13, no. 2, pp. 221–261, 2004.
[14]
A. A. Zykov, “On some properties of linear complexes,” Journal of Combinatorial Theory B, vol. 24, no. 66, pp. 163–188, 1949.
[15]
P. J. Cameron, “Algebraic properties of chromatic roots,” in Proceedings of the 7th Australian and New Zealand Mathematics Convention, Christchurch, New Zealand, December 2008.
[16]
A. E. Brouwer, “The number of dominating sets of a finite graph is odd,” preprint.
[17]
S. Alikhani, “The domination polynomial of a graph at-1,” Graphs and Combinatorics. In press.
[18]
S. Akbari, S. Alikhani, M. R. Oboudi, and Y. H. Peng, “On the zeros of domination polynomial of a graph,” in Combinatorics and Graphs, vol. 531, pp. 109–115, American Mathematical Society, Providence, RI, USA, 2010.
[19]
R. Frucht and F. Harary, “On the corona of two graphs,” Aequationes Mathematicae, vol. 4, pp. 322–325, 1970.
[20]
T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley-Interscience, 2001.
[21]
I. N. Herstein, Topics in Algebra, Xerox College Publishing, 1964.
