The number of spanning trees in an (r, s)‐semiregular graph and its line graph. Issue 8 (26th June 2012)

• Record Type: Journal Article
• Authors: Bibak, Khodakhast
• Is Part Of: International journal of quantum chemistry. Volume 113:Issue 8(2013:Apr. 15)
• Page Start: 1209
• Page End: 1212
• Publication Date: 2012-06-26
• Subjects: Quantum chemistry -- Periodicals; 541.28
• DOI: 10.1002/qua.24252
• Languages: English
• ISSNs: 0020-7608

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>For a graph <italic>G</italic>, a "spanning tree" in <italic>G</italic> is a tree that has the same vertex set as <italic>G</italic>. The number of spanning trees in a graph (network) <italic>G</italic>, denoted by <italic>t</italic>(<italic>G</italic>), 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 (<italic>r</italic>, <italic>s</italic>)‐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 (<italic>r</italic>, <italic>s</italic>)‐semiregular graph, we give a new proof of Cayley's Theorem. © 2013 Wiley Periodicals, Inc.</p> </abstract>