Euler’s idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees. (English) Zbl 1289.05043

Azarija, Jernej; Škrekovski, Riste

Math. Bohem. 138, No. 2, 121-131 (2013).

The authors consider the following problem: what is the smallest graphs (either in terms of the number of vertices, or of the number of edges), which contains exactly a given number of spanning trees. This problem was first considered in [J. Sedláček, Can. Math. Bull. 13, 515–517 (1970; Zbl 0202.23501)]. Here, some new bounds on problem are obtained. The central part of the paper comes from explicitly constructed graphs whose number of spanning trees can be controlled.

Reviewer: Jan Hladký (Coventry)

MSC:

05C05	Trees
05C30	Enumeration in graph theory

Keywords:

spanning tree

Citations:

Zbl 0202.23501