Tetravalent distance magic graphs of small order and an infinite family of examples
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_ | 1866909731621175296 |
|---|---|
| author | Rozman, Ksenija Šparl, Primož |
| author_facet | Rozman, Ksenija Šparl, Primož |
| contents | A graph of order $n$ is distance magic if it admits a bijective labeling of its vertices with integers from $1$ to $n$ such that each vertex has the same sum of the labels of its neighbors.
This paper contributes to the long term project of characterizing all tetravalent distance magic graphs. With the help of a computer we find that out of almost nine million connected tetravalent graphs up to order $16$ only nine are distance magic. In fact, besides the six well known wreath graphs there are only three other examples, one of each of the orders $12$, $14$ and $16$. We introduce a generalization of wreath graphs, the so-called quasi wreath graphs, and classify all distance magic graphs among them. This way we obtain infinitely many new tetravalent distance magic graphs. Moreover, the two non-wreath graphs of orders $12$ and $14$ are quasi wreath graphs while the one of order $16$ can be obtained from a quasi wreath graph of order $14$ using a simple construction due to Kovář, Fronček and Kovářová. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_09033 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Tetravalent distance magic graphs of small order and an infinite family of examples Rozman, Ksenija Šparl, Primož Combinatorics 05C78 A graph of order $n$ is distance magic if it admits a bijective labeling of its vertices with integers from $1$ to $n$ such that each vertex has the same sum of the labels of its neighbors. This paper contributes to the long term project of characterizing all tetravalent distance magic graphs. With the help of a computer we find that out of almost nine million connected tetravalent graphs up to order $16$ only nine are distance magic. In fact, besides the six well known wreath graphs there are only three other examples, one of each of the orders $12$, $14$ and $16$. We introduce a generalization of wreath graphs, the so-called quasi wreath graphs, and classify all distance magic graphs among them. This way we obtain infinitely many new tetravalent distance magic graphs. Moreover, the two non-wreath graphs of orders $12$ and $14$ are quasi wreath graphs while the one of order $16$ can be obtained from a quasi wreath graph of order $14$ using a simple construction due to Kovář, Fronček and Kovářová. |
| title | Tetravalent distance magic graphs of small order and an infinite family of examples |
| topic | Combinatorics 05C78 |
| url | https://arxiv.org/abs/2310.09033 |