Printer Friendly

Ore and Erdos type conditions for long cycles in balanced bipartite graphs.

1 Introduction

One of the classical problems of graph theory is the study of sufficient conditions for a graph to contain a Hamilton cycle. In this paper we are primarily interested in two types of such conditions. Namely, the ones that put constraints on degree sums of pairs of non-adjacent vertices, and those that combine bounds on the size of a graph with bounds on its minimal degree. The first approach is due to Ore (see Section 2 for notation):

Theorem 1.1 (Ore, [12]). Let G be a graph of order n [greater than or equal to] 3, in which [d.sub.G](x) + [d.sub.G](y) [greater than or equal to] n

for every pair of non-adjacent vertices x and y. Then G contains a Hamilton cycle.

It follows immediately from Ore's theorem that the minimal size of a graph of order n [greater than or equal to] 3 that guarantees hamiltonicity is (n-1/2 + 2. Erdos generalized this condition by adding a bound on the minimal degree of a graph:

Theorem 1.2 (Erdos, [9]). Let G be a graph of order n [greater than or equal to] 3 and minimal degree [delta](G) [greater than or equal to] r, where 1 [less than or equal to] r < n/2. Then G contains a Hamilton cycle, provided

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

The above conditions can, of course, be significantly strengthened in case of a balanced bipartite graph. The following two theorems are bipartite counterparts of Ore and Erdos criteria, respectively.

Theorem 1.3 (Moon and Moser, [11]). Let G be a bipartite graph of order 2n, with colour classes X and Y , where |absolute value of X| = |absolute value of Y| = n [greater than or equal to] 2. Suppose that [d.sub.G](x) + [d.sub.G](y) [greater than or equal to] n + 1 for every pair of non-adjacent vertices x [member of] X and y [member of] Y . Then G contains a Hamilton cycle.

Theorem 1.4 (Moon and Moser, [11]). Let G be a bipartite graph of order 2n, with colour classes X and Y ,[absolute value of X] = [absolute value of Y] = n [greater than or equal to] 2, and minimal degree [delta](G) [greater than or equal to] r, 1 [less or equal to] r [less than or equal to] n/2. Then G contains a Hamilton cycle, provided [parallel] G [parallel] > n(n - r) + [r.sup.2].

Our goal is to generalize the above criteria to long cycles, that is, cycles of length 2n - 2k, where 0 [less than or equal to] k < n/2. We state the following two conjectures, that include Theorems 1.3 and 1.4 as special cases (k = 0).

Conjecture A. Let G be a 2-connected balanced bipartite graph of order 2n, with colour classes X and Y ,[absolute value of X] =[absolute value of Y] = n [greater than or equal to] 5, and let k < n/2 be a non-negative integer. If

[d.sub.G](x) + [d.sub.G](y) [greater than or equal to] n - k + 1

for every pair of non-adjacent x [member of] X and y [member of] Y , then G contains a cycle of length 2n - 2k.

Conjecture B. Let G be a balanced bipartite graph of order 2n and minimal degree [delta](G) [greater than or equal to] r [greater than or equal to] 1, where n [greater than or equal to] 2k + 2r and k [member of] Z. If

[parallel G [parallel] > n(n - k - r) + r(k + r)

then G contains a cycle of length 2n - 2k.

The main two results of this paper, Theorems A and B (Section 3), assert that our conjectures hold true for k = 1. We believe the conjectures to be significantly harder in case k [greater than or equal to] 2.

It should be mentioned here that analogous generalizations to long cycles of Ore's and Erdos's theorems have been studied in ordinary graphs. Woodall [14, Thm. 11] gives a complete list of Erdos type conditions for a graph of order n to contain a cycle of length n - k for any 0 [less than or equal to] k [less than or equal to] n-3/2 . The Ore type criterion is conjectured in [1], and follows from a result of Linial [10] in case k [less than or equal to] 1.

Remark 1.5. Both the degree sum condition of Conjecture A and the bound on the size of Conjecture B are sharp, as can be seen in Example 1.6 below. It is also necessary to assume 2-connectedness in Conjecture A (Example 1.7). Finally, a quick look at [C.sub.6] and [C.sub.8] shows that Conjecture A would fail for n < 5.

Example 1.6. Let [G.sub.1] be a balanced bipartite graph, with colour classes X and Y ,[absolute value of X] =[absolute value of Y] = n, where X = A [union] B, Y = C [union] D,|A| = k + r,|absolute value of b| = n - k - r,[absolute value of C] = r, and[absolute value of D] = n _ r. Moreover, assume that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for all x [member of] A, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for all x [member of] B. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for every pair x [member of] A and y [member of] D, and, in general, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for every pair of x [member of] X and y [member of] Y . If n [greater than or equal to] 2k + 2r, then [delta]([G.sub.1]) = r [greater than or equal to] 1 and [parallel] [G.sub.1] [parallel] = n(n - k - r) + r(k + r), but [G.sub.1] does not contain a cycle of length 2n - 2k.

Example 1.7. Let [G.sub.2] = (X; Y ;E) be a balanced bipartite graph obtained from the disjoint union of [H.sub.1] = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] by adding a single edge joining a vertex of H1 with a vertex of [H.sub.2]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for every pair of non-adjacent vertices x [member of] X and y [member of] Y , nonetheless G2 contains no cycle of length 2n - 2. In fact, G2 contains no long cycle whatsoever.

The next section contains the inventory of basic definitions and results used throughout the paper. In Section 3 we state our main results, Theorems A and B, and their consequences. In particular, by combining Theorems A and B, we obtain a complete Erdos type characterisation of balanced bipartite graphs that do not contain cycles of length 2n - 2 (Theorem 3.6). The last two sections are devoted to proofs of the two main results.

