A lower bound on the number of spanning trees with k end-vertices

If a graph G with cycle rank ρ contains both spanning trees with m and with n end-vertices, m < n, then G has at least 2ρ spanning trees with k end-vertices for each integer k, m < k < n. Moreover, the lower bound of 2ρ is best possible.     

A quadratic distance bound on sliding between crossing-free spanning trees

Let S be a set of n points in the plane and let be the set of all crossing-free spanning trees of S. We show that it is possible to transform any two trees in into each other by O(n²) local and constant-size edge slide operations. Previously no polynomial upper bound for this task was known, but in [O. Aichholzer, F. Aurenhammer, F. Hurtado, Sequences of spanning trees and a fixed tree theorem, Comput. Geom.: Theory Appl. 21 (1–2) (2002) 3–20] a bound of O(n²logn) operations was conjectured.     

Edge-disjoint spanning trees: A connectedness theorem

It is well known that any spanning tree of a graph can be obtained from any other by a sequence of single edge exchanges in a way that preserves, at each step, the property of being a spanning tree. We consider a variation of this problem concerning pairs of edge-disjoint spanning trees. In particular, it is shown that any pair of edge-disjoint spanning trees can be obtained from any other by a sequence of single edge exchanges in a way that preserves, at each step, the property of being edge-disjoint spanning trees.     

A lower bound for the distance k-domination number of trees

A subset D of vertices of a graph G = (V, E) is a distance k-dominating set for G if the distance between every vertex of V ? D and D is at most k. The minimum size of a distance k-dominating set of G is called the distance k-domination number γ_k(G) of G. In this paper we prove that (2k + 1)γ_k(T) ≥ ¦V¦ + 2k ? kn₁ for each tree T = (V, E) with n₁ leafs, and we characterize the class of trees that satisfy the equality (2k + 1)γ_k(T) = ¦V¦ + 2k ? kn₁. Our results generalize those of Lemanska [4] for k = 1 and of Cyman, Lemanska and Raczek [1] for k = 2.     

On low bound of degree sequences of spanning trees in K-edge-connected graphs

A graph G = (V, E) is k-edge-connected if for any subset E′ ⊆ E,|E′| < k, G − E′ is connected. A d_k-tree T of a connected graph G = (V, E) is a spanning tree satisfying that ∀v ∈ V, d_T(v) ≤ + α, where [·] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d_k-tree, and α = 1 for k = 2, α = 2 for k ≥ 3. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 87–95, 1998     

Minimal spanning trees

The main result is that a recursive weighted graph having a minimal spanning tree has a minimal spanning tree that is . This leads to a proof of the failure of a conjecture of Clote and Hirst (1998) concerning Reverse Mathematics and minimal spanning trees.

     

Generalized spanning trees

In this paper, we propose a definition for the Generalized Minimal Spanning Tree (GMST) of a graph. The GMST requires spanning at least one node out of every set of disjoint nodes (node partition) in a graph. The analysis of the GMST problem is motivated by real life agricultural settings related to construction of irrigation networks in desert environments. We prove that the GMST problem is NP-hard, and examine a number of heuristic solutions for this problem. Computational experiments comparing these heuristics are presented.     

Efficient spanning trees

The definition of a shortest spanning tree of a graph is generalized to that of an efficient spanning tree for graphs with vector weights, where the notion of optimality is of the Pareto type. An algorighm for obtaining all efficient spanning trees is presented.     

Chain-constrained spanning trees

Mathematical Programming - We consider the problem of finding a spanning tree satisfying a family of additional constraints. Several settings have been considered previously, the most famous being...     

Homeomorphically irreducible spanning trees

We show that if G is a graph such that every edge is in at least two triangles, then G contains a spanning tree with no vertex of degree 2 (a homeomorphically irreducible spanning tree). This result was originally asked in a question format by Albertson, Berman, Hutchinson, and Thomassen in 1979, and then conjectured to be true by Archdeacon in 2009.     

Degree-bounded minimum spanning trees

