Premium
The number of spanning trees in an ( r , s )‐semiregular graph and its line graph
Author(s) -
Bibak Khodakhast
Publication year - 2012
Publication title -
international journal of quantum chemistry
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.484
H-Index - 105
eISSN - 1097-461X
pISSN - 0020-7608
DOI - 10.1002/qua.24252
Subject(s) - spanning tree , combinatorics , line graph , graph factorization , cubic graph , mathematics , discrete mathematics , factor critical graph , trémaux tree , minimum spanning tree , voltage graph , mathematical proof , minimum degree spanning tree , graph , pathwidth , geometry
For a graph G , a “spanning tree” in G is a tree that has the same vertex set as G . The number of spanning trees in a graph (network) G , denoted by t ( G ), is an important invariant of the graph (network) with lots of decisive applications in many disciplines. In the article by Sato (Discrete Math. 2007, 307, 237), the number of spanning trees in an ( r , s )‐semiregular graph and its line graph are obtained. In this article, we give short proofs for the formulas without using zeta functions. Furthermore, by applying the formula that enumerates the number of spanning trees in the line graph of an ( r , s )‐semiregular graph, we give a new proof of Cayley's Theorem. © 2013 Wiley Periodicals, Inc.