All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 2 Next

Displaying 21 – 40 of 54

Showing per page

Spanning caterpillars with bounded diameter

Ralph Faudree, Ronald Gould, Michael Jacobson, Linda Lesniak (1995)

Discussiones Mathematicae Graph Theory

A caterpillar is a tree with the property that the vertices of degree at least 2 induce a path. We show that for every graph G of order n, either G or G̅ has a spanning caterpillar of diameter at most 2 log n. Furthermore, we show that if G is a graph of diameter 2 (diameter 3), then G contains a spanning caterpillar of diameter at most c n 3 / 4 (at most n).

Spanning tree congestion of rook's graphs

Kyohei Kozawa, Yota Otachi (2011)

Discussiones Mathematicae Graph Theory

Let G be a connected graph and T be a spanning tree of G. For e ∈ E(T), the congestion of e is the number of edges in G joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Kₘ ☐ Kₙ for any m and n.

Spanning trees of bounded degree.

Czygrinow, Andrzej, Fan, Genghua, Hurlbert, Glenn, Kierstead, H.A., Trotter, William T. (2001)

The Electronic Journal of Combinatorics [electronic only]

Spanning trees whose reducible stems have a few branch vertices

Pham Hoang Ha, Dang Dinh Hanh, Nguyen Thanh Loan, Ngoc Diep Pham (2021)

Czechoslovak Mathematical Journal

Let T be a tree. Then a vertex of T with degree one is a leaf of T and a vertex of degree at least three is a branch vertex of T . The set of leaves of T is denoted by L ( T ) and the set of branch vertices of T is denoted by B ( T ) . For two distinct vertices u , v of T , let P T [ u , v ] denote the unique path in T connecting u and v . Let T be a tree with B ( T ) ≠ ∅ . For each leaf x of T , let y x denote the nearest branch vertex to x . We delete V ( P T [ x , y x ] ) ∖ { y x } from T for all x ∈ L ( T ) . The resulting subtree of T is called the reducible stem of T and denoted...

Spanning Trees whose Stems have a Bounded Number of Branch Vertices

Zheng Yan (2016)

Discussiones Mathematicae Graph Theory

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.

Spanning trees with many or few colors in edge-colored graphs

Hajo Broersma, Xueliang Li (1997)

Discussiones Mathematicae Graph Theory

Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.

Statuses and branch-weights of weighted trees

Chiang Lin, Jen-Ling Shang (2009)

Czechoslovak Mathematical Journal

In this paper we show that in a tree with vertex weights the vertices with the second smallest status and those with the second smallest branch-weight are the same.

Currently displaying 21 – 40 of 54