Displaying similar documents to “On extremal sizes of locally k -tree 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

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

Cyclic decompositions of complete graphs into spanning trees

Dalibor Froncek (2004)

Discussiones Mathematicae Graph Theory

Similarity:

We examine decompositions of complete graphs with an even number of vertices, K 2 n , into n isomorphic spanning trees. While methods of such decompositions into symmetric trees have been known, we develop here a more general method based on a new type of vertex labelling, called flexible q-labelling. This labelling is a generalization of labellings introduced by Rosa and Eldergill.

Minimum degree, leaf number and traceability

Simon Mukwembi (2013)

Czechoslovak Mathematical Journal

Similarity:

Let G be a finite connected graph with minimum degree δ . The leaf number L ( G ) of G is defined as the maximum number of leaf vertices contained in a spanning tree of G . We prove that if δ ≥ 1 2 ( L ( G ) + 1 ) , then G is 2-connected. Further, we deduce, for graphs of girth greater than 4, that if δ ≥ 1 2 ( L ( G ) + 1 ) , then G contains a spanning path. This provides a partial solution to a conjecture of the computer program Graffiti.pc [DeLaVi na and Waller, Spanning trees with many leaves and average distance, Electron. J. Combin....

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 .

The 3-path-step operator on trees and unicyclic graphs

Bohdan Zelinka (2002)

Mathematica Bohemica

Similarity:

E. Prisner in his book Graph Dynamics defines the k -path-step operator on the class of finite graphs. The k -path-step operator (for a positive integer k ) is the operator S k ' which to every finite graph G assigns the graph S k ' ( G ) which has the same vertex set as G and in which two vertices are adjacent if and only if there exists a path of length k in G connecting them. In the paper the trees and the unicyclic graphs fixed in the operator S 3 ' are studied.