Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-05T13:25:16.948Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Minimal Graph with a Given Number of Spanning Trees

Published online by Cambridge University Press:  20 November 2018

J. Sedláček
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).

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 13 , Issue 4 , December 1970 , pp. 515 - 517
Copyright
Copyright © Canadian Mathematical Society 1970

References

1. Sedláček, J., On the spanning trees of finite graphs, Časopis Pěst. Mat. 91 (1966), 221-227.Google Scholar
2. Sedláček, J., On the number of spanning trees of finite graphs, Časopis Pěst. Mat. 94 (1969), 217-221.Google Scholar