Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.22317 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913915500232704 |
|---|---|
| author | Axelrod, Levi Bickel, Nathan Halfpap, Anastasia Hawranick, Luke Parker, Alex Swain, Cole |
| author_facet | Axelrod, Levi Bickel, Nathan Halfpap, Anastasia Hawranick, Luke Parker, Alex Swain, Cole |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_22317 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Statistics of maximal independent sets in grid-like graphs Axelrod, Levi Bickel, Nathan Halfpap, Anastasia Hawranick, Luke Parker, Alex Swain, Cole Combinatorics 05A15, 05A16 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. |
| title | Statistics of maximal independent sets in grid-like graphs |
| topic | Combinatorics 05A15, 05A16 |
| url | https://arxiv.org/abs/2506.22317 |