Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees

Title:

Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees

Creator:

Azarija, Jernej and Škrekovski, Riste

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:e06bbaed-91ed-401a-b451-648bb1fede67
uuid:e06bbaed-91ed-401a-b451-648bb1fede67
doi:10.21136/MB.2013.143285

Subject:

number of spanning trees and extremal graph

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

Let α(n) be the least number k for which there exists a simple graph with k vertices having precisely n ≥ 3 spanning trees. Similarly, define β(n) as the least number k for which there exists a simple graph with k edges having precisely n ≥ 3 spanning trees. As an n-cycle has exactly n spanning trees, it follows that α(n), β(n) ≤ n. In this paper, we show that α(n) ≤ 1⁄3 (n + 4) and β(n) ≤ 1⁄3 (n + 7) if and only if n /∈ {3, 4, 5, 6, 7, 9, 10, 13, 18, 22}, which is a subset of Euler’s idoneal numbers. Moreover, if n 6≡ 2 (mod 3) and n ≠ 25 we show that α(n) ≤ 1⁄4 (n + 9) and β(n) ≤ 1⁄4 (n + 13). This improves some previously estabilished bounds.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

121-131

Source:

Mathematica bohemica | 2013 Volume:138 | Number:2

Harvested from:

CDK

Metadata only:

false