Quasiperiods of Magic Labeling Quasipolynomials
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_ | 1866913256680980480 |
|---|---|
| author | Bayer, Margaret Burcroff, Amanda McAllister, Tyrrell B. Pai, Leilani |
| author_facet | Bayer, Margaret Burcroff, Amanda McAllister, Tyrrell B. Pai, Leilani |
| contents | A magic labeling of a graph is a labeling of the edges by nonnegative integers such that the label sum over the edges incident to every vertex is the same. This common label sum is known as the index. We count magic labelings by maximum edge label, rather than index, using an Ehrhart-theoretic approach. In contrast to Stanley's 1973 work showing that the function counting magic labelings with bounded index is a quasipolynomial with quasiperiod $2$, we show by construction that the minimum quasiperiod of the quasipolynomial counting magic labelings with bounded maximum label can be arbitrarily large, even for planar bipartite graphs. Unfortunately, this rules out a certain Ehrhart-theoretic approach to proving Hartsfield and Ringel's Antimagic Graph Conjecture. However, we show that this quasipolynomial is in fact a polynomial for any bipartite graph with matching preclusion number at most $1$, which includes any bipartite graph with a leaf. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_04129 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quasiperiods of Magic Labeling Quasipolynomials Bayer, Margaret Burcroff, Amanda McAllister, Tyrrell B. Pai, Leilani Combinatorics 05C78 (Primary) 52B20, 05C30 (Secondary) A magic labeling of a graph is a labeling of the edges by nonnegative integers such that the label sum over the edges incident to every vertex is the same. This common label sum is known as the index. We count magic labelings by maximum edge label, rather than index, using an Ehrhart-theoretic approach. In contrast to Stanley's 1973 work showing that the function counting magic labelings with bounded index is a quasipolynomial with quasiperiod $2$, we show by construction that the minimum quasiperiod of the quasipolynomial counting magic labelings with bounded maximum label can be arbitrarily large, even for planar bipartite graphs. Unfortunately, this rules out a certain Ehrhart-theoretic approach to proving Hartsfield and Ringel's Antimagic Graph Conjecture. However, we show that this quasipolynomial is in fact a polynomial for any bipartite graph with matching preclusion number at most $1$, which includes any bipartite graph with a leaf. |
| title | Quasiperiods of Magic Labeling Quasipolynomials |
| topic | Combinatorics 05C78 (Primary) 52B20, 05C30 (Secondary) |
| url | https://arxiv.org/abs/2403.04129 |