ON THE BIPARTITE INDEPENDENCE NUMBER OF A BALANCED BIPARTITE GRAPH

Authors
FAVARON O MAGO P ORDAZ O
Citation
O. Favaron et al., ON THE BIPARTITE INDEPENDENCE NUMBER OF A BALANCED BIPARTITE GRAPH, Discrete mathematics, 121(1-3), 1993, pp. 55-63
Citations number
7
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
Discrete mathematics → ACNP
ISSN journal
0012365X
Volume
121
Issue
1-3
Year of publication
1993
Pages
55 - 63
Database
ISI
SICI code
0012-365X(1993)121:1-3<55:OTBINO>2.0.ZU;2-5
Abstract
The bipartite independence number alpha(BIP) of a bipartite graph G is the maximum order of a balanced independent set of G. Let delta be th e minimum degree of the graph. When G itself is balanced, we establish some relations between alpha(BIP) and the size or the connectivity of G. We also prove that the condition alpha(BIP) less-than-or-equal-to delta (resp. alpha(BIP) less-than-or-equal-to delta-1) implies that G is hamiltonian (resp. Hamilton-biconnected), thus improving a result o f Fraisse.