A characterization of regular partial cubes whose all convex cycles have the same lengths
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_ | 1866909346955264000 |
|---|---|
| author | Xie, Yan-Ting Feng, Yong-De Xu, Shou-Jun |
| author_facet | Xie, Yan-Ting Feng, Yong-De Xu, Shou-Jun |
| contents | Partial cubes are graphs that can be isometrically embedded into hypercubes. Convex cycles play an important role in the study of partial cubes. In this paper, we prove that a regular partial cube is a hypercube (resp., a Doubled Odd graph, an even cycle of length $2n$ where $n\geqslant 4$) if and only if all its convex cycles are 4-cycles (resp., 6-cycles, $2n$-cycles). In particular, the partial cubes whose all convex cycles are 4-cycles are equivalent to almost-median graphs. Therefore, we conclude that regular almost-median graphs are exactly hypercubes, which generalizes the result by Mulder [J. Graph Theory, 4 (1980) 107--110] -- regular median graphs are hypercubes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_12200 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A characterization of regular partial cubes whose all convex cycles have the same lengths Xie, Yan-Ting Feng, Yong-De Xu, Shou-Jun Combinatorics 05C75 Partial cubes are graphs that can be isometrically embedded into hypercubes. Convex cycles play an important role in the study of partial cubes. In this paper, we prove that a regular partial cube is a hypercube (resp., a Doubled Odd graph, an even cycle of length $2n$ where $n\geqslant 4$) if and only if all its convex cycles are 4-cycles (resp., 6-cycles, $2n$-cycles). In particular, the partial cubes whose all convex cycles are 4-cycles are equivalent to almost-median graphs. Therefore, we conclude that regular almost-median graphs are exactly hypercubes, which generalizes the result by Mulder [J. Graph Theory, 4 (1980) 107--110] -- regular median graphs are hypercubes. |
| title | A characterization of regular partial cubes whose all convex cycles have the same lengths |
| topic | Combinatorics 05C75 |
| url | https://arxiv.org/abs/2301.12200 |