Maximum matchings in a regular graph of specified connectivity and bounded order

Upper bounds are placed on the order of a k-regular m-connected graph G that produce a lower bound on the number of independent edges in G. As a corollary, we obtain the order of a smallest k-regular m-connected graph which has no 1-factor.     

Closure, 2-factors,and cycle coverings in claw-free graphs

In this article, we study cycle coverings and 2-factors of a claw-free graph and those of its closure, which has been defined by the first author (On a closure concept in claw-free graphs, J Combin Theory Ser B 70 (1997), 217–224). For a claw-free graph G and its closure cl(G), we prove: (1) V(G) is covered by k cycles in G if and only if V(cl(G)) is covered by k cycles of cl(G); and (2) G has a 2-factor with at most k components if and only if cl(G) has a 2-factor with at most k components. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 109–117, 1999     

Independence number,connectivity, and r-factors

We show that if r ? 1 is an odd integer and G is a graph with |V(G)| even such that k(G) ? (r + 1)²/2 and (r + 1)²α(G) ? 4rk(G), then G has an r-factor; if r ? 2 is even and G is a graph with k(G) ? r(r + 2)/2 and (r + 2)α(G) ? 4k(G), then G has an r-factor (where k(G) and α(G) denote the connectivity and the independence number of G, respectively).     

Toughness and the existence of k-factors

A connected graph G is called t-tough if t · w(G - S) ? |S| for any subset S of V(G) with w(G - S) > 1, where w(G - S) is the number of connected components of G - S. We prove that every k-tough graph has a k-factor if k|G| is even and |G| ? k + 1. This result, first conjectured by Chvátal, is sharp in the following sense: For any positive integer k and for any positive real number ε, there exists a (k - ε)-tough graph G with k|G| even and |G| ? k + 1 which has no k-factor.     

Binding number and minimum degree for k-factors

In this paper, we study mixed conditions on the binding number and the minimum degree of a graph G that guarantee the existence of a k-factor in G. Among others, we prove that a graph G of order n with δ(G) ? cn and bind(G) > (2 ? 3c)/(1 ? c), where c is any fixed number, has a 2-factor.     

<Emphasis Type="Italic">k</Emphasis>-factors in regular graphs

Plesnik in 1972 proved that an （m - 1）-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular （2n ＋ 1）-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and （or） excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik＇s result and the results obtained by Liu et al. in 1998, and improve Katerinis＇ result obtained 1993. Furthermore, we show that the results in this paper are the best possible.     

A degree condition for the existence of k-factors

Let k be an integer such that ≦, and let G be a connected graph of order n with ≦, kn even, and minimum degree at least k. We prove that if G satisfies max(deg(u), deg(v)) ≦ n/2 for each pair of nonadjacent vertices u, v in G, then G has a k-factor.     

Degree conditions for 2-factors

For any positive integer k, we investigate degree conditions implying that a graph G of order n contains a 2-factor with exactly k components (vertex disjoint cycles). In particular, we prove that for k ≤ (n/4), Ore's classical condition for a graph to be hamiltonian (k = 1) implies that the graph contains a 2-factor with exactly k components. We also obtain a sufficient degree condition for a graph to have k vertex disjoint cycles, at least s of which are 3-cycles and the remaining are 4-cycles for any s ≤ k. © 1997 John Wiley & Sons, Inc.     

(3,k)-Factor-Critical Graphs and Toughness

 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and k≤n−7. Revised: September 21, 1998     

Obstacle Numbers of Graphs

An obstacle representation of a graph G is a drawing of G in the plane with straight-line edges, together with a set of polygons (respectively, convex polygons) called obstacles, such that an edge exists in G if and only if it does not intersect an obstacle. The obstacle number (convex obstacle number) of G is the smallest number of obstacles (convex obstacles) in any obstacle representation of G. In this paper, we identify families of graphs with obstacle number 1 and construct graphs with arbitrarily large obstacle number (convex obstacle number). We prove that a graph has an obstacle representation with a single convex k-gon if and only if it is a circular arc graph with clique covering number at most k in which no two arcs cover the host circle. We also prove independently that a graph has an obstacle representation with a single segment obstacle if and only if it is the complement of an interval bigraph.     

An ore-type condition for the existence ofk-factors in graphs

