A vertex cover with chorded 4-cycles

Let k be an integer with k ≥ 2 and G a graph with order n > 4k. We prove that if the minimum degree sum of any two nonadjacent vertices is at least n + k, then G contains a vertex cover with exactly k components such that k−1 of them are chorded 4-cycles. The degree condition is sharp in general.     

Digraphs containing every possible pair of dicycles

Let D = (V, A) be a directed graph of order n ≥ 4. Suppose that the minimum degree of D is at least (3n − 3)/2. Then for any two integers s and t with s ≥ 2, t ≥ 2 and s + t ≤ n, D contains two vertex‐disjoint directed cycles of lengths s and t, respectively. Moreover, the condition on the minimum degree is sharp. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 154–162, 2000     

Vertex‐disjoint cycles of length at most four each of which contains a specified vertex*

We obtain a sharp minimum degree condition δ (G) ≥ of a graph G of order n ≥ 3k guaranteeing that, for any k distinct vertices, G contains k vertex‐disjoint cycles of length at most four each of which contains one of the k prescribed vertices. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 37–47, 2001     

Cycles in 2-Factors of Balanced Bipartite Graphs

In the study of hamiltonian graphs, many well known results use degree conditions to ensure sufficient edge density for the existence of a hamiltonian cycle. Recently it was shown that the classic degree conditions of Dirac and Ore actually imply far more than the existence of a hamiltonian cycle in a graph G, but also the existence of a 2-factor with exactly k cycles, where . In this paper we continue to study the number of cycles in 2-factors. Here we consider the well-known result of Moon and Moser which implies the existence of a hamiltonian cycle in a balanced bipartite graph of order 2n. We show that a related degree condition also implies the existence of a 2-factor with exactly k cycles in a balanced bipartite graph of order 2n with . Revised: May 7, 1999     

Vertex‐disjoint cycles containing prescribed vertices

Enomoto 7 conjectured that if the minimum degree of a graph G of order n ≥ 4k ? 1 is at least the integer , then for any k vertices, G contains k vertex‐disjoint cycles each of which contains one of the k specified vertices. We confirm the conjecture for n ≥ ck² where c is a constant. Furthermore, we show that under the same condition the cycles can be chosen so that each has length at most six. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 276–296, 2003     

Pentagons and cycle coverings

Let G be a graph of order n ≥ 5k + 2, where k is a positive integer. Suppose that the minimum degree of G is at least ?(n + k)/2?. We show that G contains k pentagons and a path such that they are vertex‐disjoint and cover all the vertices of G. Moreover, if n ≥ 5k + 7, then G contains k + 1 vertex‐disjoint cycles covering all the vertices of G such that k of them are pentagons. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 194–208, 2007     

Edge-disjoint cycles in regular directed graphs

We prove that any k-regular directed graph with no parallel edges contains a collection of at least O(k²) edge-disjoint cycles; we conjecture that in fact any such graph contains a collection of at least (^k+1₂) disjoint cycles, and note that this holds for k ≤ 3. © 1996 John Wiley & Sons, Inc.     

Half-integral packing of odd cycles through prescribed vertices

The well-known theorem of Erd?s-Pósa says that a graph G has either k disjoint cycles or a vertex set X of order at most f(k) for some function f such that G\X is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization. In this paper, we discuss packing disjoint S-cycles, i.e., cycles that are required to go through a set S of vertices. For this problem, Kakimura-Kawarabayashi-Marx (2011) and Pontecorvi-Wollan (2010) recently showed the Erd?s-Pósa-type result holds. We further try to generalize this result to packing S-cycles of odd length. In contrast to packing S-cycles, the Erd?s-Pósa-type result does not hold for packing odd S-cycles. We then relax packing odd S-cycles to half-integral packing, and show the Erd?s-Pósa-type result for the half-integral packing of odd S-cycles, which is a generalization of Reed (1999) when S=V. That is, we show that given an integer k and a vertex set S, a graph G has either 2k odd S-cycles so that each vertex is in at most two of these cycles, or a vertex set X of order at most f(k) (for some function f) such that G\X has no odd S-cycle.     

Edge disjoint cycles in graphs

Ore proved in 1960 that if G is a graph of order n and the sum of the degrees of any pair of nonadjacent vertices is at least n, then G has a hamiltonian cycle. In 1986, Li Hao and Zhu Yongjin showed that if n ? 20 and the minimum degree δ is at least 5, then the graph G above contains at least two edge disjoint hamiltonian cycles. The result of this paper is that if n ? 2δ², then for any 3 ? l₁ ? l₂ ? ? ? l_k ? n, 1 = k = [(δ - 1)/2], such graph has K edge disjoint cycles with lengths l₁, l₂…l_k, respectively. In particular, when l₁ = l₂ = ? = l_k = n and k = [(δ - 1)/2], the graph contains [(δ - 1)/2] edge disjoint hamiltonian cycles.     

A Minimum Degree Result for Disjoint Cycles and Forests in Graphs

