Displaying similar documents to “Trees with α-labelings and decompositions of complete graphs into non-symmetric isomorphic spanning trees”

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.

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

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 .

Closure for spanning trees and distant area

Jun Fujisawa, Akira Saito, Ingo Schiermeyer (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A k-ended tree is a tree with at most k endvertices. Broersma and Tuinstra [3] have proved that for k ≥ 2 and for a pair of nonadjacent vertices u, v in a graph G of order n with d e g G u + d e g G v n - 1 , G has a spanning k-ended tree if and only if G+uv has a spanning k-ended tree. The distant area for u and v is the subgraph induced by the set of vertices that are not adjacent with u or v. We investigate the relationship between the condition on d e g G u + d e g G v and the structure of the distant area for u and v. We prove...

Signpost systems and spanning trees of graphs

Ladislav Nebeský (2006)

Czechoslovak Mathematical Journal

Similarity:

By a ternary system we mean an ordered pair ( W , R ) , where W is a finite nonempty set and R W × W × W . By a signpost system we mean a ternary system ( W , R ) satisfying the following conditions for all x , y , z W : if ( x , y , z ) R , then ( y , x , x ) R and ( y , x , z ) R ; if x y , then there exists t W such that ( x , t , y ) R . In this paper, a signpost system is used as a common description of a connected graph and a spanning tree of the graph. By a ct-pair we mean an ordered pair ( G , T ) , where G is a connected graph and T is a spanning tree of G . If ( G , T ) is a ct-pair, then by...

Pruning Galton–Watson trees and tree-valued Markov processes

Romain Abraham, Jean-François Delmas, Hui He (2012)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We present a new pruning procedure on discrete trees by adding marks on the nodes of trees. This procedure allows us to construct and study a tree-valued Markov process { 𝒢 ( u ) } by pruning Galton–Watson trees and an analogous process { 𝒢 * ( u ) } by pruning a critical or subcritical Galton–Watson tree conditioned to be infinite. Under a mild condition on offspring distributions, we show that the process { 𝒢 ( u ) } run until its ascension time has a representation in terms of { 𝒢 * ( u ) } . A similar result was obtained by...

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

On the (2,2)-domination number of trees

You Lu, Xinmin Hou, Jun-Ming Xu (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Let γ(G) and γ 2 , 2 ( G ) denote the domination number and (2,2)-domination number of a graph G, respectively. In this paper, for any nontrivial tree T, we show that ( 2 ( γ ( T ) + 1 ) ) / 3 γ 2 , 2 ( T ) 2 γ ( T ) . Moreover, we characterize all the trees achieving the equalities.