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     

Pancyclic arcs and connectivity in tournaments

A tournament is an orientation of the edges of a complete graph. An arc is pancyclic in a tournament T if it is contained in a cycle of length l, for every 3 ≤ l ≤ |T|. Let p(T) denote the number of pancyclic arcs in a tournament T. In 4 , Moon showed that for every non‐trivial strong tournament T, p(T) ≥ 3. Actually, he proved a somewhat stronger result: for any non‐trivial strong tournament h(T) ≥ 3 where h(T) is the maximum number of pancyclic arcs contained in the same hamiltonian cycle of T. Moreover, Moon characterized the tournaments with h(T) = 3. All these tournaments are not 2‐strong. In this paper, we investigate relationship between the functions p(T) and h(T) and the connectivity of the tournament T. Let p_k(n) := min {p(T), T k‐strong tournament of order n} and h_k(n) := min{h(T), T k‐strong tournament of order n}. We conjecture that (for k ≥ 2) there exists a constant α_k> 0 such that p_k(n) ≥ α_kn and h_k(n) ≥ 2k+1. In this paper, we establish the later conjecture when k = 2. We then characterized the tournaments with h(T) = 4 and those with p(T) = 4. We also prove that for k ≥ 2, p_k(n) ≥ 2k+3. At last, we characterize the tournaments having exactly five pancyclic arcs. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 87–110, 2004     

Average degree and contractibility

It is proved that for every number k there exists a number f(k) such that every finite k‐connected graph of average degree exceeding f(k) contains an edge whose contraction yields again a k‐connected graph. For the proof, tree orders on certain sets of smallest separating sets of the graph in question are constructed. This leads to new canonical tree decompositions as well. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Some results on spanning trees

Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ（G） =Δ（T） and the number of leaves of T is not greater than n D（G）＋1,where D（G） is the diameter of G.     

Spanning k‐arc‐strong subdigraphs with few arcs in k‐arc‐strong tournaments

Given a k‐arc‐strong tournament T, we estimate the minimum number of arcs possible in a k‐arc‐strong spanning subdigraph of T. We give a construction which shows that for each k ≥ 2, there are tournaments T on n vertices such that every k‐arc‐strong spanning subdigraph of T contains at least arcs. In fact, the tournaments in our construction have the property that every spanning subdigraph with minimum in‐ and out‐degree at least k has arcs. This is best possible since it can be shown that every k‐arc‐strong tournament contains a spanning subdigraph with minimum in‐ and out‐degree at least k and no more than arcs. As our main result we prove that every k‐arc‐strong tournament contains a spanning k‐arc‐strong subdigraph with no more than arcs. We conjecture that for every k‐arc‐strong tournament T, the minimum number of arcs in a k‐arc‐strong spanning subdigraph of T is equal to the minimum number of arcs in a spanning subdigraph of T with the property that every vertex has in‐ and out‐degree at least k. We also discuss the implications of our results on related problems and conjectures. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 265–284, 2004     

The structure of 4‐strong tournaments containing exactly three out‐arc pancyclic vertices

Yao et al. (Discrete Appl Math 99 (2000), 245–249) proved that every strong tournament contains a vertex u such that every out‐arc of u is pancyclic and conjectured that every k‐strong tournament contains k such vertices. At present, it is known that this conjecture is true for k = 1, 2, 3 and not true for k?4. In this article, we obtain a sufficient and necessary condition for a 4‐strong tournament to contain exactly three out‐arc pancyclic vertices, which shows that a 4‐strong tournament contains at least four out‐arc pancyclic vertices except for a given class of tournaments. Furthermore, our proof yields a polynomial algorithm to decide if a 4‐strong tournament has exactly three out‐arc pancyclic vertices.     

On a Spanning Tree with Specified Leaves

Let k ≥ 2 be an integer. We show that if G is a (k + 1)-connected graph and each pair of nonadjacent vertices in G has degree sum at least |G| + 1, then for each subset S of V(G) with |S| = k, G has a spanning tree such that S is the set of endvertices. This result generalizes Ore’s theorem which guarantees the existence of a Hamilton path connecting any two vertices. Dedicated to Professor Hikoe Enomoto on his 60th birthday.     

