Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T11:11:17.007Z Has data issue: false hasContentIssue false

On the Minimal Graph with a Given Number of Spanning Trees

Published online by Cambridge University Press:  20 November 2018

J. Sedláček*
Affiliation:
University of Calgary, Calgary, Alberta
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let G be a finite connected graph without loops or multiple edges. A maximal tree subgraph T of G is called a spanning tree of G. Denote by k(G) the number of all trees spanning the graph G. A. Rosa formulated the following problem (private communication): Let x(≠2) be a given positive integer and denote by α(x) the smallest positive integer y having the following property: There exists a graph G on y vertices with x spanning trees. Investigate the behavior of the function α(x).

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1970