On the Number of 4‐Cycles in a Tournament

If T is an n‐vertex tournament with a given number of 3‐cycles, what can be said about the number of its 4‐cycles? The most interesting range of this problem is where T is assumed to have cyclic triples for some and we seek to minimize the number of 4‐cycles. We conjecture that the (asymptotic) minimizing T is a random blow‐up of a constant‐sized transitive tournament. Using the method of flag algebras, we derive a lower bound that almost matches the conjectured value. We are able to answer the easier problem of maximizing the number of 4‐cycles. These questions can be equivalently stated in terms of transitive subtournaments. Namely, given the number of transitive triples in T, how many transitive quadruples can it have? As far as we know, this is the first study of inducibility in tournaments.     

Disjoint 3‐Cycles in Tournaments: A Proof of The Bermond–Thomassen Conjecture for Tournaments

We prove that every tournament with minimum out‐degree at least contains k disjoint 3‐cycles. This provides additional support for the conjecture by Bermond and Thomassen that every digraph D of minimum out‐degree contains k vertex disjoint cycles. We also prove that for every , when k is large enough, every tournament with minimum out‐degree at least contains k disjoint cycles. The linear factor 1.5 is best possible as shown by the regular tournaments.     

On the structure of graphs with a unique k‐factor

In this paper we study the structure of graphs with a unique k‐factor. Our results imply a conjecture of Hendry on the maximal number m (n,k) of edges in a graph G of order n with a unique k‐factor: For we prove and construct all corresponding extremal graphs. For we prove . For n = 2kl, l ∈ ℕ, this bound is sharp, and we prove that the corresponding extremal graph is unique up to isomorphism. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 227–243, 2000     

List‐Coloring the Squares of Planar Graphs without 4‐Cycles and 5‐Cycles

Let G be a planar graph without 4‐cycles and 5‐cycles and with maximum degree . We prove that . For arbitrarily large maximum degree Δ, there exist planar graphs of girth 6 with . Thus, our bound is within 1 of being optimal. Further, our bound comes from coloring greedily in a good order, so the bound immediately extends to online list‐coloring. In addition, we prove bounds for ‐labeling. Specifically, and, more generally, , for positive integers p and q with . Again, these bounds come from a greedy coloring, so they immediately extend to the list‐coloring and online list‐coloring variants of this problem.     

The Zarankiewicz problem in 3‐partite graphs

Let be a graph, be an integer, and write for the maximum number of edges in an ‐vertex graph that is ‐partite and has no subgraph isomorphic to . The function has been studied by many researchers. Finding is a special case of the Zarankiewicz problem. We prove an analog of the Kövári‐Sós‐Turán theorem for 3‐partite graphs by showing for . Using Sidon sets constructed by Bose and Chowla, we prove that this upper bound is asymptotically best possible in the case that and is odd, that is, for . In the cases of and , we use a result of Allen, Keevash, Sudakov, and Verstraëte, to show that a similar upper bound holds for all and gives a better constant when . Finally, we point out an interesting connection between difference families from design theory and .     

Enclosings of λ‐Fold 5‐Cycle Systems: Adding One Vertex

A k‐cycle system of a multigraph G is an ordered pair (V, C) where V is the vertex set of G and C is a set of k‐cycles, the edges of which partition the edges of G. A k‐cycle system of is known as a λ‐fold k‐cycle system of order V. A k‐cycle system of (V, C) is said to be enclosed in a k‐cycle system of if and . We settle the difficult enclosing problem for λ‐fold 5‐cycle systems with u = 1.     

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.     

Minimum C5‐saturated graphs

A graph is C₅‐saturated if it has no five‐cycle as a subgraph, but does contain a C₅ after the addition of any new edge. We prove that the minimum number of edges in a C₅ ‐saturated graph on n≥11 vertices is sat(n, C₅)=?10(n?1)/7??1 if n∈N₀={11, 12, 13, 14, 16, 18, 20} and is ?10(n?1)/7? if n≥11 and n?N₀. © 2009 Wiley Periodicals, Inc. J Graph Theory     

多部竞赛图中包含某条弧的圈

多部竞赛图或n部竞赛图是指一个完全n部无向图的定向图.2007年Volkmann证明了每个强连通的n部竞赛图(n≥3)至少存在一条弧它包含在从3到n的每个长度的圈中.在此基础上给出了强连通n部竞赛图中存在一条弧它包含在从3到n+1的每个长度的圈中的一个充分条件,并举例说明该条件在某种意义上的最佳可能性.     

Solution of a conjecture of Tewes and Volkmann regarding extendable cycles in in‐tournaments

A directed cycle C of a digraph D is extendable if there exists a directed cycle C′ in D that contains all vertices of C and an additional one. In 1989, Hendry defined a digraph D to be cycle extendable if it contains a directed cycle and every non‐Hamiltonian directed cycle of D is extendable. Furthermore, D is fully cycle extendable if it is cycle extendable and every vertex of D belongs to a directed cycle of length three. In 2001, Tewes and Volkmann extended these definitions in considering only directed cycles whose length exceed a certain bound 3≤k<n: a digraph D is k ‐extendable if every directed cycle of length t, where k≤t<n, is extendable. Moreover, D is called fully k ‐extendable if D is k ‐extendable and every vertex of D belongs to a directed cycle of length k. An in‐tournament is an oriented graph such that the in‐neighborhood of every vertex induces a tournament. This class of digraphs which generalizes the class of tournaments was introduced by Bang‐Jensen, Huang and Prisner in 1993. Tewes and Volkmann showed that every connected in‐tournament D of order n with minimum degree δ≥1 is ( ) ‐extendable. Furthermore, if D is a strongly connected in‐tournament of order n with minimum degree δ=2 or , then D is fully ( ) ‐extendable. In this article we shall see that if , every vertex of D belongs to a directed cycle of length , which means that D is fully ( ) ‐extendable. This confirms a conjecture of Tewes and Volkmann. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 82–92, 2010     

