Out-arc pancyclicity of vertices in tournaments

Yao, Guo and Zhang [T. Yao, Y. Guo, K. Zhang, Pancyclic out-arcs of a vertex in a tournament, 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. In this paper, we prove that every strong tournament with minimum out-degree at least two contains two such vertices. Yeo [A. Yeo, The number of pancyclic arcs in a k-strong tournament, J. Graph Theory 50 (2005) 212-219.] conjectured that every 2-strong tournament has three distinct vertices {x,y,z}, such that every arc out of x,y and z is pancyclic. In this paper, we also prove that Yeo’s conjecture is true.     

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.     

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.     

Vertex‐pancyclicity of hypertournaments

A hypertournament or a k‐tournament, on n vertices, 2≤k≤n, is a pair T=(V, E), where the vertex set V is a set of size n and the edge set E is the collection of all possible subsets of size k of V, called the edges, each taken in one of its k! possible permutations. A k‐tournament is pancyclic if there exists (directed) cycles of all possible lengths; it is vertex‐pancyclic if moreover the cycles can be found through any vertex. A k‐tournament is strong if there is a path from u to v for each pair of distinct vertices u and v. A question posed by Gutin and Yeo about the characterization of pancyclic and vertex‐pancyclic hypertournaments is examined in this article. We extend Moon's Theorem for tournaments to hypertournaments. We prove that if k≥8 and n≥k + 3, then a k‐tournament on n vertices is vertex‐pancyclic if and only if it is strong. Similar results hold for other values of k. We also show that when n≥7, k≥4, and n≥k + 2, a strong k‐tournament on n vertices is pancyclic if and only if it is strong. The bound n≥k+ 2 is tight. We also find bounds for the generalized problem when we extend vertex‐pancyclicity to require d edge‐disjoint cycles of each possible length and extend strong connectivity to require d edge‐disjoint paths between each pair of vertices. Our results include and extend those of Petrovic and Thomassen. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 338–348, 2010     

The number of vertices whose out-arcs are pancyclic in a 2-strong tournament

An arc going out from a vertex x in a digraph is called an out-arc of x. Yao et al. [Discrete Appl. Math. 99 (2000) 245-249] proved that every strong tournament contains a vertex x such that all out-arcs of x are pancyclic. Recently, Yeo [J. Graph Theory 50 (2005) 212-219] proved that each 3-strong tournament contains two such vertices. In this paper, we confirm that Yeo's result is also true for 2-strong tournaments. Our proof implies a polynomial algorithm to find two such vertices.     

Outpaths of arcs in multipartite tournaments

1. IntroductionThroughout the paPer, we use the terminology and notation of [1] and [2]. Let D =(V(D), A(D)) be a digraPh. If xy is an arc of a digraPh D, then we say that x dominatesy, denoted by x - y. More generally, if A and B are two disjoint vertex sets of D such thatevery vertex of A dominates every vertex of B, then we say that A dominates B, denotedby A - B. The outset N (x) of a vertex x is the set of vertices dominated by x in D,and the inset N--(x) is the set of vertices d…     

Edge‐disjoint Hamiltonian cycles in hypertournaments

We introduce a method for reducing k‐tournament problems, for k ≥ 3, to ordinary tournaments, that is, 2‐tournaments. It is applied to show that a k‐tournament on n ≥ k + 1 + 24d vertices (when k ≥ 4) or on n ≥ 30d + 2 vertices (when k = 3) has d edge‐disjoint Hamiltonian cycles if and only if it is d‐edge‐connected. Ironically, this is proved by ordinary tournament arguments although it only holds for k ≥ 3. We also characterizatize the pancyclic k‐tournaments, a problem posed by Gutin and Yeo.(Our characterization is slightly incomplete in that we prove it only for n large compared to k.). © 2005 Wiley Periodicals, Inc. J Graph Theory     

On Light Graphs in 3-Connected Plane Graphs Without Triangular or Quadrangular Faces

 We prove that each 3-connected plane graph G without triangular or quadrangular faces either contains a k-path P _k , a path on k vertices, such that each of its k vertices has degree ≤5/3k in G or does not contain any k-path. We also prove that each 3-connected pentagonal plane graph G which has a k-cycle, a cycle on k vertices, k∈ {5,8,11,14}, contains a k-cycle such that all its vertices have, in G, bounded degrees. Moreover, for all integers k and m, k≥ 3, k∉ {5,8,11,14} and m≥ 3, we present a graph in which every k-cycle contains a vertex of degree at least m. Received: June 29, 1998 Final version received: April 11, 2000     

On the number of affine equivalence classes of spherical tube hypersurfaces

We consider Levi non-degenerate tube hypersurfaces in \mathbbCⁿ⁺¹{\mathbb{C}^{n+1}} that are (k, n − k)-spherical, i.e. locally CR-equivalent to the hyperquadric with Levi form of signature (k, n − k), with n ≤ 2k. We show that the number of affine equivalence classes of such hypersurfaces is infinite (in fact, uncountable) in the following cases: (i) k = n − 2, n ≥ 7; (ii) k = n − 3, n ≥ 7; (iii) k ≤ n − 4. For all other values of k and n, except for k = 3, n = 6, the number of affine classes was known to be finite. The exceptional case k = 3, n = 6 has been recently resolved by Fels and Kaup who gave an example of a family of (3, 3)-spherical tube hypersurfaces that contains uncountably many pairwise affinely non-equivalent elements. In this paper we deal with the Fels–Kaup example by different methods. We give a direct proof of the sphericity of the hypersurfaces in the Fels–Kaup family, and use the j-invariant to show that this family indeed contains an uncountable subfamily of pairwise affinely non-equivalent hypersurfaces.     

The Number of Out-Pancyclic Vertices in a Strong Tournament

An arc in a tournament T with n ≥ 3 vertices is called pancyclic, if it belongs to a cycle of length l for all 3 ≤ l ≤ n. We call a vertex u of T an out-pancyclic vertex of T, if each out-arc of u is pancyclic in T. Yao et al. (Discrete Appl. Math. 99, 245–249, 2000) proved that every strong tournament contains an out-pancyclic vertex. For strong tournaments with minimum out-degree 1, Yao et al. found an infinite class of strong tournaments, each of which contains exactly one out-pancyclic vertex. In this paper, we prove that every strong tournament with minimum out-degree at least 2 contains three out-pancyclic vertices. Our result is best possible since there is an infinite family of strong tournaments with minimum degree at least 2 and no more than 3 out-pancyclic vertices.     

Vertex pancyclic in‐tournaments

An in‐tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. The topic of this paper is to investigate vertex k‐pancyclicity of in‐tournaments of order n, where for some 3 ≤ k ≤ n, every vertex belongs to a cycle of length p for every k ≤ p ≤ n. We give sharp lower bounds for the minimum degree such that a strong in‐tournament is vertex k‐pancyclic for k ≤ 5 and k ≥ n − 3. In the latter case, we even show that the in‐tournaments in consideration are fully (n − 3)‐extendable which means that every vertex belongs to a cycle of length n − 3 and that the vertex set of every cycle of length at least n − 3 is contained in a cycle of length one greater. In accordance with these results, we state the conjecture that every strong in‐tournament of order n with minimum degree greater than is vertex k‐pancyclic for 5 < k < n − 3, and we present a family of examples showing that this bound would be best possible. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 84–104, 2001     

Global Connectivity And Expansion: Long Cycles and Factors In f-Connected Graphs

Given a function f : ℕ→ℝ, call an n-vertex graph f-connected if separating off k vertices requires the deletion of at least f(k) vertices whenever k≤(n−f(k))/2. This is a common generalization of vertex connectivity (when f is constant) and expansion (when f is linear). We show that an f-connected graph contains a cycle of length linear in n if f is any linear function, contains a 1-factor and a 2-factor if f(k)≥2k+1, and contains a Hamilton cycle if f(k)≥2(k+1)². We conjecture that linear growth of f suffices to imply hamiltonicity.     

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     

Path numbers of tournaments

A family of simple (that is, cycle-free) paths is a path decomposition of a tournament T if and only if partitions the acrs of T. The path number of T, denoted pn(T), is the minimum value of | | over all path decompositions of T. In this paper it is shown that if n is even, then there is a tournament on n vertices with path number k if and only if n/2 k n²/4, k an integer. It is also shown that if n is odd and T is a tournament on n vertices, then (n + 1)/2 pn(T) (n² − 1)/4. Moreover, if k is an integer satisfying (i) (n + 1)/2 k n − 1 or (ii) n < k (n² − 1)/4 and k is even, then a tournament on n vertices having path number k is constructed. It is conjectured that there are no tournaments of odd order n with odd path number k for n k < (n² − 1)/4.     

Hamiltonicity, independence number, and pancyclicity

A graph on n vertices is called pancyclic if it contains a cycle of length ? for all 3≤?≤n. In 1972, Erd?s proved that if G is a Hamiltonian graph on n>4k⁴ vertices with independence number k, then G is pancyclic. He then suggested that n=Ω(k²) should already be enough to guarantee pancyclicity. Improving on his and some other later results, we prove that there exists a constant c such that n>ck^7/3 suffices.     

A 2-factor with Short Cycles Passing Through Specified Independent Vertices in Graph

For a graph G, we define σ₂(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k of length at most four such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k. And show if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k, V(C ₁) ∪...∪ V(C _k ) = V(G), and |C _i | ≤ 4 for all 1 ≤ i ≤ k − 1. The condition of degree sum σ₂(G) ≥ n + k − 1 is sharp. Received: December 20, 2006. Final version received: December 12, 2007.     

The Convexity Number of a Graph

 For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented. Received: August 19, 1998 Final version received: May 17, 2000     

Claws in Rotational Tournaments

 A claw is a rooted tree whose each branch is a directed path starting at the root. We prove that each rotational tournament on 2n+1 vertices contains all claws with 2n edges and at most n branches. Received: December 15, 1999 Final version received: April 18, 2001 Acknowledgements. The authors wish to express their gratitude to the referee for valuable remarks, suggestions and comments that led to an improved paper.     

On the Perfect Matchings of Near Regular Graphs

Let k, h be positive integers with k ≤ h. A graph G is called a [k, h]-graph if k ≤ d(v) ≤ h for any v ? V(G){v \in V(G)}. Let G be a [k, h]-graph of order 2n such that k ≥ n. Hilton (J. Graph Theory 9:193–196, 1985) proved that G contains at least ?k/3?{\lfloor k/3\rfloor} disjoint perfect matchings if h = k. Hilton’s result had been improved by Zhang and Zhu (J. Combin. Theory, Series B, 56:74–89, 1992), they proved that G contains at least ?k/2?{\lfloor k/2\rfloor} disjoint perfect matchings if k = h. In this paper, we improve Hilton’s result from another direction, we prove that Hilton’s result is true for [k, k + 1]-graphs. Specifically, we prove that G contains at least ?\fracn3?+1+(k-n){\lfloor\frac{n}3\rfloor+1+(k-n)} disjoint perfect matchings if h = k + 1.     

On κ—ordered Graphs Involved Degree Sum

A graph G is κ-ordered Hamiltonian 2≤κ≤n,if for every ordered sequence S of κ distinct vertices of G,there exists a Hamiltonian cycle that encounters S in the given order,In this article,we prove that if G is a graph on n vertices with degree sum of nonadjacent vertices at least n 3κ-9/2,then G is κ-ordered Hamiltonian for κ=3,4,…,[n/19].We also show that the degree sum bound can be reduced to n 2[κ/2]-2 if κ(G）≥3κ-1/2 or δ（G）≥5κ-4.Several known results are generalized.