Displaying similar documents to “Functions on adjacent vertex degrees of trees with given degree sequence”

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

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

Characterization Results for theL(2, 1, 1)-Labeling Problem on Trees

Xiaoling Zhang, Kecai Deng (2017)

Discussiones Mathematicae Graph Theory

Similarity:

An L(2, 1, 1)-labeling of a graph G is an assignment of non-negative integers (labels) to the vertices of G such that adjacent vertices receive labels with difference at least 2, and vertices at distance 2 or 3 receive distinct labels. The span of such a labelling is the difference between the maximum and minimum labels used, and the minimum span over all L(2, 1, 1)-labelings of G is called the L(2, 1, 1)-labeling number of G, denoted by λ2,1,1(G). It was shown by King, Ras and Zhou...

From paths to stars.

Alameddine, A.F. (1991)

International Journal of Mathematics and Mathematical Sciences

Similarity:

Graphic sequences of trees and a problem of Frobenius

Gautam Gupta, Puneet Joshi, Amitabha Tripathi (2007)

Czechoslovak Mathematical Journal

Similarity:

We give a necessary and sufficient condition for the existence of a tree of order n with a given degree set. We relate this to a well-known linear Diophantine problem of Frobenius.

Small integral trees.

Brouwer, A.E. (2008)

The Electronic Journal of Combinatorics [electronic only]

Similarity: