Displaying similar documents to “Generalized connected domination in graphs.”

Helly Property for Subtrees

Jessica Enright, Piotr Rudnicki (2008)

Formalized Mathematics

Similarity:

We prove, following [5, p. 92], that any family of subtrees of a finite tree satisfies the Helly property.MML identifier: HELLY, version: 7.8.09 4.97.1001

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

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.