Invariant subsets of scattered trees and the tree alternative property of Bonato and Tardif

A tree is scattered if it does not contain a subdivision of the complete binary tree as a subtree. We show that every scattered tree contains a vertex, an edge, or a set of at most two ends preserved by every embedding of T. This extends results of Halin, Polat and Sabidussi. Calling two trees equimorphic if each embeds in the other, we then prove that either every tree that is equimorphic to a scattered tree T is isomorphic to T, or there are infinitely many pairwise non-isomorphic trees which are equimorphic to T. This proves the tree alternative conjecture of Bonato and Tardif for scattered trees, and a conjecture of Tyomkyn for locally finite scattered trees.     

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.     

Convex labelings of trees

A convex labeling of a tree T of order n is a one-to-one function f from the vertex set of T into the nonnegative integers, so that f(y) ? (f(x) + f(z))/2 for every path x, y, z of length 2 in T. If, in addition, f(v) ? n ? 1 for every vertex v of T, then f is a perfect convex labeling and T is called a perfectly convex tree. Jamison introduced this concept and conjectured that every tree is perfectly convex. We show that there exists an infinite class of trees, none of which is perfectly convex, and in fact prove that for every n there exists a tree of order n which requires a convex labeling with maximum value at least 6n/5 – 22. We also prove that every tree of order n admits a convex labeling with maximum label no more than n²/8 + 2. In addition, we present some constructive methods for obtaining perfect convex labelings of large classes of trees.     

Graphs that admit square 1-factorizations are hamiltonian Cayley graphs

A square 1-factorization of a graph is a 1-factorization in which the union of any two distinct 1-factors is a disjoint union of 4-cycles. We show that a graph admits a square 1-factorization if and only if it is a Cayley graph with group (₂) ⁿ for somen. The rest of the title follows since Cayley graphs of abelian groups are known to be hamiltonian.     

Maximally Symmetric Trees

We characterize the best model geometries for the class of virtually free groups, and we show that there is a countable infinity of distinct best model geometries in an appropriate sense – these are the maximally symmetric trees. The first theorem gives several equivalent conditions on a bounded valence, cocompact tree T without valence 1 vertices saying that T is maximally symmetric. The second theorem gives general constructions for maximally symmetric trees, showing for instance that every virtually free group has a maximally symmetric tree for a model geometry.     

Chromatic number and subtrees of graphs

Let G and H be two graphs. We say that G induces H if G has an induced subgraph isomorphic to H: A. Gyárfás and D. Sumner, independently, conjectured that, for every tree T. there exists a function f _T ; called binding function, depending only on T with the property that every graph G with chromatic number f _T (ω(G)) induces T. A. Gyárfás, E. Szemerédi and Z. Tuza confirmed the conjecture for all trees of radius two on triangle-free graphs, and H. Kierstead and S. Penrice generalized the approach and the conclusion of A. Gyárfás et al. onto general graphs. A. Scott proved an interesting topological version of this conjecture asserting that for every integer k and every tree T of radius r, every graph G with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(14 ^r-1(r - 1)!) times. We extend the approach of A. Gyárfás and present a binding function for trees obtained by identifying one end of a path and the center of a star. We also improve A. Scott's upper bound by modifying his subtree structure and partition technique, and show that for every integer k and every tree T of radius r, every graph with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(6 ^r?2) times.     

From Isomorphic Rooted Trees to Isometric Ultrametric Spaces

For every finite ultrametric space X we can put in correspondence its representing tree T_X. We found conditions under which the isomorphism of representing trees T_X and T_Y implies the isometricity of ultrametric spaces X and Y having the same range of distances.     

On the domination of the products of graphs II: Trees

For a graph G, a subset of vertices D is a dominating set if for each vertex X not in D, X is adjacent to at least one vertex of D. The domination number, γ(G), is the order of the smallest such set. An outstanding conjecture in the theory of domination is for any two graph G and H, One result presented in this paper settles this question in the case when at least one of G or H is a tree. We show that for all graphs G and any tree T. Furthermore, we supply a partial characterization for which pairs of trees, T₁ and T₂, strict inequality occurs. We show for almost all pairs of trees.     

