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

Page 1 Next

Displaying 1 – 20 of 22

Showing per page

Edge Dominating Sets and Vertex Covers

Ronald Dutton, William F. Klostermeyer (2013)

Discussiones Mathematicae Graph Theory

Bipartite graphs with equal edge domination number and maximum matching cardinality are characterized. These two parameters are used to develop bounds on the vertex cover and total vertex cover numbers of graphs and a resulting chain of vertex covering, edge domination, and matching parameters is explored. In addition, the total vertex cover number is compared to the total domination number of trees and grid graphs.

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 1 – 20 of 22

Page 1 Next