Spanning trees of extended graphs |
| |
Authors: | A K Kelmans |
| |
Institution: | (1) RUTCOR, Rutgers University, 08903 New Brunswick, NJ, USA |
| |
Abstract: | A generalization of the Prüfer coding of trees is given providing a natural correspondence between the set of codes of spanning trees of a graph and the set of codes of spanning trees of theextension of the graph. This correspondence prompts us to introduce and to investigate a notion ofthe spanning tree volume of a graph and provides a simple relation between the volumes of a graph and its extension (and in particular a simple relation between the spanning tree numbers of a graph and its uniform extension). These results can be used to obtain simple purely combinatorial proofs of many previous results obtained by the Matrix-tree theorem on the number of spanning trees of a graph. The results also make it possible to construct graphs with the maximal number of spanning trees in some classes of graphs. |
| |
Keywords: | 05 C 05 05 C 30 |
本文献已被 SpringerLink 等数据库收录! |
|