On encodings of spanning trees |
| |
Authors: | Glenn H Hurlbert |
| |
Institution: | Department of Mathematics and Statistics, Arizona State University, Tempe, AZ 85287-1804, USA |
| |
Abstract: | Deo and Micikevicius recently gave a new bijection for spanning trees of complete bipartite graphs. In this paper we devise a generalization of Deo and Micikevicius's method, which is also a modification of Olah's method for encoding the spanning trees of any complete multipartite graph K(n1,…,nr). We also give a bijection between the spanning trees of a planar graph and those of any of its planar duals. Finally we discuss the possibility of bijections for spanning trees of DeBriujn graphs, cubes, and regular graphs such as the Petersen graph that have integer eigenvalues. |
| |
Keywords: | 05C05 05C85 68R10 |
本文献已被 ScienceDirect 等数据库收录! |
|