The distribution of the size of the ancestor‐tree and of the induced spanning subtree for random trees

We consider two tree statistics that extend in a natural way the parameters depth of a node resp. distance between two nodes. The ancestor‐tree of p given nodes in a rooted tree T is the subtree of T, spanned by the root and these p nodes and generalizes the depth (ancestor‐tree of a single node), whereas the spanning subtree induced by p given nodes in a tree T generalizes the distance (induced spanning subtree of two nodes). We study the random variables size of the ancestor‐tree resp. spanning subtree size for two tree families, the simply generated trees and the recursive trees. We will assume here the random tree model and also that all () possibilities of selecting p nodes in a tree of size n are equally likely. For random simply generated trees we can then characterize for a fixed number p of chosen nodes the limiting distribution of both parameters as generalized Gamma distributions, where we prove the convergence of the moments too. For some specific simply generated tree families we can give exact formulæ for the first moments. In the instance of random recursive trees, we will show that the considered parameters are asymptotically normally distributed, where we can give also exact formulæ for the expectation and the variance. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

SEFE without Mapping via Large Induced Outerplane Graphs in Plane Graphs

We show that every n‐vertex planar graph admits a simultaneous embedding without mapping and with fixed edges with any ‐vertex planar graph. In order to achieve this result, we prove that every n‐vertex plane graph has an induced outerplane subgraph containing at least vertices. Also, we show that every n‐vertex planar graph and every n‐vertex planar partial 3‐tree admit a simultaneous embedding without mapping and with fixed edges.     

Embeddings and Other Mappings of Rooted Trees Into Complete Trees

Let T ⁿ be the complete binary tree of height n, with root 1 _n as the maximum element. For T a tree, define and . We disprove a conjecture of Kubicki, Lehel and Morayne, which claims that for any fixed n and arbitrary rooted trees T ₁ T ₂. We show that A(n; T) is of the form where l is the number of leaves of T, and each q _j is a polynomial. We provide an algorithm for calculating the two leading terms of q _l for any tree T. We investigate the asymptotic behaviour of the ratio A(n; T)/C(n; T) and give examples of classes of pairs of trees T ₁, T ₂ where it is possible to compare A(n; T ₁)/C(n; T ₁) and A(n; T ₂)/C(n; T ₂). By calculating these ratios for a particular class of pairs of trees, we show that the conjecture fails for these trees, for all sufficiently large n. Kubicki, Lehel and Morayne have proved the conjecture when T ₁, T ₂ are restricted to being binary trees. We also look at embeddings into other complete trees, and we show how the result can be viewed as one of many possible correlation inequalities for embeddings of binary trees. We also show that if we consider strict order-preserving maps of T ₁, T ₂ into T ⁿ (rather than embeddings) then the corresponding correlation inequalities for these maps also generalise to arbitrary trees.     

On the eigenvalues and spectral radius of starlike trees

Let \(k\ge 1\) and \(n_1,\ldots ,n_k\ge 1\) be some integers. Let \(S(n_1,\ldots ,n_k)\) be a tree T such that T has a vertex v of degree k and \(T{\setminus } v\) is the disjoint union of the paths \(P_{n_1},\ldots ,P_{n_k}\), that is \(T{\setminus } v\cong P_{n_1}\cup \cdots \cup P_{n_k}\) so that every neighbor of v in T has degree one or two. The tree \(S(n_1,\ldots ,n_k)\) is called starlike tree, a tree with exactly one vertex of degree greater than two, if \(k\ge 3\). In this paper we obtain the eigenvalues of starlike trees. We find some bounds for the largest eigenvalue (for the spectral radius) of starlike trees. In particular we prove that if \(k\ge 4\) and \(n_1,\ldots ,n_k\ge 2\), then \(\frac{k-1}{\sqrt{k-2}}<\lambda _1(S(n_1,\ldots ,n_k))<\frac{k}{\sqrt{k-1}}\), where \(\lambda _1(T)\) is the largest eigenvalue of T. Finally we characterize all starlike trees that all of whose eigenvalues are in the interval \((-2,2)\).     

