Bounds on the convex label number of trees

A convex labelling of a tree is an assignment of distinct non-negative integer labels to vertices such that wheneverx, y andz are the labels of vertices on a path of length 2 theny≦(x+z)/2. In addition if the tree is rooted, a convex labelling must assign 0 to the root. The convex label number of a treeT is the smallest integerm such thatT has a convex labelling with no label greater thanm. We prove that every rooted tree (and hence every tree) withn vertices has convex label number less than 4n. We also exhibitn-vertex trees with convex label number 4n/3+o(n), andn-vertex rooted trees with convex label number 2n +o(n). The research by M. B. and A. W. was partly supported by NSF grant MCS—8311422.     

Bipartite labelings of trees and the gracesize

Let T = (V, E) be a tree whose vertices are properly 2-colored. A bipartite labeling of T is a bijection f: V ← {0, 1, ?, | E |} for which there is a k such that whenever f(u) ≤ k < f(v), then u and v have different colors. The α-size of the tree T is the maximum number of distinct values of the induced edge labels |f(u) - f(v)|, uv ? E, taken over all bipartite labelings f of T. We investigate the asymptotic behavior of the α-size of trees. Let α(n) be the smallest α-size among all the trees with n edges. As our main result we prove that 5(n + 1)/7 ≤ α(n) ≤ (5n + 9)/6. A connection with the graceful tree conjecture is established, in that every tree with n edges is shown to have “gracesize” at least 5n/7. © 1995 John Wiley & Sons, Inc.     

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.     

Rooted Spanning Trees in Tournaments

A tournament of order n is an orientation of a complete graph with n vertices, and is specified by its vertex set V(T) and edge set E(T). A rooted tree is a directed tree such that every vertex except the root has in-degree 1, while the root has in-degree 0. A rooted k-tree is a rooted tree such that every vertex except the root has out-degree at most k; the out-degree of the root can be larger than k. It is well-known that every tournament contains a rooted spanning tree of depth at most 2; and the root of such a tree is also called a king in the literature. This result was strengthened to the following one: Every tournament contains a rooted spanning 2-tree of depth at most 2. We prove that every tournament of order n≥800 contains a spanning rooted special 2-tree in this paper, where a rooted special 2-tree is a rooted 2-tree of depth 2 such that all except possibly one, non-root, non-leaf vertices, have out-degree 2 in the tree. Revised: November 9, 1998     

Semirotational Tree Factorizations of Complete Graphs

We select the class of so-called semisymmetric trees and prove that every tree T from this class admits a T-factorization of a special form in the case where T is of order n = 2k 16. We formulate the conjecture that every semisymmetric tree T admits a T-factorization. We establish the existence of a T-factorization for semisymmetric trees of certain classes.     

Spanning trees in randomly perturbed graphs

A classical result of Komlós, Sárközy, and Szemerédi states that every n‐vertex graph with minimum degree at least (1/2 + o(1))n contains every n‐vertex tree with maximum degree . Krivelevich, Kwan, and Sudakov proved that for every n‐vertex graph G_α with minimum degree at least αn for any fixed α > 0 and every n‐vertex tree T with bounded maximum degree, one can still find a copy of T in G_α with high probability after adding O(n) randomly chosen edges to G_α. We extend the latter results to trees with (essentially) unbounded maximum degree; for a given and α > 0, we determine up to a constant factor the number of random edges that we need to add to an arbitrary n‐vertex graph with minimum degree αn in order to guarantee with high probability a copy of any fixed n‐vertex tree with maximum degree at most Δ.     

The spanning trees forced by the path and the star

A set S of trees of order n forces a tree T if every graph having each tree in S as a spanning tree must also have T as a spanning tree. A spanning tree forcing set for order n that forces every tree of order n. A spanning-tree forcing set S is a test set for panarboreal graphs, since a graph of order n is panarboreal if and only if it has all of the trees in S as spanning trees. For each positive integer n ≠ 1, the star belongs to every spanning tree forcing set for order n. The main results of this paper are a proof that the path belongs to every spanning-tree forcing set for each order n ∉ {1, 6, 7, 8} and a computationally tractable characterization of the trees of order n ≥ 15 forced by the path and the star. Corollaries of those results include a construction of many trees that do not belong to any minimal spanning tree forcing set for orders n ≥ 15 and a proof that the following related decision problem is NP-complete: an instance is a pair (G, T) consisting of a graph G of order n and maximum degree n - 1 with a hamiltonian path, and a tree T of order n; the problem is to determine whether T is a spanning tree of G. © 1996 John Wiley & Sons, Inc.     

Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture

