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í toán học quốc tế đề tài: ALGEBRAIC MATCHING THEORY. | ALGEBRAIC MATCHING THEORY C. D. Godsil 1 Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada N2L 3G1 chris@ Submitted July 6 1994 Accepted April 11 1995. Abstract The number of vertices missed by a maximum matching in a graph G is the multiplicity of zero as a root of the matchings polynomial d G x of G and hence many results in matching theory can be expressed in terms of this multiplicity. Thus if mult ớ G denotes the multiplicity of 0 as a zero of G x then Gallai s lemma is equivalent to the assertion that if mult ớ G u mult ớ G for each vertex u of G then mult ớ G 1. This paper extends a number of results in matching theory to results concerning mult ớ G where Ỡ is not necessarily zero. If P is a path in G then G P denotes the graph got by deleting the vertices of P from G. We prove that mult ớ G P mult ớ G 1 and we say P is ớ-essential when equality holds. We show that if all paths in G are ớ-essential then mult ớ G 1. We dehne G to be 0-critical if all vertices in G are ớ-essential and mult ớ G 1. We prove that if mult ớ G k then there is an induced subgraph H with exactly k ớ-critical components and the vertices in G H are covered by k disjoint paths. AMS Classihcation Numbers 05C70 05E99 1 Support from grant OGP0009439 of the National Sciences and Engineering Council of Canada is gratefully acknowledged. THE ELECTRONIC JOURNAL OF COMBINATORICS 2 1995 R8 2 1. Introduction A k-matching in a graph G is a matching with exactly k edges and the number of k-matchings in G is denoted by by p G k . If n IV G I we dehne the matchings polynomial M G x by p G x X 1 kp G k xn 2k. k 0 Here p G 0 1. By way of example the matchings polynomial of the path on four vertices is x4 3x2 1. The matchings polynomial is related to the characteristic polynomial Á G x of G which is dehned to be the characteristic polynomial of the adjacency matrix of G. In particular Á G x p G x if and only if G is a forest 4 Corollary . .
