2022/08/12 by Etgar, Asaf, Linial, Nati
#05 #51 #68 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2208.06324
A graph G is geodetic if between any two vertices there exists a unique shortest path. In 1962 Ore raised the challenge to characterize geodetic graphs, but despite many attempts, such characterization still seems well beyond reach. We may assume, of course, that G is 2-connected, and here we consider only graphs with no vertices of degree 1 or 2. We prove that all such graphs are, in fact 3-connected. We also construct an infinite family of such graphs of the largest known diameter, namely 5.