Counting spanning trees in the graphs of Kleitman and Golden and a generalization
type: Item
instance of: scholarly article
title: Counting spanning trees in the graphs of Kleitman and Golden and a generalization
zbMATH Open document ID: 0569.05016
DOI: 10.1016/0016-0032(84)90054-1
author: B. George
published in: Journal of the Franklin Institute
publication date: 1984-01-01T00:00:00Z
review text: The number of trees in a graph G on \(n+1\) vertices is, by the celebrated matrix tree theorem, given by the determinant of an \(n\times n\) matrix whose (i-th entry is 1 when G has an edge connecting the i-th and j-th vertices (for i and j between 1 and n) and i-th diagonal element given by minus the degree of the i-th vertex. The authors here use properties of circulant matrices to evaluate this determinant in the case in which the \((n+1)\times (n+1)\) matrix of which this is a cofactor, is a circulant.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 3908452
reviewed by: Daniel J. Kleitman
MaRDI profile type: Publication
full work available at URL: 0016-0032(84)90054-1
OpenAlex ID: W2059247311
cites work: Counting Trees in a Certain Class of Graphs
cites work: Parallel concepts in graph theory
cites work: Q3943047
cites work: Number fields
cites work: The Fibonacci numbers via trigonometric expressions
description: scientific article; zbMATH DE number 3908452