We give a short constructive proof of a theorem of Fisher: every tournament contains a vertex whose second outneighborhood is as large as its first outneighborhood. Moreover, we exhibit two such vertices provided that the tournament has no dominated vertex. The proof makes use of median orders. A second application of median orders is that every tournament of order 2n − 2 contains every arborescence of order n > 1. This is a particular case of Sumner's conjecture: every tournament of order 2n − 2 contains every oriented tree of order n > 1. Using our method, we prove that every tournament of order (7n − 5)/2 contains every oriented tree of order n. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 244–256, 2000     

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.     

Bipartite labeling of trees with maximum degree three

Let T = (V, E) be a tree with a properly 2‐colored vertex set. A bipartite labeling of T is a bijection φ: V → {1, …, |V|} for which there exists a k such that whenever φ(u) ≤ k < φ(v), then u and v have different colors. The α‐size α(T) of the tree T is the maximum number of elements in the sets {|φ(u) − φ(v)|; uv ∈ E}, taken over all bipartite labelings φ of T. The quantity α(n) is defined as the minimum of α(T) over all trees with n vertices. In an earlier article (J Graph Theory 19 (1995), 201–215), A. Rosa and the second author proved that 5n/7 ≤ α(n) ≤ (5n + 4)/6 for all n ≥ 4; the upper bound is believed to be the asymptotically correct value of (n). In this article, we investigate the α‐size of trees with maximum degree three. Let α₃(n) be the smallest α‐size among all trees with n vertices, each of degree at most three. We prove that α₃(n) ≥ 5n/6 for all n ≥ 12, thus supporting the belief above. This result can be seen as an approximation toward the graceful tree conjecture—it shows that every tree on n ≥ 12 vertices and with maximum degree three has “gracesize” at least 5n/6. Using a computer search, we also establish that α₃(n) ≥ n − 2 for all n ≤ 17. © 1999 John Wiley & Sons, Inc. J Graph Theory 31:7–15, 1999     

On Modular Edge-Graceful Graphs

Let G be a connected graph of order \({n\ge 3}\) and size m and \({f:E(G)\to \mathbb{Z}_n}\) an edge labeling of G. Define a vertex labeling \({f': V(G)\to \mathbb{Z}_n}\) by \({f'(v)= \sum_{u\in N(v)}f(uv)}\) where the sum is computed in \({\mathbb{Z}_n}\) . If f′ is one-to-one, then f is called a modular edge-graceful labeling and G is a modular edge-graceful graph. A graph G is modular edge-graceful if G contains a modular edge-graceful spanning tree. Several classes of modular edge-graceful trees are determined. For a tree T of order n where \({n\not\equiv 2 \pmod 4}\) , it is shown that if T contains at most two even vertices or the set of even vertices of T induces a path, then T is modular edge-graceful. It is also shown that every tree of order n where \({n\not\equiv 2\pmod 4}\) having diameter at most 5 is modular edge-graceful.     

Lengths of cycles in halin graphs

A Halin graph is a plane graph H = T U C, where T is a plane tree with no vertex of degree two and at least one vertex of degree three or more, and C is a cycle connecting the endvertices of T in the cyclic order determined by the embedding of T. We prove that such a graph on n vertices contains cycles of all lengths l, 3 ≤ l n, except, possibly, for one even value m of l. We prove also that if the tree T contains no vertex of degree three then G is pancyclic.     

Invariant densities and mean ergodicity of markov operators

We prove that a Markov operatorT onL ₁ has an invariant density if and only if there exists a densityf that satisfies lim sup _n→∞‖T ⁿ f − f‖ < 2. Using this result, we show that a Frobenius-Perron operatorP is mean ergodic if and only if there exists a densityw such that lim sup _n→∞ ‖P ⁿ f − w‖<2 for every densityf. Corresponding results hold for strongly continuous semigroups.     

Combinatorial interpretations for TG(1, −1)

Let G be a connected and simple graph with vertex set {1, 2, …, n + 1} and T_G(x, y) the Tutte polynomial of G. In this paper, we give combinatorial interpretations for T_G(1, ?1). In particular, we give the definitions of even spanning tree and left spanning tree. We prove T_G(1, ?1) is the number of even‐left spanning trees of G. We associate a permutation with a spanning forest of G and give the definition of odd G‐permutations. We show T_G(1, ?1) is the number of odd G‐permutations. We give a bijection from the set of odd K_{n + 1}‐permutations to the set of alternating permutations on the set {1, 2, …, n}. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 341–348, 2012     

