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 (at most n).
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.
Let be a tree. Then a vertex of with degree one is a leaf of and a vertex of degree at least three is a branch vertex of . The set of leaves of is denoted by and the set of branch vertices of is denoted by . For two distinct vertices , of , let denote the unique path in connecting and Let be a tree with . For each leaf of , let denote the nearest branch vertex to . We delete from for all . The resulting subtree of is called the reducible stem of and denoted...
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.
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.
Graph algebras establish a connection between directed graphs without multiple edges and special universal algebras of type (2,0). We say that a graph G satisfies a term equation s ≈ t if the corresponding graph algebra satisfies s ≈ t. A class of graph algebras V is called a graph variety if where Σ is a subset of T(X) × T(X). A graph variety is called a biregular leftmost graph variety if Σ’ is a set of biregular leftmost term equations. A term equation s ≈ t is called an identity in a variety...