Given n points in the Euclidean plane, the degree-δ minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most δ. The problem is NP-hard for 2≤δ≤3, while the NP-hardness of the problem is open for δ=4. The problem is polynomial-time solvable when δ=5. By presenting an improved approximation analysis for Chan’s degree-4 MST algorithm [T. Chan, Euclidean bounded-degree spanning tree ratios, Discrete & Computational Geometry 32 (2004) 177-194], we show that, for any arbitrary collection of points in the Euclidean plane, there always exists a degree-4 spanning tree of weight at most times the weight of an MST.     

Low-degree minimum spanning trees

Motivated by practical VLSI routing applications, we study the maximum vertex degree of a minimum spanning tree (MST). We prove that, under theL _p norm, the maximum vertex degree over all MSTs is equal to the Hadwiger number of the corresponding unit ball; we show an even tighter bound for MSTs where the maximum degree is minimized. We give the best-known bounds for the maximum MST degree for arbitraryL _p metrics in all dimensions, with a focus on the rectilinear metric in two and three dimensions. We show that for any finite set of points in the rectilinear plane an MST exists with maximum degree of at most 4, and for three-dimensional rectilinear space the maximum possible degree of a minimum-degree MST is either 13 or 14. Gabriel Robins was partially supported by NSF Young Investigator Award MIP-9457412. Jeffrey Salowe was partially supported by NSF Grants MIP-9107717 and CCR-9224789.     

A sharp lower bound on Steiner Wiener index for trees with given diameter

Let $G$ be a connected graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. For a subset $S$ of $V\left(G\right)$, the Steiner distance$d\left(S\right)$ of $S$ is the minimum size of a connected subgraph whose vertex set contains $S$. For an integer $k$ with $2\le k\le n?1$, the Steiner$k$-Wiener index${\text{SW}}_k\left(G\right)$ is ${\sum }_{S?V\left(G\right),\left|S\right|=k}d\left(S\right)$. In this paper, we introduce some transformations for trees that do not increase their Steiner $k$-Wiener index for $2\le k\le n?1$. Using these transformations, we get a sharp lower bound on Steiner $k$-Wiener index for trees with given diameter, and obtain the corresponding extremal graph as well.     

A note on graphs with diameter-preserving spanning trees

The distance between a pair of vertices u, v in a graph G is the length of a shortest path joining u and v. The diameter diam(G) of G is the maximum distance between all pairs of vertices in G. A spanning tree T of G is diameter preserving if diam(T) = diam(G). In this note, we characterize graphs that have diameter-preserving spanning trees.     

A parallel algorithm for constructing minimum spanning trees

The construction of minimum spanning trees (MSTs) of weighted graphs is a problem that arises in many applications. In this paper we will study a new parallel algorithm that constructs an MST of an N-node graph in time proportional to N lg N, on an $\text{N}\text{(}\text{lg}\text{N)-}\text{processor}$ computing system. The primary theoretical contribution of this paper is the new algorithm, which is an improvement over Sollin's parallel MST algorithm in several ways. On a more practical level, this algorithm is appropriate for implementation in VLSI technology.     

A solution of Chartrand's problem on spanning trees

It is proved that if a connected graphG contains two distinct spanning trees, then any two spanning trees ofG can be connected by a chain of spanning trees, in which any two consecutive treesT ₁ andT _i+1 are adjacent, i.e., the symmetric differenceE(T _i )E(T _i+1 ) consists of two adjacent edges.     

A matrix lower bound

Four essentially different interpretations of a lower bound for linear operators are shown to be equivalent for matrices (involving inequalities, convex sets, minimax problems, and quotient spaces). Properties stated by von Neumann in a restricted case are satisfied by the lower bound. Applications are made to rank reduction, s-numbers, condition numbers, and pseudospectra. In particular, the matrix lower bound is the distance to the nearest matrix with strictly contained row or column spaces, and it occurs in a condition number formula for any consistent system of linear equations, including those that are underdetermined.