Extending cycles in bipartite graphs. (English) Zbl 0674.05044

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


05C38 Paths and cycles
Full Text: DOI


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.