Some Locally Kneser Graphs
The Kneser graph $K(n,d)$ is the graph on the $d$-subsets of an $n$-set, adjacent when disjoint. Clearly, $K(n+d,d)$ is locally $K(n,d)$. Hall showed for $n \ge 3d+1$ that there are no further examples. Here we give other examples of locally $K(n,d)$ graphs for $n = 3d$, and some further sporadic examples. It follows that Hall's bound is best possible.
Authors
- Andries Brouwer
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2024-10-18
- DOI
- https://doi.org/10.37236/12621
- Primary Topic
- Graph Labeling and Dimension Problems
- Type
- article
- Field-Weighted Citation Impact
- 0.00