Displaying similar documents to “Spanning trees with leaves bounded by independence number.”

On a Spanning k-Tree in which Specified Vertices Have Degree Less Than k

Hajime Matsumura (2015)

Discussiones Mathematicae Graph Theory

Similarity:

A k-tree is a tree with maximum degree at most k. In this paper, we give a degree sum condition for a graph to have a spanning k-tree in which specified vertices have degree less than k. We denote by σk(G) the minimum value of the degree sum of k independent vertices in a graph G. Let k ≥ 3 and s ≥ 0 be integers, and suppose G is a connected graph and σk(G) ≥ |V (G)|+s−1. Then for any s specified vertices, G contains a spanning k-tree in which every specified vertex has degree less than...

Spanning tree congestion of rook's graphs

Kyohei Kozawa, Yota Otachi (2011)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a connected graph and T be a spanning tree of G. For e ∈ E(T), the congestion of e is the number of edges in G joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Kₘ ☐ Kₙ for any m and n.

Codings and operators in two genetic algorithms for the leaf-constrained minimum spanning tree problem

Bryant Julstrom (2004)

International Journal of Applied Mathematics and Computer Science

Similarity:

The features of an evolutionary algorithm that most determine its performance are the coding by which its chromosomes represent candidate solutions to its target problem and the operators that act on that coding. Also, when a problem involves constraints, a coding that represents only valid solutions and operators that preserve that validity represent a smaller search space and result in a more effective search. Two genetic algorithms for the leaf-constrained minimum spanning tree problem...

Spanning Trees whose Stems have a Bounded Number of Branch Vertices

Zheng Yan (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let T be a tree, a vertex of degree one and a vertex of degree at least three is called a leaf and a branch vertex, respectively. The set of leaves of T is denoted by Leaf(T). The subtree T − Leaf(T) of T is called the stem of T and denoted by Stem(T). In this paper, we give two sufficient conditions for a connected graph to have a spanning tree whose stem has a bounded number of branch vertices, and these conditions are best possible.

Completely Independent Spanning Trees in (Partial) k-Trees

Masayoshi Matsushita, Yota Otachi, Toru Araki (2015)

Discussiones Mathematicae Graph Theory

Similarity:

Two spanning trees T1 and T2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T1 and T2 are internally disjoint. For a graph G, we denote the maximum number of pairwise completely independent spanning trees by cist(G). In this paper, we consider cist(G) when G is a partial k-tree. First we show that [k/2] ≤ cist(G) ≤ k − 1 for any k-tree G. Then we show that for any p ∈ {[k/2], . . . , k − 1}, there exist infinitely many k-trees G such...

A lower bound for the irredundance number of trees

Michael Poschen, Lutz Volkmann (2006)

Discussiones Mathematicae Graph Theory

Similarity:

Let ir(G) and γ(G) be the irredundance number and domination number of a graph G, respectively. The number of vertices and leaves of a graph G are denoted by n(G) and n₁(G). If T is a tree, then Lemańska [4] presented in 2004 the sharp lower bound γ(T) ≥ (n(T) + 2 - n₁(T))/3. In this paper we prove ir(T) ≥ (n(T) + 2 - n₁(T))/3. for an arbitrary tree T. Since γ(T) ≥ ir(T) is always valid, this inequality is an extension and improvement of...

The triangles method to build X -trees from incomplete distance matrices

Alain Guénoche, Bruno Leclerc (2001)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

A method to infer X -trees (valued trees having X as set of leaves) from incomplete distance arrays (where some entries are uncertain or unknown) is described. It allows us to build an unrooted tree using only 2 n -3 distance values between the n elements of X , if they fulfill some explicit conditions. This construction is based on the mapping between X -tree and a weighted generalized 2-tree spanning X .