Perfect Matchings in ε-Regular Graphs and the Blow-Up Lemma

G on vertex set , , with density d>2ε and all vertex degrees not too far from d, has about as many perfect matchings as a corresponding random bipartite graph, i.e. about . In this paper we utilize that result to prove that with probability quickly approaching one, a perfect matching drawn randomly from G is spread evenly, in the sense that for any large subsets of vertices and , the number of edges of the matching spanned between S and T is close to |S||T|/n (c.f. Lemma 1). As an application we give an alternative proof of the Blow-up Lemma of Komlós, Sárk?zy and Szemerédi [10]. Received: December 5, 1997     

Decompositions of graphs into trees

Let θ be a family of graphs. By a θ-decomposition of a graph G we mean a partition λ of the edge set of G such that every F ? π spans in G a subgraph isomorphic to a graph in θ. In this paper we state the following conjecture: If T₁ and T₂ are two trees having relatively prime sizes then there exists c = c(T₁ T₂) such that every graph G satisfying the condition δ(G) ? c has a {T₁, T₂}-decom-position. We prove this conjecture for some special pairs of trees. In particular, we prove it in the following cases: (i) T₁ and T₂ are stars having relatively prime sizes; (ii) T₁ and T₂ are paths having relatively prime sizes; and. (iii) T₁ = T₂ - {v}, where v is a terminal vertex in T ₂.     

Every vertex a king

A king in a tournament is a vertex which can reach every other vertex via a 1-path or 2-path. A new inductive proof is given for the existence of an n-tournament with exactly k kings for all integers n ? k ? 1 with the following exceptions: k = 2 with n arbitrary, and n = k = 4 (in which cases no such n-tournament exists). Also, given an n-tournament T, the smallest order m is determined so that there exists an m-tournament W which contains T as a subtournament and so that every vertex of W is a king. Bounds are obtained in a similar problem in which the kings of W are exactly the vertices of T.     

Multicolored trees in complete graphs

A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph K_2n(n > 2) with 2n ? 1 colors, there are two edge‐disjoint multicolored spanning trees. In this paper we generalize this result showing that if (a₁,…, a_k) is a color distribution for the complete graph K_n, n ≥ 5, such that , then there exist two edge‐disjoint multicolored spanning trees. Moreover, we prove that for any edge coloring of the complete graph K_n with the above distribution if T is a non‐star multicolored spanning tree of K_n, then there exists a multicolored spanning tree T' of K_n such that T and T' are edge‐disjoint. Also it is shown that if K_n, n ≥ 6, is edge colored with k colors and , then there exist two edge‐disjoint multicolored spanning trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 221–232, 2007     

AN EXTREME POINT WHICH IS ORTHOGONAL TO THE RANGE OF THE OPERATOR,CONJUGATED TO AN OPERATOR ON l 1

Abstract

In this note we prove that if a linear bounded operator T from l ₁ to a Banach space Y is not an isomorphism, then there exists an element f = (f ₁, f ₂,…) ε l _∞ such that |f _n| = 1 for every n and dist (f, T*Y*) = 1. This result we apply to Sidon sets in the theory of Fourier series.     

Some remarks on the odd hadwiger’s conjecture

We say that H has an odd complete minor of order at least l if there are l vertex disjoint trees in H such that every two of them are joined by an edge, and in addition, all the vertices of trees are two-colored in such a way that the edges within the trees are bichromatic, but the edges between trees are monochromatic. Gerards and Seymour conjectured that if a graph has no odd complete minor of order l, then it is (l ? 1)-colorable. This is substantially stronger than the well-known conjecture of Hadwiger. Recently, Geelen et al. proved that there exists a constant c such that any graph with no odd K _k -minor is ck√logk-colorable. However, it is not known if there exists an absolute constant c such that any graph with no odd K _k -minor is ck-colorable. Motivated by these facts, in this paper, we shall first prove that, for any k, there exists a constant f(k) such that every (496k + 13)-connected graph with at least f(k) vertices has either an odd complete minor of size at least k or a vertex set X of order at most 8k such that G–X is bipartite. Since any bipartite graph does not contain an odd complete minor of size at least three, the second condition is necessary. This is an analogous result of Böhme et al. We also prove that every graph G on n vertices has an odd complete minor of size at least n/2α(G) ? 1, where α(G) denotes the independence number of G. This is an analogous result of Duchet and Meyniel. We obtain a better result for the case α(G)= 3.