Products of graceful trees

We give some conditions on H and $\text{G}$ for the rooted product H($\text{G}$) to be graceful. These conditions extend and unify previous results.     

New families of graceful banana trees

Consider a family of stars. Take a new vertex. Join one end-vertex of each star to this new vertex. The tree so obtained is known as abanana tree. It is proved that the banana trees corresponding to the family of stars

1. (K_1,1, K_1,2,…, K_{1,t ?1}, (α + l) K_1,t, K_{1,t + 1}, …, K_1,n), α ? 0
2. (2K_1,1, 2K_1,2,…, 2K_{1,t? 1}, (α + 2)K_1,t, 2K_{1,t + 1, …}, 2K_1,n), 0 ? α <t and
3. (3K_1,t, 3K_1,2, …, 3K_1,n) are graceful.

     

Almost all trees are almost graceful

The Graceful Tree Conjecture of Rosa from 1967 asserts that the vertices of each tree T of order n can be injectively labeled by using the numbers {1,2,…,n} in such a way that the absolute differences induced on the edges are pairwise distinct. We prove the following relaxation of the conjecture for each γ>0 and for all n>n₀(γ). Suppose that (i) the maximum degree of T is bounded by ), and (ii) the vertex labels are chosen from the set {1,2,…,?(1+γ)n?}. Then there is an injective labeling of V(T) such that the absolute differences on the edges are pairwise distinct. In particular, asymptotically almost all trees on n vertices admit such a labeling. The proof proceeds by showing that a certain very natural randomized algorithm produces a desired labeling with high probability.     

Two sets of graceful graphs

We give graceful numberings to the following graphs: (a) the union of n K₄ having one edge in common, in other words the join of K₂ and the union of n disjoint K₂ and (b) the union of n C₄ having one edge in common, in other words the product of K₂ and K_1,n, with n + 1 not a multiple of 4.     

A substitution theorem for graceful trees and its applications

A graceful labeling of a graph G=(V,E) assigns |V| distinct integers from the set {0,…,|E|} to the vertices of G so that the absolute values of their differences on the |E| edges of G constitute the set {1,…,|E|}. A graph is graceful if it admits a graceful labeling. The forty-year old Graceful Tree Conjecture, due to Ringel and Kotzig, states that every tree is graceful.We prove a Substitution Theorem for graceful trees, which enables the construction of a larger graceful tree through combining smaller and not necessarily identical graceful trees. We present applications of the Substitution Theorem, which generalize earlier constructions combining smaller trees.     

Two theorems on integral matrices

The following two results are proved: (1) For a positive definite integral symmetric matrix S of rank (S) < 7 or when rank (S) = 8, S has an odd entry in its diagonal, there is an integral matrix A satisfying AA^t = Sif there is a rational matrix R with RR^t = S (2) Given an integral matrix A of size r×n such that AA^t = mI_r there is then always an integral completion matrix B of size n×n satisfying BB^t = mI_r whenever n-r is less than or equal to 7. This threshold number 7 is the best possible. (Here m, n satisfy the obvious necessary conditions.)     

Two fixed-point theorems

Two fixed point theorems implementing a more general principle for partially ordered sets (which is also due to this author) are proved. Translated fromMatematicheskie Zametki, Vol. 66, No. 6, pp. 920–923, December, 1999.     

Combinatorial theorems about embedding trees on the real line

We consider the combinatorial problem of embedding the metric defined by an unweighted graph into the real line, so as to minimize the distortion of the embedding. This problem is inspired by connections to Banach space theory and to computer science. After establishing a framework in which to study line embeddings, we focus on metrics defined by three specific families of trees: complete binary trees, fans, and combs. We construct asymptotically optimal (i.e., distortion‐minimizing) line embeddings for these metrics and prove their optimality via suitable lower bound arguments. It appears that even such specialized metrics require nontrivial constructions and proofs of optimality require sophisticated combinatorial arguments. The combinatorial techniques from our work might prove useful in further algorithmic research on low distortion metric embeddings. © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 153–168, 2011     

Limit theorems for reinforced random walks on certain trees

Consider a linearly edge-reinforced random walk defined on the b-ary tree, b≥70. We prove the strong law of large numbers for the distance of this process from the root. We give a sufficient condition for this strong law to hold for general edge-reinforced random walks and random walks in a random environment. We also provide a central limit theorem. Supported in part by a Purdue Research Foundation fellowship this work is part of the author's PhD thesis.     

Two theorems on quasireflexive Banach spaces

In the first theorem a characterization is given of the quasireflexive Banach spaces as spaces, every one-to-one linear map of which is a G-embedding. The second theorem develops a result of Rosenthal on the zero inclination of two subspaces in the event that they have only quasireflexive isomprphic subspaces.Translated from Ukrainskii Maternaticheskii Zhurnal, Vol. 42, No. 2, pp. 276–279, February, 1990.