Classification of interpolation theorems for spanning trees and other families of spanning subgraphs

✍ Scribed by Frank Harary; Michael J. Plantholt

• Publisher: John Wiley and Sons
• Year: 1989
• Tongue: English
• Weight: 518 KB
• Volume: 13
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190130606

✦ Synopsis

We say that a graphical invariant i of a graph interpolates over a family 8 of graphs if i satisfies the following property: If rn and M are the minimum and maximum values (respectively) of i over all graphs in 8 then for each k , rn 4 k I M , there is a graph H in 8 for which i ( H ) = k . In previous works it was shown that when 8 is the set of spanning trees of a connected graph G, a large number of invariants interpolate (some of these invariants require the additional assumption that G be 2-connected). Although the proofs of all these results use the same basic idea of gradually transforming one tree into another via a sequence of edge exchanges, some of these processes require sequences that use more properties of trees than do others. We show that the edge exchange proofs can be divided into three types, in accordance with the extent to which the exchange sequence depends upon properties of spanning trees. This idea is then used to obtain new interpolation results for some invariants, and to show how the exchange 'methods and interpolation results on spanning trees can be extended to other families of spanning subgraphs.