Let 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 . 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. 1. Introduction Let 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 graph . For convenience, the definition of these polynomials will be given in the following sections. The corona of two graphs and , as defined by Frucht and Harary in [1], is the graph formed from one copy of and copies of , where the th vertex of is adjacent to every vertex in the th copy of . The corona , in particular, is the graph constructed from a copy of , where for each vertex , a new vertex and a pendant edge are added. The join of two graphs and , denoted by is a graph with vertex set and edge set and . The decycling number (or the feedback vertex number) of a graph 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. If is the adjacency matrix of , then the eigenvalues of , are said to be the eigenvalues of the graph . These are the roots of the characteristic polynomial . 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 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 Section 2, we investigate graphs with few domination roots. In Section 3, we study graphs whose
References
[1]
R. Frucht and F. Harary, “On the corona of two graphs,” Aequationes Mathematicae, vol. 4, pp. 322–325, 1970.
[2]
D. M. Cvetkovi？, M. Doob, and H. Sachs, Spectra of Graphs: Theory and Applications, Johann Ambrosius Barth, Heidelberg, Germany, 3rd edition, 1995.
[3]
W. G. Bridges and R. A. Mena, “Multiplicative cones—a family of three eigenvalue graphs,” Aequationes Mathematicae, vol. 22, no. 2-3, pp. 208–214, 1981.
[4]
M. Muzychuk and M. Klin, “On graphs with three eigenvalues,” Discrete Mathematics, vol. 189, no. 1–3, pp. 191–207, 1998.
[5]
E. R. van Dam, “Regular graphs with four eigenvalues,” Linear Algebra and Its Applications, vol. 226–228, pp. 139–162, 1995.
[6]
E. R. van Dam, Graphs with few eigenvalues—an interplay between combinatorics and algebra [Ph.D. thesis], Center Dissertation Series 20, Tilburg University, 1996.
[7]
E. R. van Dam, “Nonregular graphs with three eigenvalues,” Journal of Combinatorial Theory. Series B, vol. 73, no. 2, pp. 101–118, 1998.
[8]
E. R. van Dam and W. H. Haemers, “Which graphs are determined by their spectrum?” Linear Algebra and Its Applications, vol. 373, pp. 241–272, 2003.
[9]
E. R. van Dam and E. Spence, “Small regular graphs with four eigenvalues,” Discrete Mathematics, vol. 189, no. 1–3, pp. 233–257, 1998.
[10]
H. Chuang and G. R. Omidi, “Graphs with three distinct eigenvalues and largest eigenvalues less than 8,” Linear Algebra and Its Applications, vol. 430, no. 8-9, pp. 2053–2062, 2009.
[11]
T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs, vol. 208 of Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, New York, NY, USA, 1998.
[12]
S. Alikhani and Y. H. Peng, “Introduction to domination polynomial of a graph,” Ars Combinatoria, http://arxiv.org/abs/0905.2251.
[13]
S. Alikhani and Y. Peng, “Dominating sets and domination polynomials of certain graphs. II,” Opuscula Mathematica, vol. 30, no. 1, pp. 37–51, 2010.
[14]
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.
[15]
J. Brown and J. Tufts, “On the roots of domination polynomials,” Graphs and Combinatorics, 2013.
[16]
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.
[17]
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.
[18]
A. E. Brouwer, “The number of dominating sets of a finite graph is odd,” preprint.
[19]
S. Alikhani, “The domination polynomial of a graph at—1,” Graphs and Combinatorics, vol. 29, no. 5, pp. 1175–1181, 2013.
[20]
S. Akbari and M. R. Oboudi, “Cycles are determined by their domination polynomials,” Ars Combinatoria, http://arxiv.org/abs/0908.3305.
[21]
S. Alikhani, “On the graphs with four distinct domination roots,” International Journal of Computer Mathematics, vol. 88, no. 13, pp. 2717–2720, 2011.
[22]
S. Alikhani and R. Hasni, “Algebraic integers as chromatic and domination roots,” International Journal of Combinatorics, vol. 2012, Article ID 780765, 8 pages, 2012.
[23]
S. Alikhani, Dominating sets and domination polynomials of graphs [Ph.D. thesis], Universiti Putra Malaysia, 2009.
[24]
S. Alikhani and E. Deutsch, “New results on domination polynomals and domination roots,” submitted.
[25]
E. J. Farrell, “On a general class of graph polynomials,” Journal of Combinatorial Theory. Series B, vol. 26, no. 1, pp. 111–122, 1979.
[26]
E. J. Farrell, “An introduction to matching polynomials,” Journal of Combinatorial Theory. Series B, vol. 27, no. 1, pp. 75–86, 1979.
[27]
C. D. Godsil, “Algebraic matching theory,” Electronic Journal of Combinatorics, vol. 2, article R8, 1995.
[28]
O. J. Heilmann and E. H. Lieb, “Monomers and dimers,” Physical Review Letters, vol. 24, no. 25, pp. 1412–1414, 1970.
[29]
C. D. Godsil, Algebraic Combinatorics, Chapman and Hall Mathematics Series, Chapman & Hall, New York, NY, USA, 1993.
[30]
E. Ghorbani, “Graphs with few matching roots,” Graphs and Combinatorics, vol. 29, no. 5, pp. 1377–1389, 2013.
[31]
S. Alikhani and Y. Peng, “Independence roots and independence fractals of certain graphs,” Journal of Applied Mathematics and Computing, vol. 36, no. 1-2, pp. 89–100, 2011.
[32]
J. I. Brown, C. A. Hickman, and R. J. Nowakowski, “On the location of roots of independence polynomials,” Journal of Algebraic Combinatorics, vol. 19, no. 3, pp. 273–282, 2004.
[33]
J. I. Brown, K. Dilcher, and R. J. Nowakowski, “Roots of independence polynomials of well covered graphs,” Journal of Algebraic Combinatorics, vol. 11, no. 3, pp. 197–210, 2000.
[34]
C. D. Godsil and I. Gutman, “On the theory of the matching polynomial,” Journal of Graph Theory, vol. 5, no. 2, pp. 137–144, 1981.
[35]
S. Akbari, M. R. Oboudi, and S. Qajar, “On the rational independence roots,” Contemporary Mathematics, vol. 531, pp. 149–158, 2010.
[36]
V. E. Levit and E. Mandrescu, “The independence polynomial of a graph at ？1,” http://arxiv.org/abs/0904.4819v1.
[37]
S. Akbari and M. R. Oboudi, “On the edge cover polynomial of a graph,” European Journal of Combinatorics, vol. 34, no. 2, pp. 297–321, 2013.
[38]
P. Csikvári and M. R. Oboudi, “On the roots of edge cover polynomials of graphs,” European Journal of Combinatorics, vol. 32, no. 8, pp. 1407–1416, 2011.
[39]
A. D. Sokal, “Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions,” Combinatorics, Probability and Computing, vol. 10, no. 1, pp. 41–77, 2001.
[40]
F. M. Dong, K. M. Koh, and K. L. Teo, Chromatic Polynomials and Chromaticity of Graphs, World Scientific Publishing, Hackensack, NJ, USA, 2005.
