𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Neighborhood conditions for balanced independent sets in bipartite graphs

✍ Scribed by Denise Amar; Stephan Brandt; Daniel Brito; Oscar Ordaz

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
319 KB
Volume
181
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a balanced bipartite graph of order 2n and minimum degree 6(G)>~3. If, for every balanced independent set S of four vertices, IN(S)I >n then G is traceable, the circumference is at least 2n -2 and G contains a 2-factor (with only small order exceptional graphs for the latter statement). If the neighborhood union condition is replaced by IN(S)I >n + 2 then G is hamiltonian.

πŸ“œ SIMILAR VOLUMES

Maximal independent sets in bipartite gr
Maximal independent sets in bipartite graphs
✍ Jiuqiang Liu πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 458 KB πŸ‘ 1 views

## Abstract A maximal independent set of a graph __G__ is an independent set that is not contained properly in any other independent set of __G.__ In this paper, we determine the maximum number of maximal independent sets among all bipartite graphs of order __n__ and the extremal graphs as well as

Approximation Algorithms for Independent
Approximation Algorithms for Independent Sets in Map Graphs
✍ Zhi-Zhong Chen πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 172 KB

This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, then a ratio of 1 + Ξ΄ can be achieved by a quadratic-time algorithm for any given con

Edge proximity conditions for extendabil
Edge proximity conditions for extendability in cubic bipartite graphs
✍ R. E. L. Aldred; Bill Jackson πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 123 KB

## Abstract We show that a set __M__ of __m__ edges in a cyclically (3__m__β€‰βˆ’β€‰2)‐edge‐connected cubic bipartite graph is contained in a 1‐factor whenever the edges in __M__ are pairwise distance at least __f__(__m__) apart, where Β© 2007 Wiley Periodicals, Inc. J Graph Theory 55: 112–120, 2007