Extending cycles in bipartite graphs. (English) Zbl 0674.05044

Hendry, George R. T.

J. Comb. Theory, Ser. B 51, No. 2, 292-313 (1991).

Let G(X,Y,E) be a balanced bipartite graph of order 2n. We introduce the following definitions. A cycle C in G is extendable if there exists a cycle C’ in G such that V(C)\(\subseteq V(C')\) and \(| V(C')| =| V(C)| +2\). G is bi-cycle extendable if G has at least one cycle and every nonhamiltonian cycle in G is extendable. G has a bi- pancyclic ordering if the vertices of X and Y can be labelled \(x_ 1,x_ 2,...,x_ n\) and \(y_ 1,y_ 2,...,y_ n\), respectively, so that \(C_{2k}\subseteq <x_ 1,...,x_ k,y_ 1,...,y_ k>,\) for \(2\leq k\leq n.\) Let \[ {\bar \sigma}(G)=\min \{d(x)+d(y):\quad x\in X,\quad y\in Y\quad and\quad xy\not\in E(G)\}. \] It is shown that if \({\bar \sigma}\)(G)\(\geq n+1\) and C is a 2k-cycle in G then C is extendable unless \(<V(C)>\cong K_{k,k}\). As consequences of the proof of this result, we deduce that if either \({\bar \sigma}(G)\geq (7n+1)/6\) or \(\delta (G)\geq (n+1)/2\) then, in each case with one exceptional graph, G is bi-cycle extendable. It is also shown that if \(\ell\) is an integer such that \(n\geq 2\ell \geq 2,\) \(\delta (G)\geq \ell\) and \(| E(G)| \geq n^ 2-\ell n+\ell^ 2\) then every cycle of length at least \(\ell\) in G is extendable unless \(G\cong K_{n,n}-E(K_{\ell,n-\ell}).\) As a corollary, we deduce that such graph G has a bi-pancyclic ordering unless \(G\cong K_{n,n}-E(K_{\ell,n-\ell}).\)
A number of preliminary results are required, among which is the determination of the maximum size of a balanced bipartite graph of specified order, minimum degree and edge independence number.

Reviewer: G.R.T.Hendry

MSC:

05C38

Paths and cycles

Keywords:

Hamiltonian; bipartite graph; cycle

References:

[1]	Behzad, M; Chartrand, G; Lesniak-Foster, L, ()
[2]	Bondy, J.A; Chvátal, V, A method in graph theory, Discrete math., 15, 111-135, (1976) · Zbl 0331.05138
[3]	Hendry, G.R.T, Extending cycles in graphs, Discrete math., 85, 59-72, (1990) · Zbl 0714.05038
[4]	Hendry, G.R.T, On paths, factors and cycles in graphs, () · Zbl 0545.05050
[5]	{\scJ. Mitchem and E. Schmeichel}, Pancyclic graphs and bipancyclic graphs—A survey, preprint. · Zbl 0566.05043
[6]	Moon, J; Moser, L, On Hamiltonian bipartite graphs, Israel J. math., 1, 163-165, (1963) · Zbl 0119.38806
[7]	Schmeichel, E; Mitchem, J, Bipartite graphs with cycles of all even lengths, J. graph theory, 6, 429-439, (1982) · Zbl 0502.05036