On the clique covering numbers of Johnson graphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908408387469312 |
|---|---|
| author | Jørgensen, Søren Fuglede |
| author_facet | Jørgensen, Søren Fuglede |
| contents | We initiate a study of the vertex clique covering numbers of Johnson graphs $J(N, k)$, the smallest numbers of cliques necessary to cover the vertices of those graphs.
We prove identities for the values of these numbers when $k \leq 3$, and $k \geq N - 3$, and using computational methods, we provide explicit values for a range of small graphs. By drawing on connections to coding theory and combinatorial design theory, we prove various bounds on the clique covering numbers for general Johnson graphs, and we show how constant-weight lexicodes can be utilized to create optimal covers of $J(2k, k)$ when $k$ is a small power of two. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_15019 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the clique covering numbers of Johnson graphs Jørgensen, Søren Fuglede Combinatorics We initiate a study of the vertex clique covering numbers of Johnson graphs $J(N, k)$, the smallest numbers of cliques necessary to cover the vertices of those graphs. We prove identities for the values of these numbers when $k \leq 3$, and $k \geq N - 3$, and using computational methods, we provide explicit values for a range of small graphs. By drawing on connections to coding theory and combinatorial design theory, we prove various bounds on the clique covering numbers for general Johnson graphs, and we show how constant-weight lexicodes can be utilized to create optimal covers of $J(2k, k)$ when $k$ is a small power of two. |
| title | On the clique covering numbers of Johnson graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2502.15019 |