On the bipartite independence number of a balanced bipartite graph
type: Item
instance of: scholarly article
title: On the bipartite independence number of a balanced bipartite graph
zbMATH Open document ID: 0791.05069
DOI: 10.1016/0012-365X(93)90537-4
author: Odile Favaron
author: Pedro Mago
author: Oscar Ordaz
published in: Discrete Mathematics
publication date: 1994-06-08T00:00:00Z
review text: The bipartite independence number \(\alpha_{\text{BIP}} (G)\) of a bipartite graph \(G\) is the maximum cardinality of a balanced independent set. \textit{P. Ash} [Ars Comb. 16 A, 33-37 (1983; Zbl 0534.05041)] proved that if the balanced bipartite graph \(G\) is 2-connected, \(n \leq 3 \delta- 3\) and \(\alpha_{\text{BIP}} (G)<(2\delta-3)/3\), then \(G\) is hamiltonian. \textit{Fraisse} [\(D_ \lambda\)-cycles and their applications for hamiltonian graphs, Thesis, Université Paris-Sud, 1986] showed that every 2-connected balanced bipartite graph for which \(\alpha_{\text{BIP}} \leq \delta-1\) is hamiltonian. \textit{O. Favaron} et al. [SIAM J. Discrete Math. 6, 189-196 (1993)] dropped the connectedness condition in showing that if the balanced bipartite graph \(G\) satisfies \(\alpha_{\text{BIP}} \leq 2 \leq \delta\) then, with two exceptional graphs, \(G\) is hamiltonian. Among other results the authors prove the following. If \(G\) is a balanced bipartite graph of minimum degree \(\delta \geq 1\) and there exists an integer \(t\), \(0 \leq t \leq \delta-1\) such that \(\alpha_{\text{BIP}} \leq \delta+t\), then \(G\) is \((\delta-t)\)- connected. If the balanced bipartite graph \(G\) satisfies \(\alpha_{\text{BIP}} \leq \delta\), then, with two exceptional graphs, \(G\) is hamiltonian.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 473115
zbMATH Keywords: bipartite independence number
zbMATH Keywords: bipartite graph
zbMATH Keywords: balanced independent set
zbMATH Keywords: hamiltonian graphs
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: Q3317137
cites work: Q4860774
cites work: Q3831040
cites work: Hamiltonian Properties of Bipartite Graphs and Digraphs with Bipartite Independence 2
cites work: On Hamiltonian bipartite graphs
cites work: Existence of Dlambda-cycles and Dlambda-paths
Recommended article: Bipartite independent number and Hamilton-biconnectedness of bipartite graphs
Recommended article: Q3317137
Recommended article: Q3073889
Recommended article: Q4895662
Recommended article: Q3021510
Recommended article: Hamiltonian cycles in bipartite graphs
Recommended article: Neighborhood conditions for balanced independent sets in bipartite graphs
Recommended article: Hamiltonian properties and the bipartite independence number
Recommended article: Q2992099
Recommended article: A sufficient condition for vertex bipancyclicity in balanced bipartite graphs
description: scientific article; zbMATH DE number 473115