Graphs with Independent Exact $r$-covers for all $r$
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913782540795904 |
|---|---|
| author | Chau, Hou Tin |
| author_facet | Chau, Hou Tin |
| contents | For every natural number $d$, we construct finite $d$-regular simple graphs that, for every $r \le d$, contain an independent exact $r$-cover. This answers a question of Gray and Johnson that arose in their study of 2-step transit probabilities.
We obtain some divisibility conditions on the order $n$ of graphs that for every $r \le d$ contain an independent exact $r$-cover, and give constructions for $d=3, 4, 5, 6$ where the order of the graph is minimal (we deduce this minimality from our divisibility conditions). We construct these graphs as common coverings of smaller graphs. We revisit a result of Angluin and Gardiner on finite common coverings of two regular graphs of the same degree, and the result of Gross that regular graphs of even degree are Schreier coset graphs. We combine both results to provide a finite common covering of two regular graphs of the same degree, that uses fewer vertices than the construction of Angluin and Gardiner in some cases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_05854 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graphs with Independent Exact $r$-covers for all $r$ Chau, Hou Tin Combinatorics 05C69 (Primary) 05C35, 05C76 (Secondary) For every natural number $d$, we construct finite $d$-regular simple graphs that, for every $r \le d$, contain an independent exact $r$-cover. This answers a question of Gray and Johnson that arose in their study of 2-step transit probabilities. We obtain some divisibility conditions on the order $n$ of graphs that for every $r \le d$ contain an independent exact $r$-cover, and give constructions for $d=3, 4, 5, 6$ where the order of the graph is minimal (we deduce this minimality from our divisibility conditions). We construct these graphs as common coverings of smaller graphs. We revisit a result of Angluin and Gardiner on finite common coverings of two regular graphs of the same degree, and the result of Gross that regular graphs of even degree are Schreier coset graphs. We combine both results to provide a finite common covering of two regular graphs of the same degree, that uses fewer vertices than the construction of Angluin and Gardiner in some cases. |
| title | Graphs with Independent Exact $r$-covers for all $r$ |
| topic | Combinatorics 05C69 (Primary) 05C35, 05C76 (Secondary) |
| url | https://arxiv.org/abs/2501.05854 |