On the number of paths and cycles for almost all graphs and digraphs

In this paper it is deduced the number ofs-paths (s-cycles) havingk edges in common with a fixeds-path (s-cycle) of the complete graphK _n (orK* _n for directed graphs). It is also proved that the number of the common edges of twos-path (s-cycles) randomly chosen from the set ofs-paths (s-cycles) ofK _n (respectivelyK* _n ), are random variables, distributed asymptotically in accordance with the Poisson law whenever s/n exists, thus extending a result by Baróti. Some estimations of the numbers of paths and cycles for almost all graphs and digraphs are made by applying Chebyshev’s inequality.     

Properly coloured Hamiltonian cycles in edge-coloured complete graphs

Let K ^c _n be an edge-coloured complete graph on n vertices. Let Δ_mon(K^c _n) denote the largest number of edges of the same colour incident with a vertex of K^c _n. A properly coloured cycleis a cycle such that no two adjacent edges have the same colour. In 1976, BollobÁs and Erd?s[6] conjectured that every K^c _n with Δ_mon(K^c _n)<?n/2?contains a properly coloured Hamiltonian cycle. In this paper, we show that for any ε>0, there exists an integer n₀ such that every K^c _n with Δ_mon(K^c _n)<(1/2–ε)n and n≥n₀ contains a properly coloured Hamiltonian cycle. This improves a result of Alon and Gutin [1]. Hence, the conjecture of BollobÁs and Erd?s is true asymptotically.     

Stability for large forbidden subgraphs

In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:

