On extremal factors of de Bruijn-like graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916336477667328 |
|---|---|
| author | Álvarez, Nicolás Becher, Verónica Mereb, Martín Pajor, Ivo Soto, Carlos Miguel |
| author_facet | Álvarez, Nicolás Becher, Verónica Mereb, Martín Pajor, Ivo Soto, Carlos Miguel |
| contents | In 1972 Mykkeltveit proved that the maximum number of vertex-disjoint cycles in the de Bruijn graphs of order $n$ is attained by the pure cycling register rule, as conjectured by Golomb. We generalize this result to the tensor product of the de Bruijn graph of order $n$ and a simple cycle of size $k$, when $n$ divides $k$ or vice versa. We also develop counting formulae for a large family of cycling register rules, including the linear register rules proposed by Golomb. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_16257 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On extremal factors of de Bruijn-like graphs Álvarez, Nicolás Becher, Verónica Mereb, Martín Pajor, Ivo Soto, Carlos Miguel Combinatorics Discrete Mathematics 05C35, 05C45 In 1972 Mykkeltveit proved that the maximum number of vertex-disjoint cycles in the de Bruijn graphs of order $n$ is attained by the pure cycling register rule, as conjectured by Golomb. We generalize this result to the tensor product of the de Bruijn graph of order $n$ and a simple cycle of size $k$, when $n$ divides $k$ or vice versa. We also develop counting formulae for a large family of cycling register rules, including the linear register rules proposed by Golomb. |
| title | On extremal factors of de Bruijn-like graphs |
| topic | Combinatorics Discrete Mathematics 05C35, 05C45 |
| url | https://arxiv.org/abs/2308.16257 |