All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 5 Next

Displaying 81 – 100 of 204

Showing per page

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

Jernej Azarija, Riste Škrekovski (2013)

Mathematica Bohemica

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 ¬ ≡ 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.

Currently displaying 81 – 100 of 204