A greedy algorithm for finding maximum spanning trees in infinite graphs

In finite graphs, greedy algorithms are used to find minimum spanning trees (MinST) and maximum spanning trees (MaxST). In infinite graphs, we illustrate a general class of problems where a greedy approach discovers a MaxST while a MinST may be unreachable. Our algorithm is a natural extension of Prim's to infinite graphs with summable and strictly positive edge weights, producing a sequence of finite trees that converge to a MaxST.     

A simple bijection between a subclass of 2-binary trees and ternary trees

A bijection between binary trees, with nodes labelled black or white, and a black node never having a white right child, and ternary trees is given. It is simpler than another bijection that has recently appeared in this journal.     

Counting trees using symmetries

We prove a new formula for the generating function of multitype Cayley trees counted according to their degree distribution. Using this formula we recover and extend several enumerative results about trees. In particular, we extend some results by Knuth and by Bousquet-Mélou and Chapuy about embedded trees. We also give a new proof of the multivariate Lagrange inversion formula. Our strategy for counting trees is to exploit symmetries of refined enumeration formulas: proving these symmetries is easy, and once the symmetries are proved the formulas follow effortlessly. We also adapt this strategy to recover an enumeration formula of Goulden and Jackson for cacti counted according to their degree distribution.     

Strong clique trees,neighborhood trees,and strongly chordal graphs

Maximal complete subgraphs and clique trees are basic to both the theory and applications of chordal graphs. A simple notion of strong clique tree extends this structure to strongly chordal graphs. Replacing maximal complete subgraphs with open or closed vertex neighborhoods discloses new relationships between chordal and strongly chordal graphs and the previously studied families of chordal bipartite graphs, clique graphs of chordal graphs (dually chordal graphs), and incidence graphs of biacyclic hypergraphs. © 2000 John Wiley & Sons, Inc. J. Graph Theory 33: 151–160, 2000     

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.

     

On the irregularity strength of trees

For any graph G, let n_i be the number of vertices of degree i, and . This is a general lower bound on the irregularity strength of graph G. All known facts suggest that for connected graphs, this is the actual irregularity strength up to an additive constant. In fact, this was conjectured to be the truth for regular graphs and for trees. Here we find an infinite sequence of trees with λ(T) = n₁ but strength converging to . © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 241–254, 2004     

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.     

On the shape of the fringe of various types of random trees

We analyze a fringe tree parameter w in a variety of settings, utilizing a variety of methods from the analysis of algorithms and data structures. Given a tree t and one of its leaves a, the w(t, a) parameter denotes the number of internal nodes in the subtree rooted at a's father. The closely related w?(t, a) parameter denotes the number of leaves, excluding a, in the subtree rooted at a's father. We define the cumulative w parameter as W(t) = Σ_aw(t, a), i.e. as the sum of w(t, a) over all leaves a of t. The w parameter not only plays an important rôle in the analysis of the Lempel–Ziv '77 data compression algorithm, but it is captivating from a combinatorial viewpoint too. In this report, we determine the asymptotic behavior of the w and W parameters on a variety of types of trees. In particular, we analyze simply generated trees, recursive trees, binary search trees, digital search trees, tries and Patricia tries. The final section of this report briefly summarizes and improves the previously known results about the w? parameter's behavior on tries and suffix trees, originally published in one author's thesis (see Analysis of the multiplicity matching parameter in suffix trees. Ph.D. Thesis, Purdue University, West Lafayette, IN, U.S.A., May 2005; Discrete Math. Theoret. Comput. Sci. 2005; AD :307–322; IEEE Trans. Inform. Theory 2007; 53 :1799–1813). This survey of new results about the w parameter is very instructive since a variety of different combinatorial methods are used in tandem to carry out the analysis. Copyright © 2008 John Wiley & Sons, Ltd.     

The height of depth‐weighted random recursive trees

In this paper, we introduce a model of depth‐weighted random recursive trees, created by recursively joining a new leaf to an existing vertex . In this model, the probability of choosing depends on its depth in the tree. In particular, we assume that there is a function such that if has depth then its probability of being chosen is proportional to . We consider the expected value of the diameter of this model as determined by , and for various increasing we find expectations that range from polylogarithmic to linear.     

A distance approximating trees

A 1-approximation of connected graph G=(V,E) is a tree T=(V,E^′) with the same vertex set such that for every two vertices |d_G(u,v)−d_T(u,v)|1. A polynomial time algorithm is designed for finding such a tree.     

Unavoidable trees in tournaments

An oriented tree T on n vertices is unavoidable if every tournament on n vertices contains a copy of T. In this paper, we give a sufficient condition for T to be unavoidable, and use this to prove that almost all labeled oriented trees are unavoidable, verifying a conjecture of Bender and Wormald. We additionally prove that every tournament on vertices contains a copy of every oriented tree T on n vertices with polylogarithmic maximum degree, improving a result of Kühn, Mycroft, and Osthus.     

Walks and paths in trees

Recently Csikvári [Combinatorica 30(2) 2010, 125–137] proved a conjecture of Nikiforov concerning the number of closed walks on trees. Our aim is to extend this theorem to all walks. In addition, we give a simpler proof of Csikvári's result and answer one of his questions in the negative. Finally we consider an analogous question for paths rather than walks. © 2011 Wiley Periodicals, Inc. J Graph Theory     

SOLUTION OF A RESEARCH PROBLEM ON TREES OF SUBSETS

ＳＯＬＵＴＩＯＮＯＦＡＲＥＳＥＡＲＣＨＰＲＯＢＬＥＭＯＮＴＲＥＥＳＯＦＳＵＢＳＥＴＳ ＷＵＳＨＩＱＵＡＮＡｂｓｔｒａｃｔ：Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｓｏｌｖｅａｒｅｓｅａｒｃｈｐｒｏｂｌｅｍｏｎｔｒｅｅｓｏｆｓｕｂｓｅｔｓｐｏｓｅｄｂｙＦ．Ｒ．Ｍｃ?..     

Ordered partitions and drawings of rooted plane trees

We study the bounded regions in a generic slice of the hyperplane arrangement in Rⁿ${\mathbb{R}}^n$ consisting of the hyperplanes defined by _xi$x_i$ and _xi+_xj$x_i+x_j$. The bounded regions are in bijection with several classes of combinatorial objects, including the ordered partitions of [n]$\left[n\right]$ all of whose left-to-right minima occur at odd locations and the drawings of rooted plane trees with n+1$n+1$ vertices. These are sequences of rooted plane trees such that each tree in a sequence can be obtained from the next one by removing a leaf.     

Wiener indices of balanced binary trees

We study a new family of trees for computation of the Wiener indices. We introduce general tree transformations and derive formulas for computing the Wiener indices when a tree is modified. We present several algorithms to explore the Wiener indices of our family of trees. The experiments support new conjectures about the Wiener indices.     

Spanning trees without adjacent vertices of degree 2

Albertson, Berman, Hutchinson, and Thomassen showed in 1990 that there exist highly connected graphs in which every spanning tree contains vertices of degree 2. Using a result of Alon and Wormald, we show that there exists a natural number $d$ such that every graph of minimum degree at least $d$ contains a spanning tree without adjacent vertices of degree 2. Moreover, we prove that every graph with minimum degree at least 3 has a spanning tree without three consecutive vertices of degree 2.