On tree factorizations of Kn

In this paper we exhibit a class of trees with the property that if T_k is a tree on k vertices that belongs to this class, then necessary and sufficient conditions for K_n to have a T_k-factorization are simply n = 0 (mod k) and n = 1 (mod 2(k - 1)). (This class is large and in particular contains all caterpillars with an odd number of vertices.) As a corollary we obtain necessary and sufficient conditions for the existence of a K_1,k-1-factorization of K_n, which previously had only been known to be asymptotically sufficient. © 1993 John Wiley & Sons, Inc.     

On a conjecture of Graham and Häggkvist with the polynomial method

A conjecture of Graham and Häggkvist states that every tree with m edges decomposes every 2m-regular graph and every bipartite m-regular graph. Let T be a tree with a prime number p of edges. We show that if the growth ratio of T at some vertex v₀ satisfies ρ(T,v₀)≥^1/2, where is the golden ratio, then T decomposes K_2p,2p. We also prove that if T has at least p/3 leaves then it decomposes K_2p,2p. This improves previous results by Häggkvist and by Lladó and López. The results follow from an application of Alon’s Combinatorial Nullstellensatz to obtain bigraceful labelings.     

Measurable events indexed by products of trees

A tree T is said to be homogeneous if it is uniquely rooted and there exists an integer b ≥ 2, called the branching number of T, such that every t ∈ T has exactly b immediate successors. A vector homogeneous tree T is a finite sequence (T ₁,...,T _d ) of homogeneous trees and its level product ?T is the subset of the Cartesian product T ₁×...×T _d consisting of all finite sequences (t ₁,...,t _d ) of nodes having common length. We study the behavior of measurable events in probability spaces indexed by the level product ?T of a vector homogeneous tree T. We show that, by refining the index set to the level product ?S of a vector strong subtree S of T, such families of events become highly correlated. An analogue of Lebesgue’s density Theorem is also established which can be considered as the “probabilistic” version of the density Halpern-Läuchli Theorem.     

On trees and tree dimension of ordered sets

We call an ordered set (X, ) a tree if no pair of incomparable elements ofX has an upper bound. It is shown that there is a natural way to associate a tree (T, ) with any ordered set (X, ), and (T, ) can be characterized by a universal property. We define the tree dimensiontd(X, ) of an ordered set as the minimal number of extensions of (X, ) which are trees such that the given order is the intersection of those tree orders. We give characterizations of the tree dimension, relations between dimension and tree dimension, and removal theorems.     

On spanning tree congestion

We prove that every connected graph G of order n has a spanning tree T such that for every edge e of T the edge cut defined in G by the vertex sets of the two components of T−e contains at most edges. This result solves a problem posed by Ostrovskii (M.I. Ostrovskii, Minimal congestion trees, Discrete Math. 285 (2004) 219-226).     

Embeddings of Twin Trees

In this article we provide sufficient conditions for when a pair of trees having a semi-codistance function can be embedded in a twin tree with codistance function extending . We use these conditions to show that given a twin tree T of bidegree (d1,d2) there exists a twin tree of bidegree (e1,e2) containing T as a substructure as long as di ei.     

On 4-semiregular 1-factorizations of complete graphs and complete bipartite graphs

A 4-semiregular 1-factorization is a 1-factorization in which every pair of distinct 1-factors forms a union of 4-cycles. LetK be the complete graphK _2nor the complete bipartite graphK _{n, n} .We prove that there is a 4-semiregular 1-factorization ofK if and only ifn is a power of 2 andn2, and 4-semiregular 1-factorizations ofK are isomorphic, and then we determine the symmetry groups. They are known for the case of the complete graphK _2n ,however, we prove them in a different method.