Displaying similar documents to “Graphic sequences of trees and a problem of Frobenius”

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

Distances between rooted trees

Bohdan Zelinka (1991)

Mathematica Bohemica

Similarity:

Two types of a distance between isomorphism classes of graphs are adapted for rooted trees.