F on s edges and k disjoint cycles. The main result is the following theorem. Let F be a forest on s edges without isolated vertices and let G be a graph of order at least with minimum degree at least , where k, s are nonnegative integers. Then G contains the disjoint union of the forest F and k disjoint cycles. This theorem provides a common generalization of previous results of Corrádi & Hajnal [4] and Brandt [3] who considered the cases (cycles only) and (forests only), respectively. Received: October 13, 1995     

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).]     

Vertex disjoint equivalent subgraphs of order 3

Let k be a fixed integer at least 3. It is proved that every graph of order (2k ? 1 ? 1/k)n + O(1) contains n vertex disjoint induced subgraphs of order k such that these subgraphs are equivalent to each other and they are equivalent to one of four graphs: a clique, an independent set, a star, or the complement of a star. In particular, by substituting 3 for k, it is proved that every graph of order 14n/3 + O(1) contains n vertex disjoint induced subgraphs of order 3 such that they are equivalent to each other. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 159–166, 2007     

Vertex-Disjoint Cycles Containing Specified Edges

Dirac and Ore-type degree conditions are given for a graph to contain vertex disjoint cycles each of which contains a previously specified edge. One set of conditions is given that imply vertex disjoint cycles of length at most 4, and another set of conditions are given that imply the existence of cycles that span all of the vertices of the graph (i.e. a 2-factor). The conditions are shown to be sharp and give positive answers to conjectures of Enomoto in [3] and Wang in [5]. Revised: July 28, 1999     

Subdivisions of graphs: A generalization of paths and cycles

One of the basic results in graph theory is Dirac's theorem, that every graph of order n?3 and minimum degree ?n/2 is Hamiltonian. This may be restated as: if a graph of order n and minimum degree ?n/2 contains a cycle C then it contains a spanning cycle, which is just a spanning subdivision of C. We show that the same conclusion is true if instead of C, we choose any graph H such that every connected component of H is non-trivial and contains at most one cycle. The degree bound can be improved to (n-t)/2 if H has t components that are trees.We attempt a similar generalization of the Corrádi-Hajnal theorem that every graph of order ?3k and minimum degree ?2k contains k disjoint cycles. Again, this may be restated as: every graph of order ?3k and minimum degree ?2k contains a subdivision of kK₃. We show that if H is any graph of order n with k components, each of which is a cycle or a non-trivial tree, then every graph of order ?n and minimum degree ?n-k contains a subdivision of H.     

Disjoint cliques in claw-free graphs

A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K_1,3. Let s and k be two integers with 0 ≤ s ≤ k and let G be a claw-free graph of order n. In this paper, we investigate clique partition problems in claw-free graphs. It is proved that if n ≥ 3s+4(k?s) and d(x)+d(y) ≥ n?2s+2k+1 for any pair of non-adjacent vertices x, y of G, then G contains s disjoint K₃s and k ? s disjoint K₄s such that all of them are disjoint. Moreover, the degree condition is sharp in some cases.     

Disjoint chorded cycles in graphs

We propose the following conjecture to generalize results of Pósa and of Corrádi and Hajnal. Let r,s be nonnegative integers and let G be a graph with |V(G)|≥3r+4s and minimal degree δ(G)≥2r+3s. Then G contains a collection of r+s vertex disjoint cycles, s of them with a chord. We prove the conjecture for r=0,s=2 and for s=1. The corresponding extremal problem, to find the minimum number of edges in a graph on n vertices ensuring the existence of two vertex disjoint chorded cycles, is also settled.     

Lengths of cycles in halin graphs

A Halin graph is a plane graph H = T U C, where T is a plane tree with no vertex of degree two and at least one vertex of degree three or more, and C is a cycle connecting the endvertices of T in the cyclic order determined by the embedding of T. We prove that such a graph on n vertices contains cycles of all lengths l, 3 ≤ l n, except, possibly, for one even value m of l. We prove also that if the tree T contains no vertex of degree three then G is pancyclic.     

The generalized almost resolvable cycle system problem

Let (X, C) be a k-cycle system of order n, with vertex set X (of cardinality n) and collection of k-cycles C. Suppose n=kq+r where r<k. An almost parallel class of C is a collection of q=(n−r)/k pairwise vertex-disjoint k-cycles of C. Each almost parallel class thus will miss r of the n vertices in X. The k-cycle system (X,C) is said to be almost resolvable if C can be partitioned into almost parallel classes such that the remaining k-cycles are vertex disjoint. (These remaining k-cycles are referred to as a short parallel class.)     

Infinite paths in planar graphs IV,dividing cycles

Nash‐Williams conjectured that a 4‐connected infinite planar graph contains a spanning 2‐way infinite path if, and only if, the deletion of any finite set of vertices results in at most two infinite components. In this article, we prove this conjecture for graphs with no dividing cycles and for graphs with infinitely many vertex disjoint dividing cycles. A cycle in an infinite plane graph is called dividing if both regions of the plane bounded by this cycle contain infinitely many vertices of the graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 173–195, 2006     

The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻_n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s₁,…,s_k,t₁,…,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007