๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On covering an independent set in a grid with a second independent set

โœ Scribed by Rue, Rachel

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
1011 KB
Volume
23
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

โœฆ Synopsis

We show that for every independent set 0 in an n x m grid, n, m > 1, there is a second independent set X with the property that every member of 0 is adjacent to a t least one member of X. The proof gives a construction for X. Equivalently, we show that for every maximal independent set in a grid, there is a second, disjoint, maximal independent set.

๐Ÿ“œ SIMILAR VOLUMES

A note on cliques and independent sets
A note on cliques and independent sets
โœ Entringer, Roger C.; Goddard, Wayne; Henning, Michael A. ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 58 KB ๐Ÿ‘ 2 views

For integers m, n โ‰ฅ 2, let f (m, n) be the minimum order of a graph where every vertex belongs to both a clique of cardinality m and an independent set of cardinality n. We show that f (m, n) = ( โˆš m -1 + โˆš n -1) 2 .

Independent Dominating Sets and a Second
Independent Dominating Sets and a Second Hamiltonian Cycle in Regular Graphs
โœ Carsten Thomassen ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 241 KB

In 1975, John Sheehan conjectured that every Hamiltonian 4-regular graph has a second Hamiltonian cycle. Combined with earlier results this would imply that every Hamiltonian r-regular graph (r 3) has a second Hamiltonian cycle. We shall verify this for r 300.

Decomposing a Planar Graph into an Indep
Decomposing a Planar Graph into an Independent Set and a 3-Degenerate Graph
โœ Carsten Thomassen ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 126 KB

We prove the conjecture made by O. V. Borodin in 1976 that the vertex set of every planar graph can be decomposed into an independent set and a set inducing a 3-degenerate graph.