Displaying similar documents to “Cyclic decompositions of complete graphs into spanning trees”

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

Jernej Azarija, Riste Škrekovski (2013)

Mathematica Bohemica

Similarity:

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

Spanning caterpillars with bounded diameter

Ralph Faudree, Ronald Gould, Michael Jacobson, Linda Lesniak (1995)

Discussiones Mathematicae Graph Theory

Similarity:

A caterpillar is a tree with the property that the vertices of degree at least 2 induce a path. We show that for every graph G of order n, either G or G̅ has a spanning caterpillar of diameter at most 2 log n. Furthermore, we show that if G is a graph of diameter 2 (diameter 3), then G contains a spanning caterpillar of diameter at most c n 3 / 4 (at most n).

On extremal sizes of locally k -tree graphs

Mieczysław Borowiecki, Piotr Borowiecki, Elżbieta Sidorowicz, Zdzisław Skupień (2010)

Czechoslovak Mathematical Journal

Similarity:

A graph G is a if for any vertex v the subgraph induced by the neighbours of v is a k -tree, k ≥ 0 , where 0 -tree is an edgeless graph, 1 -tree is a tree. We characterize the minimum-size locally k -trees with n vertices. The minimum-size connected locally k -trees are simply ( k + 1 ) -trees. For k ≥ 1 , we construct locally k -trees which are maximal with respect to the spanning subgraph relation. Consequently, the number of edges in an n -vertex locally k -tree graph is between Ω ( n ) and O ( n 2 ) , where both bounds...

Multi-faithful spanning trees of infinite graphs

Norbert Polat (2001)

Czechoslovak Mathematical Journal

Similarity:

For an end τ and a tree T of a graph G we denote respectively by m ( τ ) and m T ( τ ) the maximum numbers of pairwise disjoint rays of G and T belonging to τ , and we define t m ( τ ) : = min { m T ( τ ) T is a spanning tree of G } . In this paper we give partial answers—affirmative and negative ones—to the general problem of determining if, for a function f mapping every end τ of G to a cardinal f ( τ ) such that t m ( τ ) ≤ f ( τ ) ≤ m ( τ ) , there exists a spanning tree T of G such that m T ( τ ) = f ( τ ) for every end τ of G .

A characterization of roman trees

Michael A. Henning (2002)

Discussiones Mathematicae Graph Theory

Similarity:

A Roman dominating function (RDF) on a graph G = (V,E) is a function f: V → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of f is w ( f ) = ∑ v ∈ V f ( v ) . The Roman domination number is the minimum weight of an RDF in G. It is known that for every graph G, the Roman domination number of G is bounded above by twice its domination number. Graphs which have Roman domination number equal to twice their domination number...