Edge‐colorings avoiding rainbow stars

We consider an extremal problem motivated by a article of Balogh [J. Balogh, A remark on the number of edge colorings of graphs, European Journal of Combinatorics 27, 2006, 565–573], who considered edge‐colorings of graphs avoiding fixed subgraphs with a prescribed coloring. More precisely, given , we look for n‐vertex graphs that admit the maximum number of r‐edge‐colorings such that at most colors appear in edges incident with each vertex, that is, r‐edge‐colorings avoiding rainbow‐colored stars with t edges. For large n, we show that, with the exception of the case , the complete graph is always the unique extremal graph. We also consider generalizations of this problem.     

All minimum C5‐saturated graphs

A graph is C₅‐ saturated if it has no five‐cycle as a subgraph, but does contain a C₅ after the addition of any new edge. Extending our previous result, we prove that the minimum number of edges in a C₅‐saturated graph on n vertices is sat(n, C₅) = ?10(n ? 1)/7? ? 1 for 11≤n≤14, or n = 16, 18, 20, and is ?10(n ? 1)/7? for all other n≥5, and we also prove that the only C₅‐saturated graphs with sat(n, C₅) edges are the graphs described in Section 2 . © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 9‐26, 2011     

A note on 3‐partite graphs without 4‐cycles

Let $C_4$ be a cycle of order 4. Write $ex\left(n,n,n,C_4\right)$ for the maximum number of edges in a balanced 3‐partite graph whose vertex set consists of three parts, each has $n$ vertices that have no subgraph isomorphic to $C_4$. In this paper, we show that $ex\left(n,n,n,C_4\right)\ge \frac{3}{2}n\left(p+1\right)$, where $n=\frac{p\left(p?1\right)}{2}$ and $p$ is a prime number. Note that $ex\left(n,n,n,C_4\right)\le \left(\frac{3\sqrt{2}}{2}+o\left(1\right)\right)n^{\frac{3}{2}}$ from Tait and Timmons's works. Since for every integer $m$, one can find a prime $p$ such that $m\le p\le \left(1+o\left(1\right)\right)m$, we obtain that $\underset{n\to \infty }{\lim }\frac{ex\left(n,n,n,C_4\right)}{\frac{3\sqrt{2}}{2}{n}^{\frac{3}{2}}}=1$.     

短圈并图的列表极值数(英文)

The list extremM number,f(G) is defined for a graph G as the smallest integer k such that the join of G with a stable set of size k is not |V(G)|-choosable.In this paper,we find the exact value of f (G),where G is the union ofedge-disjoint cycles of length three,four,five and six.Our results confirm two conjectures posed by S.Gravier,F.Matfray and B.Mohar.     

Cycles with a given number of vertices from each partite set in regular multipartite tournaments

If x is a vertex of a digraph D, then we denote by d ⁺(x) and d ⁻(x) the outdegree and the indegree of x, respectively. A digraph D is called regular, if there is a number p ∈ ℕ such that d ⁺(x) = d ⁻(x) = p for all vertices x of D. A c-partite tournament is an orientation of a complete c-partite graph. There are many results about directed cycles of a given length or of directed cycles with vertices from a given number of partite sets. The idea is now to combine the two properties. In this article, we examine in particular, whether c-partite tournaments with r vertices in each partite set contain a cycle with exactly r − 1 vertices of every partite set. In 1982, Beineke and Little [2] solved this problem for the regular case if c = 2. If c ⩾ 3, then we will show that a regular c-partite tournament with r ⩾ 2 vertices in each partite set contains a cycle with exactly r − 1 vertices from each partite set, with the exception of the case that c = 4 and r = 2.     

k-强竞赛图中外弧泛5顶点的数目

称具有n≥3个顶点的强竞赛图T中的一条弧是泛k的,如果对所有的k≤l≤n来说,它属于每个l-圈.本文证明了每个s-强(s≥4)竞赛图至少包含s+2个顶点使得它们的所有外弧都是泛5的.     

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     

Quasi‐carousel tournaments

A tournament is called locally transitive if the outneighborhood and the inneighborhood of every vertex are transitive. Equivalently, a tournament is locally transitive if it avoids the tournaments W₄ and L₄, which are the only tournaments up to isomorphism on four vertices containing a unique 3‐cycle. On the other hand, a sequence of tournaments  with  is called almost balanced if all but  vertices of  have outdegree . In the same spirit of quasi‐random properties, we present several characterizations of tournament sequences that are both almost balanced and asymptotically locally transitive in the sense that the density of W₄ and L₄ in  goes to zero as n goes to infinity.     

A local structure theorem on 5‐connected graphs

An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let x be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from x is two or less, then either there are two triangles with x in common each of which has a distinct degree five vertex other than x, or there is a specified structure called a K₄^?‐configuration with center x. As a corollary, we show that if a 5‐connected graph on n vertices has no contractible edges, then it has 2n/5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009     

The Average Degree of Minimally Contraction‐Critically 5‐Connected Graphs

An edge of a 5‐connected graph is said to be 5‐removable (resp. 5‐contractible) if the removal (resp. the contraction) of the edge results in a 5‐connected graph. A 5‐connected graph with neither 5‐removable edges nor 5‐contractible edges is said to be minimally contraction‐critically 5‐connected. We show the average degree of every minimally contraction‐critically 5‐connected graph is less than . This bound is sharp in the sense that for any positive real number ε, there is a minimally contraction‐critically 5‐connected graph whose average degree is greater than .