Counting of spanning trees of a complete graph

Anderson Luiz Pedrosa Porto, Vagner Rodrigues de Bessa, Mattheus Pereira da Silva Aguiar, Mariana Martins Vieira

Abstract


In 1889, Arthur Cayley published an article that contained a formula for counting the spanning trees of a complete graph. This theorem says that: Let n E N  and Kn the complete graph with n vertices. Then the number of spanning trees of Kn is established by n n-2: The present work is constituted by a brief literary review about the basic concepts and results of the graph theory and detailed demonstration of the Cayley’s Formula, given by the meticulous construction of a bijection between the set of the spanning trees and a special set of numeric sequences. At the end we bring an algorithm that describes a precise construction of the spanning trees obtained of Kn from Cayley-Prufer sequences.


Keywords


Trees; Spanning Trees; Cayley’s Formula; Complete Graphs; Inverse Process of Cayley-Prufer

References


Abu-Sbeih, M. Z. (1990). On the number of spanning trees of Kn and Km;n. Discrete Mathematics, North-Holland, 84, 205–207.

Bondy, J. A., Murty, U. R. S. (1982). Graph theory with applications, 5o edn. New York: North Holland.

Domingues, H. H., Iezzi, G. (2003). Algebra Moderna ´ , 4o edn. Sao Paulo: Atual.

Fracasso, P. (2008). Analise de t ´ ecnicas para amostragem e sele ´ c¸ao de v ˜ ertices no planejamento probabil ´ ´ıstico de mapa de rotas.

Dissertac¸ao de mestrado, Escola polit ˜ ecnica da USP. ´

Harary, F. (1969). Graph Theory, 1o edn. Menlo Park: Addison Wesley Pub. Co. Inc..

Junior, E. R. H., Nicoletti, M. C. (2006). ´ Fundamentos da teoria dos grafos para computac¸ao ˜ , 1o edn. Sao Carlos: Edufscar. ˜

Konzen, D. C. (1997). Automata and computability, 1o edn. Springer New York.

Orsini, L. Q., Consonni, D. (2002). Curso de circuitos eletricos ´ , 2o edn. Edgard Blucher Ltda. ¨

Wilson, R. J. (1996). Introduction to graph theory, 4o edn. London: Prentice-Hall.

Wu, B. Y., Chao, K. (2004). Spanning trees and optimization problems, 1o edn. Chapman & Hall/CRC Press, USA.




DOI: http://dx.doi.org/10.5902/2179460X27277

Refbacks

  • There are currently no refbacks.