Statistics of maximal independent sets in grid-like graphs

Abstract

An independent set $I$ in a graph $G$ is maximal if $I$ is not properly contained in any other independent set of $G$. The study of maximal independent sets (MIS's) in various graphs is well-established, often focusing upon enumeration of the set of MIS's. For an arbitrary graph $G$, it is typically quite difficult to understand the number and structure of MIS's in $G$; however, when $G$ has regular structure, the problem may be more tractable. One class of graphs for which enumeration of MIS's is fairly well-understood is the rectangular grid graphs $G_{m\times n}$. We say a graph is grid-like if it is locally isomorphic to a square grid, though the global structure of such a graph might resemble a surface such as a torus or Möbius strip. We study the properties of MIS's in various types of grid-like graphs, in particular determining parity of the set of MIS's, average size of MIS's, and number of pairwise non-isomorphic MIS's in various grid-like graphs.

24 pages, 2 figures