• (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:
  • (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/3+c^1/(3r+3))n² edges.
  Letting µ(G) be the spectral radius of G, we prove also a spectral stability theorem: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with µ(G)>(1?1/r?ε)n satisfies one of the conditions:
  • (a) G contains a $K_{r+1}(\lfloor c\,\mbox{ln}\,n\rfloor,\ldots,\lfloor c\,\mbox{ln}\,n\rfloor,\lceil n^{1-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/4+c^1/(8r+8))n² edges.
  © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 362–368, 2009     

Complete subgraphs with large degree sums

Let t(n, k) denote the Turán number—the maximum number of edges in a graph on n vertices that does not contain a complete graph K_k+1. It is shown that if G is a graph on n vertices with n ≥ k²(k – 1)/4 and m < t(n, k) edges, then G contains a complete subgraph K_k such that the sum of the degrees of the vertices is at least 2km/n. This result is sharp in an asymptotic sense in that the sum of the degrees of the vertices of K_k is not in general larger, and if the number of edges in G is at most t(n, k) – ? (for an appropriate ?), then the conclusion is not in general true. © 1992 John Wiley & Sons, Inc.     

Topological minors in bipartite graphs

For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s and t such that 2 ≤ s ≤ t, 0 ≤ m − s ≤ n − t, and m + n ≤ 2s + t − 1, we prove that if G has at least mn − (2(m − s) + n − t) edges then it contains a subdivision of the complete bipartite K _(s,t) with s vertices in the m-class and t vertices in the n-class. Furthermore, we characterize the corresponding extremal bipartite graphs with mn − (2(m − s) + n − t + 1) edges for this topological Turan type problem.     

The early evolution of the H-free process

The H-free process, for some fixed graph H, is the random graph process defined by starting with an empty graph on n vertices and then adding edges one at a time, chosen uniformly at random subject to the constraint that no H subgraph is formed. Let G be the random maximal H-free graph obtained at the end of the process. When H is strictly 2-balanced, we show that for some c>0, with high probability as n→∞, the minimum degree in G is at least cn^{1-(v_H-2)/(e_H-1)}(logn)^1/(e_H-1)cn^{1-(v_{H}-2)/(e_{H}-1)}(\log n)^{1/(e_{H}-1)}. This gives new lower bounds for the Turán numbers of certain bipartite graphs, such as the complete bipartite graphs K _r,r with r≥5. When H is a complete graph K _s with s≥5 we show that for some C>0, with high probability the independence number of G is at most Cn^2/(s+1)(logn)^1-1/(e_H-1)Cn^{2/(s+1)}(\log n)^{1-1/(e_{H}-1)}. This gives new lower bounds for Ramsey numbers R(s,t) for fixed s≥5 and t large. We also obtain new bounds for the independence number of G for other graphs H, including the case when H is a cycle. Our proofs use the differential equations method for random graph processes to analyse the evolution of the process, and give further information about the structure of the graphs obtained, including asymptotic formulae for a broad class of subgraph extension variables.     

Partitioning complete graphs by heterochromatic trees

A heterochromatic tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by t _r (G), is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we determine the heterochromatic tree partition number of r-edge-colored complete graphs. We also find at most t _r (K _n ) vertex-disjoint heterochromatic trees to cover all the vertices in polynomial time for a given r-edge-coloring of K _n .     

Almost Resolvable Maximum Packings of Complete Graphs with 4-Cycles

If the complete graph K _n has vertex set X, a maximum packing of K _n with 4-cycles, (X, C, L), is an edge-disjoint decomposition of K _n into a collection C of 4-cycles so that the unused edges (the set L) is as small a set as possible. Maximum packings of K _n with 4-cycles were shown to exist by Sch?nheim and Bialostocki (Can. Math. Bull. 18:703–708, 1975). An almost parallel class of a maximum packing (X, C, L) of K _n with 4-cycles is a largest possible collection of vertex disjoint 4-cycles (so with ?/4?{\lfloor/4\rfloor} 4-cycles in it). In this paper, for all orders n, except 9, which does not exist, and possibly 23, 41 and 57, we exhibit a maximum packing of K _n with 4-cycles so that the 4-cycles in the packing are resolvable into almost parallel classes, with any remaining 4-cycles being vertex disjoint. [Note: The three missing orders have now been found, and appear in Billington et al. (to appear).]     

Large Kr‐free subgraphs in Ks‐free graphs and some other Ramsey‐type problems

In this paper we present three Ramsey‐type results, which we derive from a simple and yet powerful lemma, proved using probabilistic arguments. Let 3 ≤ r < s be fixed integers and let G be a graph on n vertices not containing a complete graph K_s on s vertices. More than 40 years ago Erd?s and Rogers posed the problem of estimating the maximum size of a subset of G without a copy of the complete graph K_r. Our first result provides a new lower bound for this problem, which improves previous results of various researchers. It also allows us to solve some special cases of a closely related question posed by Erd?s. For two graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any red‐blue coloring of the edges of the complete graph K_N, contains either a red copy of G or a blue copy of H. The book with n pages is the graph B_n consisting of n triangles sharing one edge. Here we study the book‐complete graph Ramsey numbers and show that R(B_n, K_n) ≤ O(n³/log^3/2n), improving the bound of Li and Rousseau. Finally, motivated by a question of Erd?s, Hajnal, Simonovits, Sós, and Szemerédi, we obtain for all 0 < δ < 2/3 an estimate on the number of edges in a K₄‐free graph of order n which has no independent set of size n^1‐δ. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

A generalization of Turán's theorem

In this paper, we obtain an asymptotic generalization of Turán's theorem. We prove that if all the non‐trivial eigenvalues of a d‐regular graph G on n vertices are sufficiently small, then the largest K_t‐free subgraph of G contains approximately (t ? 2)/(t ? 1)‐fraction of its edges. Turán's theorem corresponds to the case d = n ? 1. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Identity orientation of complete bipartite graphs

An identity orientation of a graph G=(V,E) is an orientation of some of the edges of E such that the resulting partially oriented graph has no automorphism other than the identity. We show that the complete bipartite graph K_s,t, with st, does not have an identity orientation if t3^s-log₃(s-1). We also show that if (r+1)(r+2)2s then K_s,3^s-r does have an identity orientation. These results improve the previous bounds obtained by Harary and Jacobson (Discuss. Math. - Graph Theory 21 (2001) 158). We use these results to determine exactly the values of t for which an identity orientation of K_s,t exists for 2s17.     

On the number of edge disjoint cliques in graphs of given size

In this paper, we prove that any graph ofn vertices andt _r–1(n)+m edges, wheret _r–1(n) is the Turán number, contains (1–o(1)m edge disjointK _r'sifm=o(n ²). Furthermore, we determine the maximumm such that every graph ofn vertices andt _r–1(n)+m edges containsm edge disjointK _r's ifn is sufficiently large.Research partially supported by Hungarian National Foundation for Scientific Research Grant no. 1812.     

The inducibility of complete bipartite graphs

For any s ≥ 1 and t ≥ (^S₂), we prove that among all graphs with n vertices the graph that contains the maximal number of induced copies of K_{t, t+s} for any fixed s ≥ 1 and t ≥ (^s₂) is K_{(n/2)+α(n/2)-α} for some function α = o(n). We show that this is not valid for t < (^s₂). Analogous results for complete multipartite graphs are also obtained.     

Constrained Ramsey numbers of graphs

Given two graphs G and H, let f(G,H) denote the minimum integer n such that in every coloring of the edges of K_n, there is either a copy of G with all edges having the same color or a copy of H with all edges having different colors. We show that f(G,H) is finite iff G is a star or H is acyclic. If S and T are trees with s and t edges, respectively, we show that 1+s(t?2)/2≤f(S,T)≤(s?1)(t²+3t). Using constructions from design theory, we establish the exact values, lying near (s?1)(t?1), for f(S,T) when S and T are certain paths or star‐like trees. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 1–16, 2003     

Recursive construction for 3-regular expanders

We present an algorithm which inn ³ (logn)³ time constructs a 3-regular expander graph onn vertices. In each step we substitute a pair of edges of the graph by a new pair of edges so that the total number of cycles of lengths=clogn decreases (for some fixed absolute constantc). When we reach a local minimum in the number of cycles of lengths the graph is an expander.     

The Bohman‐Frieze process near criticality

The Erd?s‐Rényi process begins with an empty graph on n vertices, with edges added randomly one at a time to the graph. A classical result of Erd?s and Rényi states that the Erd?s‐Rényi process undergoes a phase transition, which takes place when the number of edges reaches n/2 (we say at time 1) and a giant component emerges. Since this seminal work of Erd?s and Rényi, various random graph models have been introduced and studied. In this paper we study the Bohman‐Frieze process, a simple modification of the Erd?s‐Rényi process. The Bohman‐Frieze process also begins with an empty graph on n vertices. At each step two random edges are presented, and if the first edge would join two isolated vertices, it is added to a graph; otherwise the second edge is added. We present several new results on the phase transition of the Bohman‐Frieze process. We show that it has a qualitatively similar phase transition to the Erd?s‐Rényi process in terms of the size and structure of the components near the critical point. We prove that all components at time t_c ? ? (that is, when the number of edges are (t_c ? ?)n/2) are trees or unicyclic components and that the largest component is of size Ω(?^‐2log n). Further, at t_c + ?, all components apart from the giant component are trees or unicyclic and the size of the second‐largest component is Θ(?^‐2log n). Each of these results corresponds to an analogous well‐known result for the Erd?s‐Rényi process. Our proof techniques include combinatorial arguments, the differential equation method for random processes, and the singularity analysis of the moment generating function for the susceptibility, which satisfies a quasi‐linear partial differential equation. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

On the Ramsey-Turán numbers of graphs and hypergraphs

Let t be an integer, f(n) a function, and H a graph. Define the t-Ramsey-Turán number of H, RT _t (n,H, f(n)), to be the maximum number of edges in an n-vertex, H-free graph G with α _t (G) ≤ f(n), where α _t (G) is the maximum number of vertices in a K _t -free induced subgraph of G. Erd?s, Hajnal, Simonovits, Sós and Szemerédi [6] posed several open questions about RT _t (n,K _s , o(n)), among them finding the minimum ? such that RT _t (n,K _t+? , o(n)) = Ω(n ²), where it is easy to see that RT _t (n,K _t+1, o(n)) = o(n ²). In this paper, we answer this question by proving that RT _t (n,K _t+2, o(n)) = Ω(n ²); our constructions also imply several results on the Ramsey-Turán numbers of hypergraphs.     

The Ramsey number R(3, t) has order of magnitude t2/log t

The Ramsey number R(s, t) for positive integers s and t is the minimum integer n for which every red-blue coloring of the edges of a complete n-vertex graph induces either a red complete graph of order s or a blue complete graph of order t. This paper proves that R(3, t) is bounded below by (1 – o(1))t/²/log t times a positive constant. Together with the known upper bound of (1 + o(1))t²/log t, it follows that R(3, t) has asymptotic order of magnitude t²/log t. © 1995 John Wiley & Sons, Inc.     

On the structure of linear graphs

Denote byG(n; m) a graph ofn vertices andm edges. We prove that everyG(n; [n ²/4]+1) contains a circuit ofl edges for every 3 ≦l<c ₂ n, also that everyG(n; [n ²/4]+1) contains ak _e(u _n, u_n) withu _n=[c ₁ logn] (for the definition ofk _e(u _n, u_n) see the introduction). Finally fort>t ₀ everyG(n; [tn ^3/2]) contains a circuit of 2l edges for 2≦l<c ₃ t ². This work was done while the author received support from the National Science Foundation, N.S.F. G.88.     

Ramsey Numbers of Some Bipartite Graphs Versus Complete Graphs

The Ramsey number r(H, K _n ) is the smallest positive integer N such that every graph of order N contains either a copy of H or an independent set of size n. The Turán number ex(m, H) is the maximum number of edges in a graph of order m not containing a copy of H. We prove the following two results: (1) Let H be a graph obtained from a tree F of order t by adding a new vertex w and joining w to each vertex of F by a path of length k such that any two of these paths share only w. Then r(H,K_n) ￡ c_k,t [(n^1+1/k)/(ln^1/k n)]{r(H,K_n)\leq c_{k,t}\, {n^{1+1/k}\over \ln^{1/k} n}} , where c _k,t is a constant depending only on k and t. This generalizes some results in Li and Rousseau (J Graph Theory 23:413–420, 1996), Li and Zang (J Combin Optim 7:353–359, 2003), and Sudakov (Electron J Combin 9, N1, 4 pp, 2002). (2) Let H be a bipartite graph with ex(m, H) = O(m ^γ ), where 1 < γ < 2. Then r(H,K_n) ￡ c_H ([(n)/(lnn)])^1/(2-g){r(H,K_n)\leq c_H ({n\over \ln n})^{1/(2-\gamma)}}, where c _H is a constant depending only on H. This generalizes a result in Caro et al. (Discrete Math 220:51–56, 2000).