Displaying similar documents to “Bounds on global secure sets in cactus trees”

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.

Minimum vertex ranking spanning tree problem for chordal and proper interval graphs

Dariusz Dereniowski (2009)

Discussiones Mathematicae Graph Theory

Similarity:

A vertex k-ranking of a simple graph is a coloring of its vertices with k colors in such a way that each path connecting two vertices of the same color contains a vertex with a bigger color. Consider the minimum vertex ranking spanning tree (MVRST) problem where the goal is to find a spanning tree of a given graph G which has a vertex ranking using the minimal number of colors over vertex rankings of all spanning trees of G. K. Miyata et al. proved in [NP-hardness proof and an approximation...