Premium
On covering an independent set in a grid with a second independent set
Author(s) -
Rue Rachel
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199612)23:4<385::aid-jgt8>3.0.co;2-n
Subject(s) - disjoint sets , combinatorics , mathematics , independent set , set (abstract data type) , grid , maximal independent set , discrete mathematics , property (philosophy) , computer science , geometry , graph , programming language , philosophy , pathwidth , epistemology , line graph
We show that for every independent set O in an n × m grid, n, m > 1, there is a second independent set X with the property that every member of O is adjacent to at 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. © 1996 John Wiley & Sons, Inc.