On low bound of degree sequences of spanning trees in K-edge-connected graphs

A graph G = (V, E) is k-edge-connected if for any subset E′ ⊆ E,|E′| < k, G − E′ is connected. A d_k-tree T of a connected graph G = (V, E) is a spanning tree satisfying that ∀v ∈ V, d_T(v) ≤ + α, where [·] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d_k-tree, and α = 1 for k = 2, α = 2 for k ≥ 3. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 87–95, 1998     

Spanning 3-ended trees in k-connected K 1,4-free graphs

A tree with at most m leaves is called an m-ended tree.Kyaw proved that every connected K1,4-free graph withσ4(G)n-1 contains a spanning 3-ended tree.In this paper we obtain a result for k-connected K1,4-free graphs with k 2.Let G be a k-connected K1,4-free graph of order n with k 2.Ifσk+3(G)n+2k-2,then G contains a spanning 3-ended tree.     

Toughness,trees, and walks

A graph is t‐tough if the number of components of G\S is at most |S|/t for every cutset S ⊆ V (G). A k‐walk in a graph is a spanning closed walk using each vertex at most k times. When k = 1, a 1‐walk is a Hamilton cycle, and a longstanding conjecture by Chvátal is that every sufficiently tough graph has a 1‐walk. When k ≥ 3, Jackson and Wormald used a result of Win to show that every sufficiently tough graph has a k‐walk. We fill in the gap between k = 1 and k ≥ 3 by showing that, when k = 2, every sufficiently tough (specifically, 4‐tough) graph has a 2‐walk. To do this we first provide a new proof for and generalize a result by Win on the existence of a k‐tree, a spanning tree with every vertex of degree at most k. We also provide new examples of tough graphs with no k‐walk for k ≥ 2. © 2000 John Wiley & Sons, Inc. J Graph Theory 33:125–137, 2000     

The number of pancyclic arcs in a k‐strong tournament

A tournament is a digraph, where there is precisely one arc between every pair of distinct vertices. An arc is pancyclic in a digraph D, if it belongs to a cycle of length l, for all 3 ≤ l ≤ |V (D) |. Let p(D) denote the number of pancyclic arcs in a digraph D and let h(D) denote the maximum number of pancyclic arcs belonging to the same Hamilton cycle of D. Note that p(D) ≥ h(D). Moon showed that h(T) ≥ 3 for all strong non‐trivial tournaments, T, and Havet showed that h(T) ≥ 5 for all 2‐strong tournaments T. We will show that if T is a k‐strong tournament, with k ≥ 2, then p(T) ≥ 1/2, nk and h(T) ≥ (k + 5)/2. This solves a conjecture by Havet, stating that there exists a constant α_k, such that p(T) ≥ α_k n, for all k‐strong tournaments, T, with k ≥ 2. Furthermore, the second results gives support for the conjecture h(T) ≥ 2k + 1, which was also stated by Havet. The previously best‐known bounds when k ≥ 2 were p(T) ≥ 2k + 3 and h(T) ≥ 5. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge

Tutte proved that every 3‐connected graph G on more than 4 vertices contains a contractible edge. We strengthen this result by showing that every depth‐first‐search tree of G contains a contractible edge. Moreover, we show that every spanning tree of G contains a contractible edge if G is 3‐regular or if G does not contain two disjoint pairs of adjacent degree‐3 vertices.     

The Erdős–Pósa Property for Odd Cycles in Graphs of Large Connectivity

Dedicated to the memory of Paul Erdős A graph G is k-linked if G has at least 2k vertices, and, for any vertices , , ..., , , , ..., , G contains k pairwise disjoint paths such that joins for i = 1, 2, ..., k. We say that G is k-parity-linked if G is k-linked and, in addition, the paths can be chosen such that the parities of their lengths are prescribed. We prove the existence of a function g(k) such that every g(k)-connected graph is k-parity-linked if the deletion of any set of less than 4k-3 vertices leaves a nonbipartite graph. As a consequence, we obtain a result of Erdős–Pósa type for odd cycles in graphs of large connectivity. Also, every -connected graph contains a totally odd -subdivision, that is, a subdivision of in which each edge of corresponds to an odd path, if and only if the deletion of any vertex leaves a nonbipartite graph. Received May 13, 1999/Revised June 19, 2000     

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     

