Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Maximum Multiplicity of Matching Polynomial Roots and Minimum Path Cover in General Graphs. | Maximum Multiplicity of Matching Polynomial Roots and Minimum Path Cover in General Graphs Cheng Yeaw Ku Department of Mathematics National University of Singapore Singapore 117543 matkcy@ Kok Bin Wong Institute of Mathematical Sciences University of Malaya 50603 Kuala Lumpur Malaysia kbwong@ Submitted Oct 15 2009 Accepted Jan 29 2011 Published Feb 14 2011 Mathematics Subject Classification 05C31 05C70 Abstract Let G be a graph. It is well known that the maximum multiplicity of a root of the matching polynomial G x is at most the minimum number of vertex disjoint paths needed to cover the vertex set of G. Recently a necessary and sufficient condition for which this bound is tight was found for trees. In this paper a similar structural characterization is proved for any graph. To accomplish this we extend the notion of a Ớ G -extremal path cover where 0 is a root of p G x which was first introduced for trees to general graphs. Our proof makes use of the analogue of the Gallai-Edmonds Structure Theorem for general root. By way of contrast we also show that the difference between the minimum size of a path cover and the maximum multiplicity of matching polynomial roots can be arbitrarily large. 1 Introduction All the graphs in this paper are simple. The vertex set and edge set of a graph G are denoted by V G and E G respectively. A matching of a graph G is a set of pairwise non-adjacent edges of G. Recall that for a graph G on n vertices the matching polynomial p G x of G is given by p G x -1 kp G k xn 2k k 0 where p G k is the number of matchings with k edges in G and p G 0 1 by convention. Let mult ớ G denote the multiplicity of Ỡ as a root of p G x . THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P38 1 The following result is well known. A proof of this assertion can be found in 2 Theorem on p. 107 . Theorem . The maximum multiplicity of a root of the matching polynomial p G x is at most the minimum number of vertex disjoint paths needed
