𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hamiltonian properties and the bipartite independence number

✍ Scribed by Oscar Ordaz; Denise Amar; André Raspaud

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
412 KB
Volume
161
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

By using the notion of compatibility of subgraphs with a perfect matching developed for digraphs in [1], we show that if, in a balanced bipartite graph G of minimum degree 6, the maximum cardinality ebip of a balanced independent subset satisfies ~bip ~< 26 --4, then G is hamiltonian-biconnected, and if Ctbip ~< 26 --2, G contains a hamiltonian path. Moreover, we give some properties of balanced bipartite graphs which are not hamiltonian, and which satisfy ~bip ~ 26 -2.

📜 SIMILAR VOLUMES

On the bipartite independence number of
On the bipartite independence number of a balanced bipartite graph
✍ Odile Favaron; Pedro Mago; Oscar Ordaz 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 603 KB

Venezuela Ap. 47567, Caracas Favaron, O., P. Mago and 0. Ordaz, On the bipartite independence number of a balanced bipartite graph, Discrete Mathematics 121 (1993) 55-63. The bipartite independence number GI aIp of a bipartite graph G is the maximum order of a balanced independent set of G. Let 6 b

On the Maximum Number of Independent Cyc
On the Maximum Number of Independent Cycles in a Bipartite Graph
✍ Hong Wang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 404 KB

Let G=(V 1 , V 2 ; E ) be a bipartite graph with |V 1 |= |V 2 | =n 2k, where k is a positive integer. Suppose that the minimum degree of G is at least k+1. We show that if n>2k, then G contains k vertex-disjoint cycles. We also show that if n=2k, then G contains k&1 quadrilaterals and a path of orde

Sharp bounds for the number of 3-indepen
Sharp bounds for the number of 3-independent partitions and the chromaticity of bipartite graphs
✍ F. M. Dong; K. M. Koh; K. L. Teo; C. H. C. Little; M. D. Hendy 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 233 KB

## Abstract Given a graph __G__ and an integer __k__ ≥ 1, let α(__G, k__) denote the number of __k__‐independent partitions of __G__. Let 𝒦^−s^(__p,q__) (resp., 𝒦~2~^−s^(__p,q__)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph __K~p,q

The average distance and the independenc
The average distance and the independence number
✍ F. R. K. Chung 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB

We prove that in every connected graph the independence number is at least as large as the average distance between vertices. Theorem. For every connected graph G , we have a ( G ) 2 D ( G ) , with equality if and only if G is a complete graph.