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 .     

Average distance,minimum degree,and spanning trees

The average distance μ(G) of a connected graph G of order n is the average of the distances between all pairs of vertices of G, i.e., μ(G) = ()⁻¹ Σ_{x,y}⊂V(G) d_G(x, y), where V(G) denotes the vertex set of G and d_G(x, y) is the distance between x and y. We prove that every connected graph of order n and minimum degree δ has a spanning tree T with average distance at most . We give improved bounds for K₃‐free graphs, C₄‐free graphs, and for graphs of given girth. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 1–13, 2000     

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.     

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).     

A family of random trees with random edge lengths

We introduce a family of probability distributions on the space of trees with I labeled vertices and possibly extra unlabeled vertices of degree 3, whose edges have positive real lengths. Formulas for distributions of quantities such as degree sequence, shape, and total length are derived. An interpretation is given in terms of sampling from the inhomogeneous continuum random tree of Aldous and Pitman (1998). ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 176–195, 1999     

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.     

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.     

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].     

On homeomorphically irreducible spanning trees in cubic graphs

A spanning tree without a vertex of degree two is called a HIST, which is an abbreviation for homeomorphically irreducible spanning tree. We provide a necessary condition for the existence of a HIST in a cubic graph. As one consequence, we answer affirmatively an open question on HISTs by Albertson, Berman, Hutchinson, and Thomassen. We also show several results on the existence of HISTs in plane and toroidal cubic graphs.     

Constructing near spanning trees with few local inspections

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let G be a connected bounded‐degree graph. Given an edge e in G we would like to decide whether e belongs to a connected subgraph consisting of edges (for a prespecified constant ), where the decision for different edges should be consistent with the same subgraph . Can this task be performed by inspecting only a constant number of edges in G ? Our main results are:

• We show that if every t‐vertex subgraph of G has expansion then one can (deterministically) construct a sparse spanning subgraph of G using few inspections. To this end we analyze a “local” version of a famous minimum‐weight spanning tree algorithm.
• We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of 3‐regular graphs of high girth, in which every t‐vertex subgraph has expansion . We prove that for this family of graphs, any local algorithm for the sparse spanning graph problem requires inspecting a number of edges which is proportional to the girth.

© 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 183–200, 2017     

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.     

Sandpile groups and spanning trees of directed line graphs

We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph G and its directed line graph LG. The sandpile group is an abelian group associated to a directed graph, whose order is the number of oriented spanning trees rooted at a fixed vertex. In the case when G is regular of degree k, we show that the sandpile group of G is isomorphic to the quotient of the sandpile group of LG by its k-torsion subgroup. As a corollary we compute the sandpile groups of two families of graphs widely studied in computer science, the de Bruijn graphs and Kautz graphs.     

Minimal spanning trees and partial sorting

Two partial sorting algorithms used in conjunction with Kruskal's algorithm to find minimal spanning trees, are tested. The superior method can be used in the computation of the Held-Karp bound for the traveling salesman problem and other sort-based greedy algorithms.     

A tabu search heuristic for the generalized minimum spanning tree problem

This paper describes an attribute based tabu search heuristic for the generalized minimum spanning tree problem (GMSTP) known to be NP-hard. Given a graph whose vertex set is partitioned into clusters, the GMSTP consists of designing a minimum cost tree spanning all clusters. An attribute based tabu search heuristic employing new neighborhoods is proposed. An extended set of TSPLIB test instances for the GMSTP is generated and the heuristic is compared with recently proposed genetic algorithms. The proposed heuristic yields the best results for all instances. Moreover, an adaptation of the tabu search algorithm is proposed for a variation of the GMSTP in which each cluster must be spanned at least once.