تقرير
On extremal factors of de Bruijn-like graphs
| العنوان: | On extremal factors of de Bruijn-like graphs |
|---|---|
| المؤلفون: | Álvarez, Nicolás, Becher, Verónica, Mereb, Martín, Pajor, Ivo, Soto, Carlos Miguel |
| المصدر: | Discrete Applied Mathematics 357 (2024) 352-364 |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - 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. |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.1016/j.dam.2024.06.010 |
| URL الوصول: | http://arxiv.org/abs/2308.16257 |
| رقم الأكسشن: | edsarx.2308.16257 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.1016/j.dam.2024.06.010 |
|---|