%0 Journal Article
%T Graphs Whose Certain Polynomials Have Few Distinct Roots
%A Saeid Alikhani
%J ISRN Discrete Mathematics
%D 2013
%R 10.1155/2013/195818
%X 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¨C9]. 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
%U http://www.hindawi.com/journals/isrn.discrete.mathematics/2013/195818/