Please use this identifier to cite or link to this item:
|Title:||Maximum multiplicity of matching polynomial roots and minimum path cover in general graphs||Authors:||Ku, C.Y.
|Issue Date:||2011||Citation:||Ku, C.Y.,Wong, K.B. (2011). Maximum multiplicity of matching polynomial roots and minimum path cover in general graphs. Electronic Journal of Combinatorics 18 (1) : -. ScholarBank@NUS Repository.||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 Θ is a root of μ(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.||Source Title:||Electronic Journal of Combinatorics||URI:||http://scholarbank.nus.edu.sg/handle/10635/103537||ISSN:||10778926|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.