Matroid tree graphs and interpolation theorems

✍ Scribed by Sanming Zhou

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 119 KB
• Volume: 137
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)91429-t

✦ Synopsis

Using the Hamiltonicity of matroid tree graphs we give a new proof for an interpolation theorem of and other related results. From the proof we refine a general approach for dealing with interpolation problems of graphs.

Let G be a simple, connected graph of order p and size q. For each integer m, p-1 <~m<<,q, denote by Cm(G) the set of connected spanning subgraphs of G with m edges. Whenever H~Cm(G), let ~0(H) be the number of pendant vertices of H. Thus, r¢ is a mapping from Cm(G) to 7/+, the set of nonnegative integers. If m =p-1, Cm(G) is exactly the set of spanning trees of G. It was first proved in [6,1 that ~p(Cp_ I(G)) is an integer interval. An elegant proof for this result was given in . In general, Barefoot [1] proved the following theorem.