On graphs with unique geoodesics and antipodes
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910287482847232 |
|---|---|
| author | Gorovoy, Dmitriy Zmiaikou, David |
| author_facet | Gorovoy, Dmitriy Zmiaikou, David |
| contents | In 1962, Oystein Ore asked in which graphs there is exactly one geodesic between any two vertices. He called such graphs geodetic. In this paper, we systematically study properties of geodetic graphs, and also consider antipodal graphs, in which each vertex has exactly one antipode (a farthest vertex). We find necessary and sufficient conditions for a graph to be geodetic or antipodal, obtain results related to algorithmic construction, and find interesting families of Hamiltonian geodetic graphs. By introducing and describing the maximal hereditary subclasses and the minimal hereditary superclasses of the geodetic and antipodal graphs, we get close to the goal of our research -- a constructive classification of these graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_09987 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | On graphs with unique geoodesics and antipodes Gorovoy, Dmitriy Zmiaikou, David Combinatorics In 1962, Oystein Ore asked in which graphs there is exactly one geodesic between any two vertices. He called such graphs geodetic. In this paper, we systematically study properties of geodetic graphs, and also consider antipodal graphs, in which each vertex has exactly one antipode (a farthest vertex). We find necessary and sufficient conditions for a graph to be geodetic or antipodal, obtain results related to algorithmic construction, and find interesting families of Hamiltonian geodetic graphs. By introducing and describing the maximal hereditary subclasses and the minimal hereditary superclasses of the geodetic and antipodal graphs, we get close to the goal of our research -- a constructive classification of these graphs. |
| title | On graphs with unique geoodesics and antipodes |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2111.09987 |