An approximate version of Sumner?s universal tournament conjecture

Sumner?s universal tournament conjecture states that any tournament on 2n−2 vertices contains a copy of any directed tree on n vertices. We prove an asymptotic version of this conjecture, namely that any tournament on (2+o(1))n vertices contains a copy of any directed tree on n vertices. In addition, we prove an asymptotically best possible result for trees of bounded degree, namely that for any fixed Δ, any tournament on (1+o(1))n vertices contains a copy of any directed tree on n vertices with maximum degree at most Δ.     

Partitioning infinite trees

A graph G is bisectable if its edges can be colored by two colors so that the resulting monochromatic subgraphs are isomorphic. We show that any infinite tree of maximum degree Δ with infinitely many vertices of degree at least Δ −1 is bisectable as is any infinite tree of maximum degree Δ ≤ 4. Further, it is proved that every infinite tree T of finite maximum degree contains a finite subset E of its edges so that the graph T − E is bisectable. To measure how “far” a graph G is from being bisectable, we define c(G) to be the smallest number k > 1 so that there is a coloring of the edges of G by k colors with the property that any two monochromatic subgraphs are isomorphic. An upper bound on c(G), which is in a sense best possible, is presented. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 113–127, 2000     

On stability of Hamilton‐connectedness under the 2‐closure in claw‐free graphs

It is easy to characterize chordal graphs by every k‐cycle having at least f(k) = k ? 3 chords. I prove new, analogous characterizations of the house‐hole‐domino‐free graphs using f(k) = 2?(k ? 3)/2?, and of the graphs whose blocks are trivially perfect using f(k) = 2k ? 7. These three functions f(k) are optimum in that each class contains graphs in which every k‐cycle has exactly f(k) chords. The functions 3?(k ? 3)/3? and 3k ? 11 also characterize related graph classes, but without being optimum. I consider several other graph classes and their optimum functions, and what happens when k‐cycles are replaced with k‐paths. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:137‐147, 2011     

Spanning 2-strong tournaments in 3-strong semicomplete digraphs

We prove that every 3-strong semicomplete digraph on at least 5 vertices contains a spanning 2-strong tournament. Our proof is constructive and implies a polynomial algorithm for finding a spanning 2-strong tournament in a given 3-strong semicomplete digraph. We also show that there are infinitely many (2k−2)-strong semicomplete digraphs which contain no spanning k-strong tournament and conjecture that every(2k−1)-strong semicomplete digraph which is not the complete digraph on 2k vertices contains a spanning k-strong tournament.     

Odd‐angulated graphs and cancelling factors in box products

Under what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2k + 1. We say that G is (2k + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2k + 1)‐cycle. We call G strongly (2k + 1)‐angulated if every two vertices are connected by a sequence of (2k + 1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2k + 1)‐angulated, H is any graph, S, T are graphs with odd girth at least 2k + 1, and ?: G□ H→S□T is a graph homomorphism, then either ? maps G□{h} to S□{t_h} for all h∈V(H) where t_h∈V(T) depends on h; or ? maps G□{h} to {s_h}□ T for all h∈V(H) where s_h∈V(S) depends on h. This theorem allows us to prove several sufficient conditions for a cancelation law of a graph homomorphism between two box products with a common factor. We conclude the article with some open questions. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:221‐238, 2008     

Tiling Transitive Tournaments and Their Blow-ups

Let TT _k denote the transitive tournament on k vertices. Let TT(h,k) denote the graph obtained from TT _k by replacing each vertex with an independent set of size h≥1. The following result is proved: Let c ₂=1/2, c ₃=5/6 and c _k =1−2^{−k−log k} for k≥4. For every ∈>0 there exists N=N(∈,h,k) such that for every undirected graph G with n>N vertices and with δ(G)≥c _k n, every orientation of G contains vertex disjoint copies of TT(h,k) that cover all but at most ∈n vertices. In the cases k=2 and k=3 the result is asymptotically tight. For k≥4, c _k cannot be improved to less than 1−2^{−0.5k(1+o(1))}. This revised version was published online in June 2006 with corrections to the Cover Date.