Abstract:
The number of spanning trees in an arbitrary graph or multigraph is obtained via a general formula involving eigenvalues of an associated matrix, This is shown to be part...Show MoreMetadata
Abstract:
The number of spanning trees in an arbitrary graph or multigraph is obtained via a general formula involving eigenvalues of an associated matrix, This is shown to be particularly useful in the case of graphs (or multigraphs) which are joins, and a method for deriving the appropriate eigenvaiues of joins is given. As applications of this, concise general expressions are derived for the number of spanning trees in any wheel or top. For the ordinarynspoke wheelW_{n+1} = K_{1} + C_{n}the simple formula{\Pi|_{r=1}^{n-1} (3-2 \cos (2r{\pi}/n))is derived. A more general concept of join of multigraphs is introduced, and this is applied to obtain a simple formula in terms of integers and cosines for the number of spanning trees in general multigraph wheels.
Published in: IEEE Transactions on Circuits and Systems ( Volume: 23, Issue: 7, July 1976)