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.     

Arc‐Disjoint Cycles and Feedback Arc Sets

Isaak posed the following problem. Suppose T is a tournament having a minimum feedback arc set, which induces an acyclic digraph with a hamiltonian path. Is it true that the maximum number of arc‐disjoint cycles in T equals the cardinality of minimum feedback arc set of T? We prove that the answer to the problem is in the negative.     

A Tighter Erdős‐Pósa Function for Long Cycles

We prove that there exists a bivariate function f with such that for every natural k and ?, every graph G has at least k vertex‐disjoint cycles of length at least ? or a set of at most vertices that meets all cycles of length at least ?. This improves a result by Birmelé et al. (Combinatorica, 27 (2007), 135–145), who proved the same result with .     

Quadratic Upper Bounds on the Erdős–Pósa Property for a Generalization of Packing and Covering Cycles

According to the classical Erd?s–Pósa theorem, given a positive integer k, every graph G either contains k vertex disjoint cycles or a set of at most vertices that hits all its cycles. Robertson and Seymour (J Comb Theory Ser B 41 (1986), 92–114) generalized this result in the best possible way. More specifically, they showed that if is the class of all graphs that can be contracted to a fixed planar graph H, then every graph G either contains a set of k vertex‐disjoint subgraphs of G, such that each of these subgraphs is isomorphic to some graph in or there exists a set S of at most vertices such that contains no subgraph isomorphic to any graph in . However, the function f is exponential. In this note, we prove that this function becomes quadratic when consists all graphs that can be contracted to a fixed planar graph . For a fixed c, is the graph with two vertices and parallel edges. Observe that for this corresponds to the classical Erd?s–Pósa theorem.     

A Dirac Type Condition for Properly Coloured Paths and Cycles

Let c be an edge‐colouring of a graph G such that for every vertex v there are at least different colours on edges incident to v. We prove that G contains a properly coloured path of length 2d or a properly coloured cycle of length at least . Moreover, if G does not contain any properly coloured cycle, then there exists a properly coloured path of length .     

Arc‐Disjoint Directed and Undirected Cycles in Digraphs

The dicycle transversal number of a digraph D is the minimum size of a dicycle transversal of D, that is a set of vertices of D, whose removal from D makes it acyclic. An arc a of a digraph D with at least one cycle is a transversal arc if a is in every directed cycle of D (making acyclic). In [3] and [4], we completely characterized the complexity of following problem: Given a digraph D, decide if there is a dicycle B in D and a cycle C in its underlying undirected graph such that . It turns out that the problem is polynomially solvable for digraphs with a constantly bounded number of transversal vertices (including cases where ). In the remaining case (allowing arbitrarily many transversal vertices) the problem is NP‐complete. In this article, we classify the complexity of the arc‐analog of this problem, where we ask for a dicycle B and a cycle C that are arc‐disjoint, but not necessarily vertex‐disjoint. We prove that the problem is polynomially solvable for strong digraphs and for digraphs with a constantly bounded number of transversal arcs (but possibly an unbounded number of transversal vertices). In the remaining case (allowing arbitrarily many transversal arcs) the problem is NP‐complete.     

Parity Linkage and the Erdős–Pósa Property of Odd Cycles through Prescribed Vertices in Highly Connected Graphs

We show the following for every sufficiently connected graph G , any vertex subset S of G , and given integer k : there are k disjoint odd cycles in G each containing a vertex of S or there is set X of at most vertices such that does not contain any odd cycle that contains a vertex of S . We prove this via an extension of Kawarabayashi and Reed's result about parity‐k‐linked graphs (Combinatorica 29, 215–225). From this result, it is easy to deduce several other well‐known results about the Erd?s–Pósa property of odd cycles in highly connected graphs. This strengthens results due to Thomassen (Combinatorica 21, 321–333), and Rautenbach and Reed (Combinatorica 21, 267–278), respectively.     

Random coloring method in the combinatorial problem of Erdős and Lovász

The work deals with a combinatorial problem of P. Erd?s and L. Lovász concerning simple hypergraphs. Let denote the minimum number of edges in an n‐uniform simple hypergraph with chromatic number at least . The main result of the work is a new asymptotic lower bound for . We prove that for large n and r satisfying the following inequality holds where . This bound improves previously known bounds for . The proof is based on a method of random coloring. We have also obtained results concerning colorings of h‐simple hypergraphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Modularity of Erdős‐Rényi random graphs

For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G. The modularity q^?(G) of the graph G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 ≤ q^?(G)<1. Modularity is at the heart of the most popular algorithms for community detection. We investigate the behaviour of the modularity of the Erd?s‐Rényi random graph G_n,p with n vertices and edge‐probability p. Two key findings are that the modularity is 1+o(1) with high probability (whp) for np up to 1+o(1) and no further; and when np ≥ 1 and p is bounded below 1, it has order (np)^?1/2 whp, in accord with a conjecture by Reichardt and Bornholdt in 2006. We also show that the modularity of a graph is robust to changes in a few edges, in contrast to the sensitivity of optimal vertex partitions.     

A Relaxed Version of the Erdős–Lovász Tihany Conjecture

The Erd?s–Lovász Tihany conjecture asserts that every graph G with ) contains two vertex disjoint subgraphs G ₁ and G ₂ such that and . Under the same assumption on G , we show that there are two vertex disjoint subgraphs G ₁ and G ₂ of G such that (a) and or (b) and . Here, is the chromatic number of is the clique number of G , and col(G ) is the coloring number of G .     

On Hamilton cycles in Erdős‐Rényi subgraphs of large graphs

