×

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

MSC:

05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Behzad, M.; Chartrand, G.; Lesniak-Foster, L., (Graphs and Digraphs (1979), Prindle, Weber & Schmidt: Prindle, Weber & Schmidt Boston) · Zbl 0403.05027
[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, (Ph.D. Thesis (1985), Aberdeen University) · Zbl 0545.05050
[5] J. Mitchem and E. Schmeichel; J. Mitchem and E. Schmeichel · 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.