Letk be a positive integer, and letG be a graph of ordern withn 4k – 5,kn even and minimum degree at leastk. We prove that if the degree sum of each pair of nonadjacent vertices is at leastn, thenG has ak-factor.     

Toughness and the existence of fractional k-factors of graphs

The toughness of a graph G, t(G), is defined as t(G)=min{|S|/ω(G-S)|S⊆V(G),ω(G-S)>1} where ω(G-S) denotes the number of components of G-S or t(G)=+∞ if G is a complete graph. Much work has been contributed to the relations between toughness and the existence of factors of a graph. In this paper, we consider the relationship between the toughness and the existence of fractional k-factors. It is proved that a graph G has a fractional 1-factor if t(G)?1 and has a fractional k-factor if t(G)?k-1/k where k?2. Furthermore, we show that both results are best possible in some sense.     

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     

Hamilton decompositions of graphs with primitive complements

A k-factor of a graph is a k-regular spanning subgraph. A Hamilton cycle is a connected 2-factor. A graph G is said to be primitive if it contains no k-factor with 1≤k<Δ(G). A Hamilton decomposition of a graph G is a partition of the edges of G into sets, each of which induces a Hamilton cycle. In this paper, by using the amalgamation technique, we find necessary and sufficient conditions for the existence of a 2x-regular graph G on n vertices which:

1.

has a Hamilton decomposition, and

2.

has a complement in K_n that is primitive.

This extends the conditions studied by Hoffman, Rodger, and Rosa [D.G. Hoffman, C.A. Rodger, A. Rosa, Maximal sets of 2-factors and Hamiltonian cycles, J. Combin. Theory Ser. B 57 (1) (1993) 69-76] who considered maximal sets of Hamilton cycles and 2-factors. It also sheds light on construction approaches to the Hamilton-Waterloo problem.     

The k‐piece packing problem

A k‐piece of a graph G is a connected subgraph of G all of whose nodes have degree at most k and at least one node has degree equal to k. We consider the problem of covering the maximum number of nodes of a graph by node disjoint k‐pieces. When k = 1 this is the maximum matching problem, and when k = 2 this is the problem, recently studied by Kaneko [ 19 [, of covering the maximum number of nodes by disjoint paths of length greater than 1. We present a polynomial time algorithm for the problem as well as a Tutte‐type existence theorem and a Berge‐type min‐max formula. We also solve the problem in the more general situation where the “pieces” are defined in terms of lower and upper bounds on the degrees. © 2006 Wiley Periodicals, Inc. J Graph Theory     

On the threshold for k-regular subgraphs of random graphs

The k-core of a graph is the largest subgraph of minimum degree at least k. We show that for k sufficiently large, the threshold for the appearance of a k-regular subgraph in the Erdős-Rényi random graph model G(n,p) is at most the threshold for the appearance of a nonempty (k+2)-core. In particular, this pins down the point of appearance of a k-regular subgraph to a window for p of width roughly 2/n for large n and moderately large k. The result is proved by using Tutte’s necessary and sufficient condition for a graph to have a k-factor.     

2‐connected 7‐coverings of 3‐connected graphs on surfaces

An m‐covering of a graph G is a spanning subgraph of G with maximum degree at most m. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus k ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most 6k ? 12 vertices of degree 7. We also construct, for every surface F² with Euler genus k ≥ 2, a 3‐connected graph G on F² with arbitrarily large representativity each of whose 2‐connected 7‐coverings contains at least 6k ? 12 vertices of degree 7. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 26–36, 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     

Covering a graph with cycles

Let k and n be two integers such that k ≥ 0 and n ≥ 3(k + 1). Let G be a graph of order n with minimum degree at least ?(n + k)/2?. Then G contains k + 1 independent cycles covering all the vertices of G such that k of them are triangles. © 1995, John Wiley & Sons, Inc.     

Degree sums,k-factors and hamilton cycles in graphs

We prove (a generalization of) the following conjecture of R. Häggkvist: LetG be a 2-connected graph onn vertices where every pair of nonadjacent vertices has degree sum at leastn — k and assume thatG has ak-factor; thenG is hamiltonian. This result is a common generalization of well-known theorems of Ore and Jackson, respectively.The research for this paper was done while the second author visited Memphis State University, partly supported by a grant from the Netherlands Organization for Scientific Research (N.W.O.).