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.     

Two theorems on graceful trees

Let T be a tree on n vertices which are labelled by the integers in N = {1,2,…,n} such that each vertex of T is associated with a distinct number in N. The weight of an edge is defined to be the absolute value of the difference between the two numbers labelled at its end vertices. If the weights of all edges of T are distinct, we call T a graceful tree. In this note, two methods for constructing bigger graceful trees from a given one and a given pair of graceful trees are provided.     

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.     

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.     

Reznichenko families of trees and their applications

Examples of Talagrand, Gul'ko and Corson compacta resulting from Reznichenko families of trees are presented. The K_σδ property for weakly -analytic Banach spaces with an unconditional basis is proved.     

Graphs with certain families of spanning trees

Sufficient conditions are given in terms of δ(G) and Δ(T), for a graph G with n vertices to contain a tree T with n vertices. One of these sufficient conditions is used to calculate some of the Ramsey numbers for the pair tree-star. Also necessary conditions are given, in terms of δ(G), for a graph G with n vertices to contain all trees with n vertices.     

图Cn及其r-冠的新的优美标号

研究了关于图的r-冠的优美标号的一个问题,证明了：当n≡0,3（mod 4）时,图Cn及其r-冠是优美图,所给出的新的优美标号不同于现有文献中得到的结果.进而证明了当n≡0（mod 4）时,图Cn及其r-冠也是交错图.     

On centroid branches of trees from certain families

We obtain various results involving the centroid branches of randomly chosen trees from simply generated families.     

Strongly graceful graphs

In this paper, we prove that the n-cube is graceful, thus answering a conjecture of J.-C. Bermond and Gangopadhyay and Rao Hebbare. To do that, we introduce a special kind of graceful numbering, particular case of α-valuation, called strongly graceful and we prove that if a graph G is strongly graceful, G + K₂ is also strongly graceful.     

Super edge-magic strength of fire crackers, banana trees and unicyclic graphs

A graph G(V,E) is called super edge-magic if there exists a bijection f from V∪E to {1,2,3,…,|V|+|E|} such that f(u)+f(v)+f(uv)=c(f) is constant for any uv∈E and f(V)={1,2,3,…,|V|}. Such a bijection is called a super edge-magic labeling of G. The super edge-magic strength of a graph G is defined as the minimum of all c(f) where the minimum runs over all super edge-magic labelings of G and is denoted by sm(G). The super edge-magic strength of some families of graphs are obtained in this paper.     

基于拉普拉斯谱确定的两类树

设图G是简单连通图.如果任何一个与图G关于拉普拉斯矩阵同谱的图,都与图G同构,称图G可由其拉普拉斯谱确定.定义了树Y_n和树F(2,n,1)两类特殊结构的树.利用同谱图线图的特点,证明了树Y_n和树F(2,n,1)可由其拉普拉斯谱确定.     

On the average shape of simply generated families of trees

This paper deals with the limiting distribution of the level number of the jth leaf of a planted plane tree (where leaves are enumerated from left to right) for the so-called “simply generated families” introduced by Meir and Moon. The mathematical apparatus is determined by the idea of an asymptotic analysis of a given sequence of numbers by studying the location and nature of the singularities of appropriate generating functions.     

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.     

Splitting trees with neutral Poissonian mutations I: Small families

We consider a neutral dynamical model of biological diversity, where individuals live and reproduce independently. They have i.i.d. lifetime durations (which are not necessarily exponentially distributed) and give birth (singly) at constant rate b. Such a genealogical tree is usually called a splitting tree [9], and the population counting process (N_t;t≥0) is a homogeneous, binary Crump-Mode-Jagers process.We assume that individuals independently experience mutations at constant rate θ during their lifetimes, under the infinite-alleles assumption: each mutation instantaneously confers a brand new type, called an allele, to its carrier. We are interested in the allele frequency spectrum at time t, i.e., the number A(t) of distinct alleles represented in the population at time t, and more specifically, the numbers A(k,t) of alleles represented by k individuals at time t, k=1,2,…,N_t.We mainly use two classes of tools: coalescent point processes, as defined in [15], and branching processes counted by random characteristics, as defined in [11] and [13]. We provide explicit formulae for the expectation of A(k,t) conditional on population size in a coalescent point process, which apply to the special case of splitting trees. We separately derive the a.s. limits of A(k,t)/N_t and of A(t)/N_t thanks to random characteristics, in the same vein as in [19].Last, we separately compute the expected homozygosity by applying a method introduced in [14], characterizing the dynamics of the tree distribution as the origination time of the tree moves back in time, in the spirit of backward Kolmogorov equations.     

Packing and covering constants for certain families of trees. I

If ? denotes a family of rooted trees, let p_k(n) and c_k(n) denote the average value of the k-packing and k-covering numbers of trees in ? that have n nodes. We assume, among other things, that the generating function y of trees in ? satisfies a relation of the type y = x?(y) for some power series ?. We show that the limits of p_k(n)/n and c_k(n)/n as n → ∞ exist and we describe how to evaluate these limits.     

Generalized Stirling permutations, families of increasing trees and urn models

Bóna (2007) [6] studied the distribution of ascents, plateaux and descents in the class of Stirling permutations, introduced by Gessel and Stanley (1978) [13]. Recently, Janson (2008) [17] showed the connection between Stirling permutations and plane recursive trees and proved a joint normal law for the parameters considered by Bóna. Here we will consider generalized Stirling permutations extending the earlier results of Bóna (2007) [6] and Janson (2008) [17], and relate them with certain families of generalized plane recursive trees, and also (k+1)-ary increasing trees. We also give two different bijections between certain families of increasing trees, which both give as a special case a bijection between ternary increasing trees and plane recursive trees. In order to describe the (asymptotic) behaviour of the parameters of interests, we study three (generalized) Pólya urn models using various methods.     

New families of hypohamiltonian graphs

We construct three new infinite families of hypohamiltonian graphs having respectively 3k+1 vertices (k?3), 3k vertices (k?5) and 5k vertices (k?4); in particular, we exhibit a hypohamiltonian graph of order 19 and a cubic hypohamiltonian graph of order 20, the existence of which was still in doubt. Using these families, we get a lower bound for the number of non-isomorphic hypohamiltonian graphs of order 3k and 5k. We also give an example of an infinite graph G having no two-way infinite hamiltonian path, but in which every vertex-deleted subgraph G - x has such a path.