Every tree on $n$ edges decomposes $K_{nx,nx}$ and $K_{2nx+1}$
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929616469360640 |
|---|---|
| author | Chalise, Parikshit Clark, Antwan Gnang, Edinah K. |
| author_facet | Chalise, Parikshit Clark, Antwan Gnang, Edinah K. |
| contents | We prove that every tree on $n$ edges decomposes $K_{nx,nx}$ and $K_{2nx + 1}$ for all positive integers $x$. The said decompositions are obtained by proving that every tree admits a $\vecβ$-labeling (oriented beta-labeling). Our proof employs the polynomial method by identifying trees as functions in the transformation monoid $\mathbb{Z}_n^{\mathbb{Z}_n}$. A proof of the graceful tree conjecture (1967) follows as an immediate consequence of the current result. Finally, we introduce additional algebraic properties derived from the decomposition results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_01981 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Every tree on $n$ edges decomposes $K_{nx,nx}$ and $K_{2nx+1}$ Chalise, Parikshit Clark, Antwan Gnang, Edinah K. Combinatorics 05C51, 05C78 G.2.2 We prove that every tree on $n$ edges decomposes $K_{nx,nx}$ and $K_{2nx + 1}$ for all positive integers $x$. The said decompositions are obtained by proving that every tree admits a $\vecβ$-labeling (oriented beta-labeling). Our proof employs the polynomial method by identifying trees as functions in the transformation monoid $\mathbb{Z}_n^{\mathbb{Z}_n}$. A proof of the graceful tree conjecture (1967) follows as an immediate consequence of the current result. Finally, we introduce additional algebraic properties derived from the decomposition results. |
| title | Every tree on $n$ edges decomposes $K_{nx,nx}$ and $K_{2nx+1}$ |
| topic | Combinatorics 05C51, 05C78 G.2.2 |
| url | https://arxiv.org/abs/2409.01981 |