On graphs with unique geodesics or antipodes

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 the properties of geodetic, as well as antipodal graphs, in each vertex of which has exactly one antipode (the vertex farthest from it). We find necessary and sufficient conditions and obtain results related to algorithmic construction, investigate hamiltonian geodetic graphs, introduce and describe maximal hereditary subclass and minimal hereditary superclass of classes of geodetic and antipodal graphs. The main goal of the research is a constructive classification of these graphs.

Category: MATHEMATICS Country: BELARUS Year: 2020