2 Notation and tools

All graphs considered are undirected, have no loops and no multiple edges. Given a graph G, we denote by [parallel] G [parallel] the size (i.e., number of edges) of G, and by V (G) the vertex set of G. A bipartite graph is often denoted by G = (X; Y ;E), where X and Y are the two colour classes of G, and E = E(G) is the edge set of G. When [absolute value of X] = [absolute value of Y], we say that G is balanced. Given a vertex x [member of] V (G), [N.sub.G] (x) denotes the set of vertices adjacent to x in G, [d.sub.G](x) the degree of x in G (i.e., [d.sub.G](x) = [absolute value of [N.sub.G](x)|), and [delta](G) the minimal vertex degree in G. If L [subset] V (G) is a vertex subset of G, then G - L denotes the subgraph of G induced by V (G) n L, and NG(L) is the set of neighbours of all the vertices in L. Given distinct vertices x and y of G, an x - y path is a path in G with endvertices x and y. We denote by [C.sub.l] a cycle of length l, and by [K.sub.n,n] a complete balanced bipartite graph of order 2n. Finally, recall that a graph is called 2-connected if the removal of any single vertex does not disconnect G.

In this section we have gathered results used in the proofs of Theorems A and B. First of all, we recall two hamiltonicity criteria obtained by Moon and Moser [11].

Theorem 2.1 (Moon and Moser, [11]). Let G be a balanced bipartite graph of order 2n [greater than or equal to] 4, with

[delta] (G) [greater than or equal to] n + 1 / 2. Then G contains a Hamilton cycle.

Theorem 2.2 (Moon and Moser, [11]). Let G = (X; Y ;E) be a balanced bipartite graph of order 2n, and let [S.sub.m] = {x [member of] X : [d.sub.G](x) [less than or equal to] m}, [T.sub.m] = {y [member of] Y : [d.sub.G](y) [less than or equal to] m} for m [member of] Z. If, for every 1 [less than or equal to] m [less than or equal to] n/2, the sets [S.sub.m] and [T.sub.m] are of cardinalities less than m, then G is hamiltonian.

We shall need the following strengthening of Theorem 1.4.

Theorem 2.3 (Wojda and Wozniak, [13]). Let G(n; r) denote a bipartite graph with colour classes X = P [union] Q and Y = R [union] S such that [absolute value of P] =[absolute value of R] = r,[absolute value of Q] =[absolute value of S] = n - r, [N.sub.G(n;r)](x) = R for all x [member of] P, and [N.sub.G(n;r])(x) = Y for all x [member of] Q. Let G be a balanced bipartite graph of order 2n [greater than or equal to] 4, minimal degree [delta](G) [greater than or equal to] r [greater than or equal to] 1, and size [parallel] G [parallel] [greater than or equal to] n(n - r) + [r.sup.2]. Then G contains a Hamilton cycle, else r [less than or equal to] n/2 and G is isomorphic to G(n; r).

A bipartite graph of order 2n is called bipancyclic if it contains cycles of lengths 2k for all [member of] [less than or equal to] k [less than or equal to] n.

Theorem 2.4 (Bagga and Varma, [5]). Let G = (X; Y ;E) be a balanced bipartite graph of order 2n [greater than or equal to than or equal to] 8. If [d.sub.G](x)+[d.sub.G](y) [greater than or equal to] n+1 for every pair of non-adjacent vertices x [member of] X and y [member of] Y , then G is bipancyclic.

Theorem 2.5 (Entringer and Schmeichel, [8]). Let G be a hamiltonian bipartite graph of order 2n [greater than or equal to] 8. If [parallel] G [parallel] > n2=2, then G is bipancyclic.

We will also need to know the cycle structure of an n=2-regular hamiltonian bipartite graph G of order 2n. Notice that then [parallel] G [parallel] = [n.sup.2] = 2, so the above theorem does not apply. We then have:

Theorem 2.6 (J. Adamus, [2]). Let G be an n=2-regular hamiltonian bipartite graph of order 2n. Then G contains a cycle C of length 2n - 2. Moreover, if C can be chosen to omit a pair of adjacent vertices, then G is bipancyclic.

Given a balanced bipartite graph G = (X; Y ;E), one defines a k-biclosure [BCl.sub.k](G) of G as the graph obtained from G by succesively joining pairs of non-adjacent vertices x [member of] X and y [member of] Y , with degree sum of at least k, until no such pair remains. Closely related to this construction is the notion of k-bistability: A property P defined on all balanced bipartite graphs of order 2n is called k-bistable when, whenever G + xy has the property P and [d.sub.G](x) + [d.sub.G](y) [greater than or equal to] k, then G itself has the property P.

Theorem 2.7 (Bondy and Chvatal, [7]). A balanced bipartite graph G of order 2n is hamiltonian if and only if its (n + 1)-biclosure [BCl.sub.n+1](G) is so.

Theorem 2.8 (Amar, Favaron, Mago and Ordaz, [4]). The property of containing a cycle of length 2n-2 is (n + 2)-bistable on balanced bipartite graphs of order 2n.

3 Long cycles in balanced bipartite graphs

Suppose we want to know whether a balanced bipartite graph G = (X; Y ;E) has the property of containing a long cycle [C.sub.2n-2k] for some 0 [less than or equal to] k < n/2. Given Theorem 1.3 of Moon and Moser, a natural question arises: Can one impose such a property by decreasing the bound on the degree sum of nonadjacent vertices by k? We believe the answer to this question be positive (Conjecture A). As shown in Example 1.6, any lower bound on the degree sum of non-adjacent vertices x [member of] X and y [member of] Y which ensures [C.sub.2n-2k] [subset] G is at least n-k +1. On the other hand, decreasing the bound below n+1 imposes additional assumptions on the graph. Interestingly enough, without the 2-connectedness constraint the graph could contain no long cycles at all (see Example 1.7). The following result gives a positive answer to the above question in case k = 1.

Theorem A. Let G = (X; Y ;E) be a 2-connected balanced bipartite graph of order 2n [greater than or equal to] 4, such that [d.sub.G](x) + [d.sub.G](y) [greater than or equal to] n for every pair of non-adjacent vertices x [member of] X and y [member of] Y . Then G contains an even cycle of length at least 2n - 2.

We postpone the proof of the theorem to Section 4. Right now we will show that Theorem A implies Conjecture A for k = 1.

Corollary 3.1. Conjecture A holds for k = 1.

Proof: Let G = (X; Y ;E) be a balanced bipartite graph of order 2n that satisfies the assumptions of Conjecture A. By Theorem A above, G contains an even cycle of length at least 2n - 2, so without loss of generality one may assume that G is hamiltonian.

Let x [member of] X, say, be a vertex of minimal degree _(G) in G. Then Y contains precisely n- [delta](G) vertices non-adjacent to x, each of degree at least n - [delta](G) (as [d.sub.G](x) + [d.sub.G](y) [greater than or equal to] n for xy [??] E). Counting the edges incident with Y , we get

[parallel] G [parallel] [greater than or equal to] * (n - [delta](G))_(n _ [delta](G)) + [delta](G)* [delta](G).

Observe that [(n - [delta](G)).sup.2] + [[delta](G).sup.2] > [n.sup.2] [not equal to] 2 iff [delta](G) 6= n/2. Hence [parallel] G [parallel] > [n.sup.2]/2, provided [delta](G) [not equal to] n/2, and thus G contains [C.sub.2n-2], by Theorem 2.5. If, in turn, [delta](G) = n/2, then the result follows from Theorem 2.6.

Let us now turn to Erdos type criteria. In [3], the second author conjectured the following sufficient condition for a balanced bipartite graph to contain a long cycle [C.sub.2n-2k] (proved in [3] under considerably stronger assumptions).

Conjecture 3.2 (L. Adamus, [3]). Let G be a balanced bipartite graph of order 2n, where n C2n_2k 2k + 2, k [member of] Z. If [parallel] G [parallel] > n(n - k - 1) + k + 1, then G contains a cycle of length 2n - 2k.

Notice that both assumptions of the conjecture are weakest possible, as shown by the following two examples.

Example 3.3. Consider a graph [G.sub.1] of Example 1.6, with r = 1. This graph has precisely n(n-k-1)+ k + 1 edges, and it contains no cycle of length greater than 2n - 2k - 2.

Example 3.4. Let [G.sub.3] = (X; Y ;E) be a balanced bipartite graph, with colour classes of the form X = A [union] B, Y = C [union] D, where [absolute value of A] = [absolute value of D] = k + 1,[absolute value of B] =[absolute value of C] = n - k - 1. Fix a vertex [y.sub.0] in C, and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for all x [member of] A, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for all x [member of] B. Then [paralle] [G.sub.3] [paralle > n(n-k - 1)+ k +1 for k+3 [less than or equal to] n [less than or equal to] 2k+1, yet [G.sub.3] contains no cycle of length greater than 2n-2k-2. Hence the necessity of the assumption n [greater than or equal to] 2k + 2.

Interestingly, a similar graph was recently shown in [6] to be a counterexample to Gyori's conjecture on [C.sub.2l]-free bipartite graphs.

In light of Example 3.3 above, we ask: By how much can we decrease the lower bound on the size of a given graph G ensuring the existence of a cycle of length 2m - 2k, knowing that the minimal degree of G is greater than 1? We address this question in Conjecture B. Certain special cases of Conjecture B are known true: k = 0 is Theorem 1.4, k = r = 1 is done in [3]. The following theorem (proved in Section 5 below) shows that the conjecture also holds for k = 1 and arbitrary r.

Theorem B. Let G = (X; Y ;E) be a balanced bipartite graph of order 2n and minimal degree [delta](G) [greater than or equal to] r [greater than or equal to] where n [greater than or equal to] 4 and n [greater than or equal to] 2r + 1. Let

g(n; r) = n(n - 1 - r) + r(1 + r) + 1.

Then G contains a cycle of length 2n - 2, provided [parallel] G [parallel] [greater than or equal to] g(n, r).

Notice that Theorems 2.1 and 1.4 can be put together as follows:

Theorem 3.5. Let G be a balanced bipartite graph of order 2n [greater than or equal to] 4, with minimal degree [delta](G) [greater than or equal to] r. Then G contains a Hamilton cycle, provided

(1) n [less than or equal to] 2r - 1 or

(2) n [greater than or equal to] 2r and [parallel] G [parallel] > n(n - r) + [r.sup.2] .

Along the same lines, we combine Theorem 2.4 and Theorems A and B to prove the following criterion for cycles of length 2n - 2.

Theorem 3.6. Let G = (X; Y ;E) be a balanced bipartite graph of order 2n [greater than or equal to] 8, with minimal degree [delta](G) [greater than or equal to] r [greater than or equal to] 1. Then G contains a cycle of length 2n _ 2, provided

(1) n [less than or equal to] 2r - 1 or

(2) n = 2r and [parallel] G [parallel] - [2r.sup.2] + r + 1 or

(3) n [greater than or equal to] 2r + 1 and [parallel] G [parallel] - n(n - 1 - r) + r(1 + r) + 1 .

Remark 3.7. The lower bounds of conditions (2) and (3) are sharp: For an extremal graph for (2), consider the graph G3 from Example 3.4 with k + 1 = r; for (3), consider [G.sub.1] from Example 1.6 with k = 1.

Proof of Theorem 3.6:

(1) Since n [less than or equal to] 2r - 1 iff r [greater than or equal to] (n + 1)/2, then the degree sum is greater than or equal to n + 1 for every pair of vertices in G (in particular, for non-adjacent ones). By Theorem 2.4, G is then bipancyclic.

(2) The bound on the size of G together with [delta](G) [greater than or equal to] r = n=2 force 2-connectedness. Also, the degree sum is at least 2r = n for every pair of vertices in G. Hence, by Corollary 3.1, G contains [C.sub.2n-2].

(3) This is Theorem B.

4 Proof of Theorem A

As 2-connectedness of a graph G implies [delta](G) [greater than or equal to] 2, the assertion of the theorem holds true for n [less than or equal to] 3, by Theorem 2.1. Suppose then there exists n [greater than or equal to] 4 for which the assertion fails. Let G = (X; Y ;E) be a maximal 2-connected balanced bipartite graph of order 2n, in which [d.sub.G](x) + [d.sub.G](y) [greater than or equal to] n for all non-adjacent x [member of] X, y [member of] Y , without a cycle of length at least 2n - 2. By maximality of G, G + xy contains a cycle of length at least 2n - 2, and hence G contains an x - y path of length 2n - 3 or 2n - 1 for every pair of non-adjacent x [member of] X, y [member of] Y .

We shall show first that G contains a Hamilton path. Suppose not. Let x [member of] X, y [member of] Y be non-adjacent vertices and let P be an x - y path in G of length 2n - 3; say, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Put [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] then G contains a cycle [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of length 2n - 2; a contradiction.

As |absolute value of [I.sub.P| = [d.sub.G [V (P)]](x) and [absolute value of [I.sub.P]] = [d.sub.G][V (P)](y), we obtain

[d.sub.G[V (P)]](x) + [d.sub.G [V (P)]](y) = [absolute value of [I.sub.P]] + [absolute value of [J.sub.P]] = [absolute value of [I.sub.P]] [union] [J.sub.P] [less than or equal to] n - 1,

where G[V (P)] denotes the subgraph of G induced by the vertex set of P. This shows that at least one of the vertices [u.sub.1] and [v.sub.n-1] has a neighbour among the remaining vertices [u.sub.n]; [v.sub.n] of G-P; say, [v.sub.n-1][u.sub.n] [member of] E. Notice that then [u.sub.n][v.sub.n] [??] E, for otherwise [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] would be a Hamilton path. Similarly, [u.sub.1][v.sub.n] [??] E. Hence, in particular, [I.sub.P] contains indices of all the neighbours of [u.sub.1] in G, so [absolute value of [I.sub.P]] = [d.sub.G]([u.sub.1]). Let now [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and as [d.sub.G]([u.sub.1]) + [d.sub.G]([v.sub.n]) [greater than or equal to] n, it follows that there exists [i.sub.0] [member of] [I.sub.P] [intersection] [K.sub.P] . Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a Hamilton path in G; a contradiction.

Let now x [member of] X and y [member of] Y be a pair of non-adjacent vertices such that G contains a Hamilton x - y path P; say, P = [u.sub.1][v.sub.1] : : : [u.sub.n][v.sub.n], where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and y = [v.sub.n]. Put [I.sub.G] = {1 [less than or equal to] i [less than or equal to]|[u.sub.1][v.sub.i] [member of] E and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [I.sub.G] [intersection] [empty set] for if [i.sub.0] [member of] [I.sub.G] [intersection] [J.sub.G], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a Hamilton cycle in G.

Hence

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

so that, for every 1 [less than or equal to] i [less than or equal to] n,

either [u.sub.i] [member of] [N.sub.G](y) or else [v.sub.i] [member of] [N.sub.G] (x): (*)

Let d = [d.sub.G](y). Denote by [x.sub.1], ... [x.sub.d] those of the vertices [u.sub.1], ... , [u.sub.n] that are adjacent to y, ordered according to the orientation of P (from x to y). Let [y.sub.1], ... , [y.sub.d] be the vertices of Y that lie on P next to the respective [x.sub.1], ... , [x.sub.d]; then [y.sub.d] = y.

Observe that if [x.sub.1] = [u.sub.i] with i < n - d + 1, then there exists 1 [less than or equal to] j [less than or equal to] - 1 such that [y.sub.j] = [v.sub.l], where [u.sub.l+1] [empty set] [N.sub.G](y). Then [v.sub.l+1] [member of] [N.sub.G](x) and we obtain a cycle [u.sub.1][v.sub.l]+[u.sub.l]+2 ... [v.sub.n][u.sub.l][v.sub.l-1] ... [v.sub.1][u.sub.1] of length 2n - [member of] in G; a contradiction.

Therefore [x.sub.1] = [u.sub.n-d+1], and hence NG(y) coincides with the set {[u.sub.n-d+1], ... , [u.sub.n]}, call it U. Then {[y.sub.1], ... , [y.sub.d]} coincides with V := {[v.sub.n-d+1], ... , [v.sub.n]}, and by (*), [N.sub.G](x) = Y \ V .

Suppose now that, for every v [member of] V , NG(v) - U. Then, for all u [member of] X n U and v [member of] V , u and v are non-adjacent, hence NG(u) - Y n V . Consequently, [d.sub.G]([u.sub.i]) [less than or equal to] n - d (i [less than or equal to] n - d), and [d.sub.G] ([v.sub.j]) [less than or equal to] d (j [greater than or equal to] n - d + 1). But [u.sub.i]and [v.sub.j] being non-adjacent, we also have [d.sub.G]([u.sub.i]) + [d.sub.G]([v.sub.j]) - n, which implies that [d.sub.G]([u.sub.i]) = n - d and [d.sub.G]([v.sub.j]) = d, and hence

[N.sub.G]([u.sub.i]) = Y n V and [N.sub.G]([v.sub.j]) = U for all i [less than or equal to] n - d; j [greater than or equal to] n - d + 1:

Thus G contains a complete bipartite graph [K.sub.d,d] spanned on the vertices of U and V , and a complete bipartite [K.sub.n-d,n-d] spanned on X n U and Y n V .

Now, G being 2-connected, it must contain two independent edges [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some [i.sub.1]; [i.sub.2] [greater than or equal to] n-d+1 and [j.sub.1]; [j.sub.2] [less than or equal to] n-d. One immediately verifies that such a graph contains a cycle of length 2n-2, again contradicting the choice of G.

We can therefore conclude that there exists a vertex [v.sub.j] , with n - d + 1 [less than or equal to] j [less than or equal to] n - 1, adjacent to a [u.sub.i], where i [less than or equal to] n-d. Then [u.sub.1][v.sub.i] ... [u.sub.j][v.sub.n][u.sub.n] ... [v.sub.j][u.sub.i][v.sub.i-1] ... [v.sub.1][u.sub.1] is a Hamilton cycle in G. This contradiction completes the proof of the theorem.

5 Proof of Theorem B

Throughout this section we will frequently refer to the exceptional graph G(n; r) of Theorem 2.3. Recall that by G(n; r) we denote a balanced bipartite graph of order 2n, with colour classes X = P [union] Q and Y = R[union]S, where [absolute value of P] = [absolute value of R] = r, [absolute value of Q] = [absolute value of S] = n-r, [N.sub.G(n,r)](x) = R for all x [member of] P, and [N.sub.G(n,r])(x) = for all x [member of] Q.

Let, as before, g(n; r) = n(n - 1 - r) + r(1 + r) + 1. We shall first show the following lemma.

Lemma 5.1. Let G = (X; Y ;E) be a balanced bipartite graph of order 2n and minimal degree [delta](G) [greater than or equal to] r [greater than or equal to] 1, where n [greater than or equal to] 4 and n [greater than or equal to] 2r+1. Let [parallel] G [parallel] [greater than or equal to] g(n; r), and assume there exists a pair of vertices x [member of] X and y [member of] Y such that [d.sub.G](x) + [d.sub.G](y) [less than or equal to] n and [delta](G - {x; y}) [greater than or equal to] r. Then G contains a cycle of length 2n - 2.

Proof: Suppose G contains no cycle of length 2n-2. Then G- fx; yg contains no such cycle either, and as [delta](G - {x; y}) [greater than or equal to] r, Theorem 2.3 implies that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

On the other hand,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

Hence [d.sub.G](x) + [d.sub.G](y) = n, the vertices x and y are non-adjacent, G - fx; yg equals G(n - 1; r), and r [less than or equal to] (n - 1)=2. Without loss of generality, we may assume that x belongs to the colour class of G containing P [union] Q of G(n - 1; r).

Now, either [d.sub.G](x) - r + 1 or [d.sub.G](x) = r. In the first case, x must have at least two neighbours in S or else at least one neighbour in both S and R. One easily verifies that then G contains a cycle of length 2n - 2, omitting y and a single vertex of P; a contradiction.

If, in turn, [d.sub.G](x) = r, then [d.sub.G](y) = n - r and y must have neighbours in both P and Q, since r [less than or equal to] (n - 1)/2 < n/2. Consequently, G contains a cycle of length 2n - 2, omitting x and a vertex of S, which again contradicts the choice of G.

We are now in position to prove Theorem B.

For a proof by contradiction, consider a graph G satisfying the assumptions of Theorem B, that does not contain a cycle of length 2n_2. Observe first that [parallel] G [parallel] > n2=2. Indeed, the difference g(n; r) - [n.sup.2]/2 is always positive. Hence, by Theorem 2.5, G is not hamiltonian. Consequently, Theorem 2.2 implies that there exists a positive integer m - n=2 such that at least one of the sets [S.sub.m] = {x [member of] X : [d.sub.G](x) [less than or equal to] m}, [T.sub.m] = {y [member of] Y : [d.sub.G](y) [less than or equal to] m} has cardinality greater than or equal to m.

Let l be the least such m. Without loss of generality, we may assume that l is realized in X; i.e., |{x [member of] X : [d.sub.G](x) [less than or equal to] l}| [greater than or equal to] l. Order the vertices of X = {[x.sub.1], ... , [x.sub.n]} so that r [less than or equal to] [d.sub.G] ([x.sub.1]) [less than or equal to] ... [less than or equal to] [d.sub.G]([x.sub.n]). Then, by minimality of l, we have l = min {i : [d.sub.G]([x.sub.i]) [less than or equal to] i}. Of course, r [less than or equal to] l [less than or equal to] n/2. Put L = {[x.sub.1], ... , xl}.

The rest of the proof proceeds in two cases, depending on l being equal to or greater than r.

Case 1:

l = r. We will first show that all the vertices of Y have degrees greater than r. Suppose to the contrary that there exists [y.sub.1] [member of] Y with [d.sub.G] ([y.sub.1]) = r. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and [delta](G - {[x.sub.1]; [y.sub.1]}). [right arrow] r - 1. On the other hand, by Theorem 2.3,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Hence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. By comparison of degrees, one readily verifies that [x.sub.1] belongs to that colour class of G that contains G(n - 1; r - 1). in fact, L = {[x.sub.1]} [union] P. Consider the sets R and S of the other colour class of G(n - 1; r - 1). As [absolute value of [N.sub.G]] ([x.sub.1]) = r > [absolute value of R] and [x.sub.1][y.sub.1] [??] E, it follows that either [x.sub.1] has neighbours in both R and S or else it has at least two neighbours in S. In any case, as in the proof of Lemma 5.1, one easily finds a cycle of length 2n - 2 in G, omitting [y.sub.1] and a vertex of P; a contradiction. Thus [d.sub.G](y) [greater than or equal to] r + 1 for every y [member of] Y .

Next observe that every vertex of Y has a neighbour in L. Suppose otherwise, and let [y.sub.1] [member of] Y be such that [N.sub.G]([y.sub.1]) [member of] X\L. Notice that all vertices of X n L have degrees greater than r, for otherwise [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. As. Consequently, by removing [y.sub.1] and a vertex of L, say [x.sub.1], we do not decrease the minimal degree in the remainder of G. But, as [N.sub.G]([y.sub.1]) [member of] X\L, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], and by Lemma 5.1, G contains a cycle of lenth 2n - 2; a contradiction.

Consider the graph G - L. Notice that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Moreover, we claim that [d.sub.G-L] (x) + [d.sub.G-L](y) [greater than or equal to] n for every pair of non-adjacent x [member of] X\L and y [member of] Y. For if [d.sub.G-L](x) + [d.sub.G-L] (y) n - 1 for a pair of non-adjacent x [member of] X \ L and y [member of] Y , then, by the above inequality,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

which contradicts [parallel] (G - L) - {x, y} [parallel] being a bipartite graph with colour classes of cardinality n - r - 1 and n - 1.

Taking into account that every vertex in Y has a neighbour in L, we now obtain that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Let [??] be the bipartite graph obtained from G by joining all the non-adjacent vertices of Y and X \ L. As [absolute value of X \ L ] = n - r and every y [member of] Y has a neighbour in L, we get that [d.sub.[??]] (y) [greater than or equal to] n - r + 1 for all y [member of] Y . Hence [d.sub.[??]] (x) + [d.sub.[??](y) [greater than or equal to] n + 1 for every pair of non-adjacent vertices x [member of] X and y [member of] Y . Therefore, joining all the non-adjacent vertices of X and Y in [??] with degree sum of at least n + 1 yields a complete bipartite graph [K.sub.n,n]. As [??] was obtained from G also by joining certain non-adjacent vertices of X and Y with degree sum of at least n + 1, this shows that the (n + 1)-biclosure of G equals [K.sub.n,n]. Thus, by Theorem 2.7, G contains a Hamilton cycle, which, as we observed at the begining of this proof, is impossible.

Case 2:

l [greater than or equal to] r + 1. In this case n [greater than or equal to] 2r + 2 (as [less than or equal to] n=2) and r [greater than or equal to] 2 (for otherwise l = r = 1, by minimality); hence [absolute value of L] [greater than or equal to] 3. Moreover, [d.sub.G]([x.sub.l]) = [d.sub.G]([x.sub.l]) = l, by minimality of l.

Suppose first that [d.sub.G](x) + [d.sub.G](y) [greater than or equal to] n + 2 for every pair of non-adjacent x [member of] X \ L and y [member of] Y . Let G' be the bipartite graph obtained from G by joining all the non-adjacent vertices of X \ L and Y . We claim that every y [member of] Y has a neighbour in L (in G'). Suppose otherwise, and let [y.sub.1] [member of] Y be such that [N.sub.G'] ([y.sub.1]) [member of] X \ L. Then [d.sub.G'] ([y.sub.1]) [less than or equal to] n-l, hence [d.sub.G'] ([x.sub.1])+[d.sub.G'] ([y.sub.1]) [less than or equal to] n. Moreover, [delta](G'-{[x.sub.1]; [y.sub.1]}) [greater than or equal to] r, as all the vertices in X \ L have degrees of at least l [greater than or equal to] r + 1, and [d.sub.G'] (y) [greater than or equal to] n - l [greater than or equal to] l [greater than or equal to] r + 1 for all y [member of] Y . Then Lemma 5.1 implies that G0 contains a cycle of length 2n - 2, and hence, by Theorem 2.8, so does G; a contradiction.

Notice that G0 was obtained from G by joining only pairs of vertices with degree sum of at least n+2. Also, as every vertex y [member of] Y has a neighbour in L (in G'), we have [d.sub.G'] (y) [greater than or equal to] n - l + 1. Recall that [d.sub.G'] ([x.sub.l]) = [d.sub.G]([x.sub.l]) = l and [d.sub.G'] ([x.sub.l-1]) = [d.sub.G]([x.sub.l-1]) = l. Hence

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Let G(2) be the graph obtained from G0 by joining [x.sub.l] and [x.sub.l-1] with all the vertices of Y. Then [d.sub.G(2)] (y) [greater than or equal to] n - l + 2 for all y [member of] Y, and as [d.sub.G](2) ([x.sub.l-2]) = [d.sub.G]([x.sub.l-2]) [greater than or equal to] l - 1 (by minimality of l), we get that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Let now [G.sup.(3)] be the graph obtained from [G.sup.(2)] by joining [xl.sub.-2] with all the non-adjacent vertices of Y . In general, let [G.sub.(m)] (m [greater than or equal to] 3) be obtained from [G.sup.(m-1)] by joining [x.sub.l-m+1] with all the non-adjacent vertices of Y. Then [G.sup.(l)] = [K.sub.n,n], and [G.sup.(m)] is obtained from [G.sup.(m-1)] by joining only pairs of vertices with degree sum of at least n + 1. Thus [G.sup.(l)] = [BCl.sub.n+1](G), so that the (n + 1)-biclosure of G is a complete bipartite graph. Now Theorem 2.7 implies that G contains a Hamilton cycle, which again leads to contradiction.

To complete the proof, it remains to consider the case when there is a pair of non-adjacent [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] . This however can only happen when n = 2r + 2 or n = 2r + 3. For let us suppose that n [greater than or equal to] 2r + 4, and put f(l) = [l.sup.2] +(n-l-1)(n-1) + n + 2. We show [parallel] G [parallel] < f(l) and f(l) [less than or equal to] g(n, r), and thus obtain a contradiction with the assumption [parallel] G [parallel] [greater than or equal to] g(n, r). If G contains a pair of non-adjacent vertices x [member of] X \ L and y [member of] Y with [d.sub.G](x) + [d.sub.G](y) [less than or equal to] n + 1, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

As the derivative of f equals f'(l) = -n + 2l + 1, it follows that f(l) is decreasing for l [less than or equal to] (n - 1)/2, and hence maximal at l = r + 1. One immediately verifies that f(r + 1) [less than or equal to] g(n, r) for n [greater than or equal to] 2r + 4. If, on the other hand, l > (n - 1)/2, then l = n/2 (since l [less than or equal to] n/2), and it is again immediate to check that f(n/2) [less than or equal to] g(n, r) for n [greater than or equal to] 2r + 4.

Subcase 2.1:

n = 2r + 2. Then r + 1 [less than or equal to] l [less than or equal to] n/2 yields l = r + 1, and we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

On the other hand,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (2)

Hence

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Suppose first that [parallel] G - {[x.sup.0], [y.sup.0]} = [3r.sup.2] + 3r + 1. Then, by (2), [d.sub.G](x) = l for all x [member of] L, and NG([y.sup.0])[subset]L = [empty set] in particular, [d.sub.G]([x.sup.1])+[d.sub.G]([y.sup.0]) - l + (n-l) = n. Moreover, [N.sub.G](y) [contains] X /([union][{[x.sup.0]}) for all y [member of] Y / {[y.sup.0]}, and [d.sub.G](x) [greater than or equal to] r + 1 for all x [member of] X, so that [delta](G - {[x.sub.1], [y.sup.0]}) [greater than or equal to] r, and by Lemma 5.1, G contains a cycle of length 2n - 2; a contradiction.

Therefore we may assume that [parallel]G - {[x.sup.0], [y.sup.0]} = 3[r.sup.2] + 3r. By (1), [d.sub.G]([x.sup.0]) + [d.sub.G]([y.sup.0]) = 2r + 3, and what's more, [d.sub.G](x) + [d.sub.G](y) [greater than or equal to] 2r + 3 for all non-adjacent x [member of] X / L and y [member of] Y. Indeed, if [d.sub.G]([x.sub.1]) + [d.sub.G]([y.sup.1]) - 2r + 2 for some non-adjacent [x.sup.1] [member of] X / L and [Y.sup.1] [member of] Y, then by (1) and (2), [parallel]G - {[x.sup.1], [Y.sup.1] [less than or equal to] [3r.sup.2] + 3r + 1, which leads to contradiction, as above.

We will now show that [absolute value of [N.sub.G](L)] > r + 1. Suppose otherwise, that is, suppose [absolute value of [N.sub.G](L)] = l = r + 1. Then [N.sub.G]([y.sup.0]) [union] L = [empty set] for else [N.sub.G](L) [intersection] [y.sup.0] implies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

which is impossible. Therefore [d.sub.G]([y.sup.0]) = n - l - 1 = r; in particular, [d.sub.G]([x.sub.1]) + [d.sub.G]([y.sup.0]) [less than or equal to] l + r < n. Notice that, as G - {[x.sup.0], [y.sup.0]} only has one edge less than the right-hand side of (2), every neighbour of [y.sup.0] in G has degree at least n - 2 = 2r, and every neighbour of [x.sub.1] has at least l - 1 = r other neighbours in L ([x.sub.1] being the only vertex whose degree could be less than l). Thus [delta](G - {[x.sub.1]; [y.sup.0]}) [greater than or equal to] r, and we get a contradiction, by Lemma [5.1.] Thus [absolute value of [N.sub.G](L)] > r + 1.

It is now not difficult to see that [BCl.sub.n+1](G) = [K.sub.n,n:] Recall that we have verified that [d.sub.G](x) + [d.sub.G](y) [greater than or equal to] 2r + 3 = n + 1 for all non-adjacent x [member of] X / L and y [member of] Y. Let G' be the graph obtained from G by joining all the non-adjacent vertices of X a/ L and Y. Next observe that, by minimality of l = r + 1, [d.sub.G'] ([x.sub.r+1]) = [d.sub.G]([x.sub.r+1]) = r + 1, and as [absolute value of [N.sub.G](L)]} > r + 1, at least one non-neighbour of [x.sub.r+1], say [y.sup.0], has a neighbour among the other vertices of L. Hence [absolute value of [N.sub.G'] (y')} [greater than or equal to] [absolute value of X / L] + 1, so that [d.sub.G'] ([x.sub.r+1]) + [d.sub.G'] (y') [greater than or equal to] (r + 1) + (r + 2) = n + 1. Let [G.sup.(2)] be obtained from G' by joining [x.sub.r+1] with y', and hence increasing the degree of [x.sub.r+1] to r + 2. Then [d.sub.G(2)] ([x.sub.r+1]) + [d.sub.G(2)] (y) [greater than or equal to] n + 1 for all y [member of] Y. Let [G.sup.(3]) be obtained from [G.sup.(2)] by joining [x.sub.r+1] with all the non-adjacent vertices of Y. Now [d.sub.G(3)] (y) [greater than or equal to] r + 2 for all y [member of] Y. By minimality of l again, [d.sub.G(3)] ([x.sub.r]) = [d.sub.G](xr) = r + 1, and hence [d.sub.G(3)] (xr) + [d.sub.G(3)] (y) [greater than or equal to] 2r + 3 for all y [member of] Y. Let [G.sub.(4)] be obtained from [G.sup.(3)] by joining xr with all the non-adjacent vertices of Y. Then [d.sub.G(4)] (y) [greater than or equal to] r + 3 for all y [member of] Y, and hence, as [delta][(G.sup.(4)]) [greater than or equal to] [delta](G) [greater than or equal to] r, [d.sub.G(4)] (x) + [d.sub.G(4)] (y) [greater than or equal to] 2r + 3 for all non-adjacent x [member of ] X and y [member of] Y. Joining all the non-adjacent pairs x [member of] X, y [member of] Y of [G.sup.(4)] with degree sum of at least n + 1 we thus obtain [K.sub.n,n]. Since at each stage we only joined pairs of vertices with degree sum of at least n + 1, this shows that [K.sub.n,n] = [BCl.sub.n+1](G). By Theorem [2.7] G contains a Hamilton cycle; a contradiction.

Subcase 2.2:

n = 2r + 3. Again, r + 1 [less than or equal to] l [less than or equal to] n/2 yields l = r + 1, and we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.],

and, on the other hand,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

Therefore both inequalities must, in fact, be equalities; in particular, dG(x1) = l and dG(x) [greater than equal to] r + 1 for all x [member of] X, NG([y.sup.0])[intersection]L = [empty set] so that [d.sub.G]([y.sub.0]) [less than or equal to] nl, and finally [absolute value of [N.sub.G](y)] [greater than or equal to] [absolute value of X \L[f[x.sup.0]})] = r+1 for all y [member of ] Y n {[y.sup.0]}. Thus, again, G with the vertices x1, y0 satisfies the assumptions of Lemma 5.1, hence G contains a cycle of length 2n-2; a contradiction. This completes the proof of Theorem B.

Acknowledgements

We are grateful to Evelyne Flandrin for her valuable comments and numerous discussions regarding the problems of this paper. We would also like to thank Artur Fortuna for an inspiring conversation.

received February 12, 2009, revised June 15, 2009, accepted June 16, 2009.

References

[1] J. Adamus, A note on a degree sum condition for long cycles in graphs, preprint arXiv:0711.4394v2.

[2] J. Adamus, On the cycle structure of hamiltonian [delta]-regular bipartite graphs of order 4[delta], preprint arXiv:0711.4426v2.

[3] L. Adamus, Edge condition for long cycles in bipartite graphs, Discrete Math. Theor. Comput. Sci. 11:2 (2009), 25-32.

[4] D. Amar, O. Favaron, P. Mago and O. Ordaz, Biclosure and bistability in a balanced bipartite graph, J. Graph Theory 20 (1995), 513-529.

[5] K.S. Bagga and B.N. Varma, Hamiltonian properties in bipartite graphs, Bull. Inst. Combin. Appl. 26 (1999), 71-85.

[6] C. Balbuena, P. Garcia-Vazquez, X. Marcote and J.C. Valenzuela, Counterexample to a conjecture of Gyori on C2l-free bipartite graphs, Discrete Math. 307 (2007), 748-749.

[7] J. A. Bondy and V. Chvatal, A method in graph theory, Discrete Math. 15 (1976), 111-135.

[8] R.C. Entringer and E.F. Schmeichel, Edge conditions and cycle structure in bipartite graphs, Ars Combinatoria 26 (1988), 229-232.

[9] P. Erdos, Remarks on a paper of Posa, Magyar Tud. Akad. Mat. Kutato Int. Kozl. 7 (1962) 227-229.

[10] N. Linial, A lower bound for the circumference of a graph, Discrete Math. 15 (1976), 297-300.

[11] J. Moon and L. Moser, On hamiltonian bipartite graphs, Israel J. Math. 1 (1963), 163-165.

[12] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960), 55.

[13] A.P.Wojda and M.Wozniak, Orientations of hamiltonian cycles in bipartite digraphs, Period. Math. Hungar. 28 (1994), 103-108.

[14] D.R. Woodall, Sufficient conditions for circuits in graphs, Proc. London Math. Soc. (3) 24 (1972), 739-755.

Janusz Adamus (1) ([dagger]) and Lech Adamus (2) ([double dagger])

(1) Department of Mathematics, The University of Western Ontario, London, Ontario, N6A 5B7 Canada and Institute of Mathematics, Jagiellonian University, ul. Lojasiewicza 6, 30-348 Krakow, Poland

(2) Faculty of Applied Mathematics, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Krakow, Poland and LRI, Bat. 490, Universite Paris-Sud, 91405 Orsay Cedex, France

([dagger]) Corresponding author.

([doubel dagger]) The second author's research was partially supported by the AGH University of Science and Technology grant No. 11.420.04 and by the Polish Ministry of Science doctoral grant No. 0102/M03/2007/32.
COPYRIGHT 2009 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2009 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Adamus, Janusz; Adamus, Lech
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Geographic Code:4EXPO
Date:Jun 1, 2009
Words:8396
Previous Article:On the chromatic number of some flip graphs.
Next Article:On economical set representations of graphs.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters