Mean distance and minimum degree

We prove that in a graph of order n and minimum degree d, the mean distance μ must satisfy . This asymptotically confirms, and improves, a conjecture of the computer program GRAFFITI. The result is close to optimal; examples show that for any d, μ may be larger than n/(d + 1). © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 95–99, 1997     

Average degree and contractibility

It is proved that for every number k there exists a number f(k) such that every finite k‐connected graph of average degree exceeding f(k) contains an edge whose contraction yields again a k‐connected graph. For the proof, tree orders on certain sets of smallest separating sets of the graph in question are constructed. This leads to new canonical tree decompositions as well. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Maximizing the minimum voter satisfaction on spanning trees

This paper analyzes the computational complexity involved in solving fairness issues on graphs, e.g., in the installation of networks such as water networks or oil pipelines. Based on individual rankings of the edges of a graph, we will show under which conditions solutions, i.e., spanning trees, can be determined efficiently given the goal of maximin voter satisfaction. In particular, we show that computing spanning trees for maximin voter satisfaction under voting rules such as approval voting or the Borda count is -complete for a variable number of voters whereas it remains polynomially solvable for a constant number of voters.     

Minimum congestion spanning trees in bipartite and random graphs

The first problem considered in this article reads: is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs? It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n 3 2 , where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n 3 2 .     

Maintaining dynamic minimum spanning trees: An experimental study

We report our findings on an extensive empirical study on the performance of several algorithms for maintaining minimum spanning trees in dynamic graphs. In particular, we have implemented and tested several variants of the polylogarithmic algorithm by Holm et al., sparsification on top of Frederickson’s algorithm, and other (less sophisticated) dynamic algorithms. In our experiments, we considered as test sets several random, semi-random and worst-case inputs previously considered in the literature together with inputs arising from real-world applications (e.g., a graph of the Internet Autonomous Systems).     

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.     

Spanning trees with leaf distance at least four

For a graph G, we denote by i(G) the number of isolated vertices of G. We prove that for a connected graph G of order at least five, if i(G–S) < |S| for all ?? ≠ S ? V(G), then G has a spanning tree T such that the distance in T between any two leaves of T is at least four. This result was conjectured by Kaneko in “Spanning trees with constrains on the leaf degree”, Discrete Applied Math, 115 (2001), 73–76. Moreover, the condition in the result is sharp in a sense that the condition i(G–S) < |S| cannot be replaced by i(G–S) ≤ |S|. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 83–90, 2007     

On the number of rainbow spanning trees in edge-colored complete graphs

A spanning tree of a properly edge-colored complete graph, $K_n$, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if $K_{2m}$ is properly $(2m?1)$-edge-colored, then the edges of $K_{2m}$ can be partitioned into $m$ rainbow spanning trees except when $m=2$. By means of an explicit, constructive approach, in this paper we construct $?\sqrt{6m+9}∕3?$ mutually edge-disjoint rainbow spanning trees for any positive value of $m$. Not only are the rainbow trees produced, but also some structure of each rainbow spanning tree is determined in the process. This improves upon best constructive result to date in the literature which produces exactly three rainbow trees.     

On spanning trees and walks of low maximum degree

This article uses the discharging method to obtain the best possible results that a 3‐connected graph embeddable on a surface of Euler characteristic χ ≤ −46 has a spanning tree of maximum degree at most and a closed, spanning walk meetting each vertex at most times. Each of these results is shown to be best possible. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 67–74, 2001     

Unicyclic and bicyclic graphs having minimum degree distance

In this paper characterizations of connected unicyclic and bicyclic graphs in terms of the degree sequence, as well as the graphs in these classes minimal with respect to the degree distance are given.     

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     

Undirected simple connected graphs with minimum number of spanning trees

We show that for positive integers n, m with n(n−1)/2≥m≥n−1, the graph L_n,m having n vertices and m edges that consists of an (n−k)-clique and k−1 vertices of degree 1 has the fewest spanning trees among all connected graphs on n vertices and m edges. This proves Boesch’s conjecture [F.T. Boesch, A. Satyanarayana, C.L. Suffel, Least reliable networks and reliability domination, IEEE Trans. Commun. 38 (1990) 2004-2009].     

Counting degree sequences of spanning trees in bipartite graphs: A graph-theoretic proof

Given a bipartite graph with bipartition each spanning tree in has a degree sequence on and one on . Löhne and Rudloff showed that the number of possible degree sequences on equals the number of possible degree sequences on . Their proof uses a non-trivial characterization of degree sequences by -draconian sequences based on polyhedral results of Postnikov. In this paper, we give a purely graph-theoretic proof of their result.     

Degree sum conditions for the existence of homeomorphically irreducible spanning trees

In 1990, Albertson, Berman, Hutchinson, and Thomassen proved a theorem which gives a minimum degree condition for the existence of a spanning tree with no vertices of degree 2. Such a spanning tree is called a homeomorphically irreducible spanning tree (HIST). In this paper, we prove that every graph of order $n$ ($n\ge 8$) contains a HIST if $d(u)+d(v)\ge n?1$ for any nonadjacent vertices $u$ and $v$. The degree sum condition is best possible.     

Average Distance,Independence Number,and Spanning Trees

Let G be a connected graph of order n and independence number α. We prove that G has a spanning tree with average distance at most , if , and at most , if . As a corollary, we obtain, for n sufficiently large, an asymptotically sharp upper bound on the average distance of G in terms of its independence number. This bound, apart from confirming and improving on a conjecture of Graffiti [8], is a strengthening of a theorem of Chung [1], and that of Fajtlowicz and Waller [8], on average distance and independence number of a graph.