Given a graph Γ_n=(V,E) on n vertices and m edges, we define the Erd?s‐Rényi graph process with host Γ_n as follows. A permutation e₁,…,e_m of E is chosen uniformly at random, and for t ≤ m we let Γ_n,t=(V,{e₁,…,e_t}). Suppose the minimum degree of Γ_n is δ(Γ_n) ≥ (1/2+ε)n for some constant ε>0. Then with high probability (An event holds with high probability (whp) if as n→∞.), Γ_n,t becomes Hamiltonian at the same moment that its minimum degree reaches 2. Given 0 ≤ p ≤ 1 let Γ_n,p be the Erd?s‐Rényi subgraph of Γ_n, obtained by retaining each edge independently with probability p. When δ(Γ_n) ≥ (1/2+ε)n, we provide a threshold for Hamiltonicity in Γ_n,p.     

On a generalization of a theorem of Erdős and Fuchs

Let A={a₁,a₂,…}(a₁<a₂<) be an infinite sequence of nonnegative integers, let k≥2 be a fixed integer and denote by r_k(A,n) the number of solutions of a_i1+a_i2++a_ik≤n. Montgomery and Vaughan proved that r₂(A,n)=cn+o(n^1/4) cannot hold for any constant c>0. In this paper, we extend this result to k>2.     

On a Conjecture of Erdős,Gallai, and Tuza

Erd?s, Gallai, and Tuza posed the following problem: given an n‐vertex graph G, let denote the smallest size of a set of edges whose deletion makes G triangle‐free, and let denote the largest size of a set of edges containing at most one edge from each triangle of G. Is it always the case that ? We have two main results. We first obtain the upper bound , as a partial result toward the Erd?s–Gallai–Tuza conjecture. We also show that always , where m is the number of edges in G; this bound is sharp in several notable cases.     

Two Questions of Erdős on Hypergraphs above the Turán Threshold

For ordinary graphs it is known that any graph G with more edges than the Turán number of must contain several copies of , and a copy of , the complete graph on vertices with one missing edge. Erd?s asked if the same result is true for , the complete 3‐uniform hypergraph on s vertices. In this note, we show that for small values of n, the number of vertices in G, the answer is negative for . For the second property, that of containing a , we show that for the answer is negative for all large n as well, by proving that the Turán density of is greater than that of .     

Generalization of a theorem of Erdős and Rényi on Sidon sequences

Erd?s and Rényi claimed and Vu proved that for all h ≥ 2 and for all ? > 0, there exists g = g_h(?) and a sequence of integers A such that the number of ordered representations of any number as a sum of h elements of A is bounded by g, and such that |A ∩ [1,x]| ? x^1/h‐?. We give two new proofs of this result. The first one consists of an explicit construction of such a sequence. The second one is probabilistic and shows the existence of such a g that satisfies g_h(?) ? ?^?1, improving the bound g_h(?) ? ?^?h+1 obtained by Vu. Finally we use the “alteration method” to get a better bound for g₃(?), obtaining a more precise estimate for the growth of B₃[g] sequences. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Powers of Hamiltonian cycles in randomly augmented graphs

We study the existence of powers of Hamiltonian cycles in graphs with large minimum degree to which some additional edges have been added in a random manner. It follows from the theorems of Dirac and of Komlós, Sarközy, and Szemerédi that for every k ≥ 1 and sufficiently large n already the minimum degree for an n‐vertex graph G alone suffices to ensure the existence of a kth power of a Hamiltonian cycle. Here we show that under essentially the same degree assumption the addition of just O(n) random edges ensures the presence of the (k + 1)st power of a Hamiltonian cycle with probability close to one.     

On a problem of Duke–Erdős–Rödl on cycle-connected subgraphs

In this short note, we prove that for β<1/5 every graph G with n vertices and n^2−β edges contains a subgraph G^′ with at least cn^2−2β edges such that every pair of edges in G^′ lie together on a cycle of length at most 8. Moreover edges in G^′ which share a vertex lie together on a cycle of length at most 6. This result is best possible up to the constant factor and settles a conjecture of Duke, Erdős, and Rödl.     

一类直径为2的极大平面图的Mostar指数

图G的Mostar指数定义为Mo(G)=∑uv∈Ε(G)|nu-nv|,其中nu表示在G中到顶点u的距离比到顶点v的距离近的顶点个数,nv表示到顶点v的距离比到顶点u的距离近的顶点个数.若一个图G的任两点之间的距离至多为2,且不是完全图,则称G是一个直径为2的图.已知直径为2点数至少为4的极大平面图的最小度为3或4.本文研究了直径为2且最小度为4的极大平面图的Mostar指数.具体说,若G是一个点数为n,直径为2,最小度为4的极大平面图,则(1)当n≤12时,Mostar指数被完全确定;(2)当n≥13时,4/3n2-44/3n+94/3≤Mo(G)≤2n2-16n+24,且达到上,下界的极图同时被找到.     

On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph

The Erd?s‐Rényi and Projective Norm graphs are algebraically defined graphs that have proved useful in supplying constructions in extremal graph theory and Ramsey theory. Their eigenvalues have been computed and this yields an upper bound on their independence number. Here we show that in many cases, this upper bound is sharp in the order of magnitude. Our result for the Erd?s‐Rényi graph has the following reformulation: the maximum size of a family of mutually non‐orthogonal lines in a vector space of dimension three over the finite field of order q is of order q^3/2. We also prove that every subset of vertices of size greater than q^2/2 + q^3/2 + O(q) in the Erd?s‐Rényi graph contains a triangle. This shows that an old construction of Parsons is asymptotically sharp. Several related results and open problems are provided. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 113–127, 2007