论文标题
关于大地图的连通性和直径
On the Connectivity and Diameter of Geodetic Graphs
论文作者
论文摘要
如果在任何两个顶点之间存在一个独特的最短路径，则图形$ g $是大地测量的。 1962年，矿石提出了表征大地图的挑战，但是尽管有许多尝试，但这种表征似乎仍然无法触及。当然，我们可以假设$ g $是$ 2 $连接的，在这里，我们仅考虑没有$ 1 $或$ 2 $的顶点的图表。我们证明所有这些图形实际上是$ 3 $连接的。我们还构建了一个无限的图形，即最大的已知直径，即$ 5 $。
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$.
