Partitionability of trees
Bohdan Zelinka (1988)
Czechoslovak Mathematical Journal
Similarity:
Bohdan Zelinka (1988)
Czechoslovak Mathematical Journal
Similarity:
František Neuman (1964)
Časopis pro pěstování matematiky
Similarity:
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...
Katarzyna Jesse-Józefczyk (2012)
Open Mathematics
Similarity:
Let G = (V, E) be a graph. A global secure set SD ⊆ V is a dominating set which satisfies the condition: for all X ⊆ SD, |N[X] ∩ SD| ≥ | N[X] − SD|. A global defensive alliance is a set of vertices A that is dominating and satisfies a weakened condition: for all x ∈ A, |N[x] ∩ A| ≥ |N[x] − A|. We give an upper bound on the cardinality of minimum global secure sets in cactus trees. We also present some results for trees, and we relate them to the known bounds on the minimum cardinality...
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...
Bohdan Zelinka (1991)
Mathematica Bohemica
Similarity:
Two types of a distance between isomorphism classes of graphs are adapted for rooted trees.
Teresa W. Haynes, Michael A. Henning (2002)
Discussiones Mathematicae Graph Theory
Similarity:
A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. We provide three equivalent conditions for a tree to have a unique minimum total dominating set and give a constructive characterization of such trees.