# On graphs with unique geoodesics and antipodes

Dmitriy Gorovoy and David Zmiaikou Jagiellonian University, Krakow,
PolandHarbour Space University, Barcelona, Spain

###### Abstract

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.

Key words: geodetic graphs, antipodal graphs, Hamiltonian geodetic graphs,
bearing trees, hereditary subclasses and superclasses

## Introduction

In 1962, in his famous book on graph theory [1], the Norwegian mathematician
Oystein Ore presented a new problem: ‘‘In a tree there is a unique shortest
arc between any two vertices, but there are also other connected graphs with
the same property. Try to characterize these _geodetic_ graphs in other way.‘‘

######  Definition 1.

A _geodesic_ between two vertices of a graph is a shortest path connecting
these vertices.

######  Definition 2.

A graph is called _geodetic_ if for any pair of its vertices there is exactly
one geodesic between them.

See examples of geodetic graphs in the Figure 1.

Analogy with geometry. As we know, in the Euclidean geometry of a space of
zero curvature ($\mathbb{R}^{n}$), as well as in the geometry of Lobachevsky
spaces of negative curvature (hyperbolic half-plane and Poincaré disc) between
any two points there is exactly one geodesic. Geodetic graphs have a discrete
analogue of this property.

Complete graphs

Trees

Odd cycles

Cacti without even cycles

Figure 1: Examples of geodetic graphs.

Applications. Studying the connections between vertices of a graph and finding
criteria for the existence of a configuration of these connections is of
exceptional interest in network modeling. In particular, geodetic graphs are
applied in the design of computer systems and networks (see [3]).

In contrast to the uniqueness of geodesics, the following question naturally
arises: in which graphs does each vertex have exactly one antipode?

######  Definition 3.

An _antipode_ of a given vertex is the vertex farthest from the given one. An
_antipodal graph_ is a connected graph in which each vertex has exactly one
antipode.

See examples of antipodal graphs in the Figure 2.

Analogy with geometry. In the spherical geometry of a space of positive
curvature $\mathbb{S}^{n}$ between two points there can be infinitely many
geodesics, but each point has exactly one antipode. Discrete analogs here are
antipodal graphs.

Even-length cycle

Odd-length path

Some trees

Figure 2: Examples of antipodal graphs.

Goal. The main goal of our research is to describe geodetic and antipodal
graphs explicitly, _i.e._ to find their constructive classifications which
would allow us to build them algorithmically.

Main results. In this article we obtain the following:

  * •

a criterion for any graph with some condition on one of its spanning trees to
be geodetic (Theorem 2);

  * •

a criterion for a tree to be antipodal (Proposition 6);

  * •

two infinite series of Hamiltonian geodetic graphs of diameters two and four
(Theorems 3 and 4);

  * •

a criterion for any graph to be geodetic, $K_{1,3}$-free (Theorem 1);

  * •

algorithms of polynomial complexity $O(n^{3})$ for checking whether a weighted
graph is geodetic/antipodal or not (Theorem 8);

  * •

an algorithm for assigning positive weights to the edges of an arbitrary
connected graph so that it becomes both geodetic and antipodal (Theorem 7);

  * •

the maximal hereditary subclass of the class of geodetic graphs (Theorem 5) ;

  * •

the maximal hereditary subclass and the minimal hereditary superclass of the
class of antipodal graphs (Theorem 6);

  * •

the minimal hereditary superclasses of the classes of weighted geodetic and
antipodal graphs (Theorem 9 for geodetic and Proposition 7 for antipodal
graphs).

##  1 Geodetic and antipodal graph check and bearing trees

######  Lemma 1.

Let $G$ be a connected graph on $n$ vertices. Then it is possible to check
whether the graph $G$ is geodetic/antipodal or not for $O(n^{3})$.

###### Proof.

Let $v_{1},v_{2},...v_{n}$ be vertices of the graph $G$. We will check whether
$G$ is geodetic or not at the steps of constructing the spanning tree $T$ of
the graph $G$. Our algorithm, in fact, is exactly Breadth-first search. Take
the vertex $v_{1}$ as the root of the tree; it constitutes zero tier. Further,
add to $T$ all vertices that are adjacent to $v_{1}$ (together with the edges
from $v_{1}$). Let WLOG these vertices are $v_{2},v_{3},...v_{k}$; they form
tier 1.

Next, add all the neighbors of the vertex $v_{2}$ that have not been
considered earlier; they will form tier 2.

Now we consider the neighbors of the vertex $v_{3}$ in the graph $G$. Two
options for the next step of the algorithm:

  1. 1)

If some of the neighbors $v_{3}$ was not added earlier, add it to tier 2 of
the tree $T$.

  2. 2)

If some of the neighbors of $v_{3}$ is also a neighbor of $v_{2}$ from tier 2,
then we conclude that the graph is not geodetic.

Further, we analogously consider other vertices of the graph $G$. At the end
of the algorithm, we find out if there is exactly one geodesic from $v_{1}$ to
all other vertices.

To build such an algorithm, $O(n^{2})$ is required. Repeating this algorithm,
choosing each vertex as the root of the tree, we need $O(n^{3})$. ∎

######  Definition 4.

A _bearing tree_ of the graph $G$ is the tree $T$, built in the proof of Lemma
1. It’s always true for any bearing tree $T$ that the distance between the
root of the tree and any vertex of the $k$-th tier is equal to $k$ not only in
the tree, but also in the graph $G$ itself. (For an arbitrary spanning tree,
this is not always true, since the distance between vertices of the graph $G$
can be less than the distance between these vertices in its spanning tree).

##  2 Geodetic graphs

###  2.1 Blocks of geodetic graphs

######  Definition 5.

A _balk_ of the bearing tree $T$ is an edge of the graph $G$ with the ends
lying in the same tier of the tree $T$ (see Figure 3).

$1$$2$$3$$4$$5$$6$$7$

$1$$2$$3$$4$$5$$6$$7$$2$$1$$0$

Figure 3: A bearing tree with three balks.

######  Lemma 2.

Let $G$ be a geodetic graph, $T$ its bearing tree. Then any edge $e\in
E(G)\setminus E(T)$ is a balk of $T$.

###### Proof.

All ends of edges not added to $T$ lie either in the same tier or between
adjacent tiers. Indeed, let the vertex $a$ from the tier $l$ be adjacent to
the vertex $b$ from the $l+i$ of the tier, where $i\geq 0$. Then the distance
in the graph $G$ between the root and the vertex $b$ does not exceed $l+1$,
and on the other hand, by the definition of the bearing tree, it is equal to
$l+i$. Therefore, $i$ is equal to 0 or 1. If $i=1$, then the graph is not
geodetic - there are two geodesics between the root and the vertex $b$. Hence,
$i=0$. ∎

######  Definition 6.

Let $T$ be some tree with a root $u$. A _stem_ of a tree $T$ is a path whose
ends are a root $u$ and an arbitrary leaf of the tree. Note that two stems can
intersect.

For example, the tree in the Figure 4 has five stems (one of length 1, two of
length 2, and two of length 3).

$u$$1$$2$$3$$4$$5$ Figure 4: A tree with five stems.

######  Lemma 3.

Let $G$ be a geodetic graph and $T$ be its bearing tree. Then there is at most
one balk between any two stems of the tree $T$.

###### Proof.

Suppose there are two balks between some two stems of the tree $T$ as in the
Figure 5. Consider a pair of vertices $a$ and $d$, there are two paths of
length $l-m+1$ between them (in an even cycle $abdca$). But then, since the
graph is geodetic, there must be a path of length at most $l-m$ between the
vertices $a$ and $d$. Therefore, there are two geodesics from the root of the
tree to the vertex $d$ (one of them passes through $a$).

$\dots$$\dots$$\dots$$\dots$$\dots$$a$$b$$c$$d$$l$$m$ Figure 5: Two balks.

∎

######  Lemma 4.

Let $G$ be a geodetic graph. Then, fixing an arbitrary vertex $v$ of the graph
$G$ as the root of the bearing tree, we get that all vertices of the first
tier of the bearing tree are split into several complete subgraphs of the
graph $G$, perhaps consisting of one vertex.

###### Proof.

Assume the statement of the lemma is incorrect, that is there is some non-
complete connected subgraph $H$ of the graph $G$ in the first tier of the
bearing tree with the root $v$. This means that there is such chain
$u_{1}u_{2}u_{3}$ in $H$ that $u_{1}u_{3}\notin E$. But then there are two
geodesic lengths of two between the vertices $u_{1}$ and $u_{3}$:
$u_{1}vu_{3}$ and $u_{1}u_{2}u_{3}$. Thus we got a contradiction. ∎

######  Definition 7.

A _cut vertex_ of a graph $G$ is a vertex of $G$ such that $G-x$ is a
disconnected graph. A _block_ of a graph is a maximal connected subgraph with
no cut vertex – a subgraph with as many edges as possible and no cut vertex.

######  Lemma 5 (Stemple and Watkins [2]).

A graph $G$ is geodetic if and only if each of its blocks is geodetic.

######  Theorem 1.

Graph $G$ is geodetic, $K_{1,3}$-free if and only if $G$ is either an odd-
length cycle or a graph, each block of which is complete and each vertex of
which belongs to at most two blocks.

###### Proof.

Consider an arbitrary block $H$ of the graph $G$. If the degree of some vertex
from $H$ is less than two, then $H$ is $K_{2}$ or $K_{1}$, otherwise there
would be a cut vertex in the block. In the case when the degree of each vertex
of the given block is equal to two, we get that $H$ is an odd cycle (it cannot
be an even cycle according to the Lemma 5 because even cycle is not a geodetic
graph). Further, consider the case when $H$ contains a vertex of degree at
least 3 and consider a bearing tree $T$ taking this vertex as a root. All
vertices of the first tier are split into several complete subgraphs due to
Lemma 4. Let these complete subgraphs be $K_{m_{1}},...K_{m_{n}}$. If $n\geq
3$, then there is $K_{1,3}$ as an induced subgraph of $G$.

Let $n=2$, and the subgraphs in the first tier are $K_{m_{1}}$ and $K_{m_{2}}$
(note that at least one of the subgraphs contains at least two vertices). Let
us call the set of all stems (See Definition 6) passing through $K_{m_{1}}$
the set $A$, and the set of all stems passing through $K_{m_{2}}$,
respectively, as $B$. There is at least one balk between the stems $A$ and
$B$, since they belong to the same block. Further, consider the uppermost such
balk, let without loss of generality it be in the $k$-th tier between the
stems $s_{2}$ from $A$ and $s_{3}$ from $B$, and let $m_{1}\geq 2$ (see Figure
6). Then there are two different paths of length $k+1$ between the vertices
$u$ and $w$ in the Figure 6 (one passes through the root of the tree $T$ and
the other contains all edges of the stem $s_{2}$ between tier 1 and tier $k$
and two balks between $s_{1}$, $s_{2}$ and $s_{2}$, $s_{3}$). Therefore, there
must be a path of length at most $k$ between these vertices. On the other
hand, the distance between the vertices of tiers $1$ and $k$ is at least
$k-1$, and since the stems from $A$ and $B$ do not intersect at the vertices
except for the root (by the Lemma 2), there must be a balk between the stems.
Therefore, the distance between $u$ and $w$ is at least $k$. And since there
are no balks above the $k$-th tier, there is some stem $s_{1}$ passing through
$u$, from which a balk goes to $s_{3}$ in the $k$-th tier. But then consider
the induced subgraph of the graph $G$ with vertices $w,t_{1},t_{2},t_{3}$ (see
Figure 6). Note that there can be no edges between $t_{3}$ and $t_{1},t_{2}$
(by the Lemma 2). There cannot be an edge $t_{1}t_{2}$ by the Lemma 3.
Therefore, this subgraph is isomorphic to $K_{1,3}$.

$\dots$$\dots$$s_{1}$$s_{2}$$s_{3}$$w$$t_{1}$$t_{2}$$t_{3}$$K_{m_{2}}$$K_{m_{1}}$$u$$k$$1$
Figure 6: The case $n=2$ .

Thus, $n=1$ for some vertex $v$ of degree at least three. Then, fixing $v$ as
the root of the bearing tree, we get that the block $H$ is complete. Indeed,
all stems of the tree pass through some vertices of the first tier. But if
there are some vertices in the second tier, then there is at least one balk
between stems, passing through different vertices of the first tier (as $H$ is
two-connected). But then we get contradiction with Lemma 3 as there is already
a balk between these stems in the first tier. Now, knowing what blocks can be,
let’s find out how they can intersect at vertices. An odd cycle on more than 3
vertices cannot intersect with any of the other blocks, otherwise $K_{1,3}$
will appear. It is also obvious that one vertex cannot belong to three blocks
– complete graphs. On the other hand, it is easy to check using Lemma 5 that
the graphs described in the statement of the theorem satisfy the condition and
are geodetic and $K_{1,3}$-free. ∎

######  Corollary 1.

Let some geodetic two-connected non-complete graph $G$ contains a clique on
$m>1$ vertices. Then the graph $G$ contains $K_{1,m}$ as an induced subgraph.

###### Proof.

Let’s fix some vertex $v$ of the clique $K_{m}$, which has a neighbor outside
the clique, as the root of the bearing tree of the graph $G$. Consider the
highest balk between stems containing at least one vertex of $K_{m}$ other
than $v$ and a stem intersecting with $K_{m}$ only at the vertex $v$. Such
balk exists as the graph $G$ is two-connected. Then the rest of the proof is
analogous to the proof of the Theorem 1, where instead of $t_{1}$ and $t_{2}$
in the $k$-th tier there will be vertices $t_{1},\dots t_{m-1}$. ∎

######  Proposition 1.

Let $k$ be an even natural number and $G$ be some graph. Consider a graph
$G(k)$ obtained from $G$ by adding $k$ vertices on each of its edges. A graph
$G(k)$ is geodetic if and only if $G$ is geodetic.

###### Proof.

Sufficiency. Consider a geodetic graph $G$ and prove that $G(k)$ is also
geodetic.

  1. (a)

Geodesics between old vertices from $G$: if the distance between two vertices
in the graph $G$ was equal to $r$, it will become $(k+1)r$. Suppose that there
is not one geodesic in $G(k)$ between corresponding vertices. Then there is
also not one geodesic in the initial graph between the considered vertices.

  2. (b)

Geodesic between the new vertex $a$ and the old $b$: let $a$ vertex appear on
the edge of $uv$, where $u$ and $v$ are the old vertices. Then geodesics from
$b$ to $a$ pass either through $u$ or through $v$. If through exactly one of
them, then according to the previous subparagraph there is exactly one
geodesic between $a$ and $b$. Let there be two geodesics between the vertices
and they pass through $u$ and $v$. Then the distance from $b$ to $u$ and the
distance from $b$ to $v$ are divisible by $k+1$, and the distances from $u$ to
$a$ and from $v$ to $a$ are not equal as $k$ is even. Thus two considered
distances have different remainders modulo $k+1$. Hence the geodesic is
unique.

  3. (c)

Geodesic between two new vertices, let $u$ and $v$, which lie on the edges
$ab$ and $cd$, where $a,b,c,d$ are old vertices (see Figure 7):

$...$$...$$...$$...$$a$$u$$b$$c$$d$$v$ Figure 7: Geodesic between new
vertices.

Let there be two geodesics between $u$ and $v$. Then it is obvious that both
geodesics cannot pass through the vertex $a$, since otherwise this case would
contradict to the case (b). Then, without loss of generality, let one of the
geodesics pass through $a$ and $c$, and the second through $b$ and $d$. Let’s
say $d(u,a)=x$, $d(v,c)=y$, then $d(u,b)=k+1-x$, $d(v,d)=k+1-y$. Also note
that $k+1|d(a,c)$ and $k+1|d(b,d)$. Therefore, we assume that
$d(u,a)+d(v,c)+d(a,c)=d(u,b)+d(v,d)+d(b,d)$, that is, $d(u,a)+d(v,c)\equiv
d(u,b)+d(v,d)\pmod{k+1}$, which is equivalent to $k+1|2(x+y)$. Since $k+1$ is
odd and $x+y<2(k+1)$, then $x=k+1-y$. But then $d(a,c)=d(b,d)$, that is, from
$a$ there are two paths to the vertex $d$ of length $d(a,c)+k+1$ Therefore,
since the initial graph $G$ is geodetic, there is a path of the length no more
than $d(a,c)$ between the vertices $a$ and $d$, similarly we get that there is
a path of length no more than $d(a,c)$ between the vertices $b$ and $c$. But
then $d(b,c)+d(c,v)\geq d(b,d)+d(d,v)$ since the geodesic from $u$ to $v$ goes
through $b$ and $d$, that is, $d(c,v)\geq d(d,v)$ and similarly, considering
the geodesic through the vertex $a$, we get that $d(d,v)\geq d(c,v)$, which
cannot be true as $k$ is even.

Necessity. Consider a non-geodetic graph $G$ and prove that $G(k)$ is also
non-geodetic:

Let there be two geodesics between the vertices $a$ and $b$ of the graph $G$.
Suppose in $G(k)$ between $a$ and $b$ there is a path shorter than the
geodesics of $G$ with the added $k$ vertices on each edge. But then there was
a shorter path in the initial graph. Hence, in $G(k)$ there are two geodesics
between the vertices $a$ and $b$. ∎

###  2.2 Bearing trees and stems

######  Proposition 2.

Let $T$ be the bearing tree of the geodetic graph $G$, any two stems of which
intersect only at the root. And let $T$ contains three stems $s_{1}$, $s_{2}$
and $s_{3}$, such that there are 2 balks between the stems $s_{1}$, $s_{2}$
and $s_{2}$, $s_{3}$. Then there is a balk between the stem $s_{1}$ and the
stem $s_{3}$. Moreover, two balks are drawn in the same tier, and the third is
not lower (see Figure 8).

###### Proof.

See Figure 8. Consider a pair of vertices $w$ and $b$, between them are two
paths of length $k-m+2$ (in an even cycle formed by stem $1$ (path from the
root to the vertex $b$), stem $3$ (path from the root to the vertex $v$), part
of the stem 2 (path from the vertex $u$ to the vertex $c$) and two balks $uv$
and $bc$). And this means that there is a path of the length at least $k-m+1$
between $w$ and $b$, but note that moving from the $m$-th tier to the $k$-th
tier we use at least $k-m$ edges, and at least one more edge to get from one
stem to another stem. So, this edge must be in one of the tiers from $m$ to
$k$.

$\dots$$\dots$$\dots$$\dots$$b$$c$$d$$v$$w$$u$$k$$m$$1$$2$$3$ Figure 8: Two
balks between stems that have no common vertices.

Further, taking the two <<highest>> edges between the stems, we get that the
third edge must be no lower than two others, using Lemma 3. If two edges are
drawn between the stems in the same tier, then the third edge will not be
lower than them. ∎

######  Proposition 3.

Let $T$ be the bearing tree of the geodetic graph $G$, any two stems of which
intersect only at the root. Let $n\geq 2$ and $k$ $\in\mathbb{N}$, and
$s_{0},s_{1},\dots,s_{n}$ be the stems of the tree $T$, such that there is a
balk in the $k$-th tier between the stem $s_{0}$ and each of the stems
$s_{1},\dots,s_{n}$. Then the vertices of the stems $s_{1},\dots,s_{n}$ induce
a complete subgraph of the graph $G$ in some of the tiers not lower than the
$k$-th.

###### Proof.

The case where $n=2$ was considered in Proposition 2. Further, consider the
case $n=3$ (see Figure 9).

$\dots$$\dots$$\dots$$\dots$$\dots$$\dots$$m$$l$$k$$1$$s_{0}$$s_{1}$$s_{2}$$s_{3}$$a$$b$$c$$e$$d$$f$
Figure 9: There is a vertex with $n$ balks going out of it.

According to Proposition 2 there are balks in tiers not lower than $k$ between
all $s_{i}$ and $s_{j}$ $i,j\geq 1$. Suppose two of them lie in different
tiers, without loss of generality, let them be the balks between the stems
$s_{1}$ and $s_{2}$; $s_{2}$ and $s_{3}$. From the same Proposition 2 it
follows that there is an edge between the vertices of the stems $s_{1}$ and
$s_{3}$; there is a balk in the $l$-th tier (Figure 9) since the balk between
the stems $s_{2}$ and $s_{3}$ is lower than the balk between the stems $s_{1}$
and $s_{2}$ (we assume this without loss of generality). Then consider the
cycle $abcdefa$ whose length is equal to $2(k-l+2)$ (see Figure 9). Note that
between the vertices $b$ and $e$ there are two paths of length $k-l+2$ in this
cycle. Also, since the difference between the tiers is $k-l$, there must be a
balk between the stems $s_{1}$ and $s_{2}$ in one of the tiers between $l$ and
$k$. Then we get a contradiction with the fact that the balk between the stems
$s_{2}$ and $s_{3}$ is lower than the balk between the stems $s_{1}$ and
$s_{2}$.

Next, we prove by mathematical induction that the statement of the proposition
is also true for $n$ balks outgoing from one vertex. The base for three balks
is discussed above. Induction step: let the statement be true for $n=p$, then
we will prove it for $n=p+1$. Consider triples of stems $s_{i},\ s_{j},\
s_{p+1}$ for $1\leq i,j\leq p$. Then, according to the statement proved above
for three arbitrary stems, between $s_{i}$ and $s_{p+1}$; $s_{j}$ and
$s_{p+1}$ there are balks in the same tier as the edge between $s_{i}$ and
$s_{j}$. ∎

We denote by $K_{n}^{\phi}$ a graph that is homeomorphic to a complete graph
$K_{n}$ with nodes $u_{r}$ $(r=1,2,…,n)$ together with a function $\phi$ which
assigns non-negative integers $\phi(u_{r})$ to the nodes such that, given two
nodes $u_{r}$ and $u_{s}$ of $K_{n}^{\phi}$,
$|d(u_{r},u_{s})|=\phi(u_{r})+1+\phi(u_{s})$. Where $d(u,v)$ is the distance
between vertices $u$ and $v$.

######  Lemma 6 (Stemple, Joel G [9]).

A graph G homeomorphic to a complete graph $K_{n}$ is geodetic if and only if
it is a $K_{n}^{\phi}$ graph.

######  Definition 8.

Let $G$ be a connected graph, $T$ its bearing tree, and $H$ some subgraph of
$G$. Suppose that either $H$ is a connected part of some stem of the tree $T$,
or all vertices of $H$ lie in the stems $s_{0},\dots s_{n}$ and there exist
natural numbers $k$ and $l\leq k$ such that the set of all edges $H$ consists
of the following:

  * •

all the edges of the stems $s_{0},\dots s_{n}$ from the root of the tree to
the tier $k$ ($k$ edges in each stem);

  * •

one balk from the stem $s_{0}$ into each of the stems $s_{1},\dots,s_{n}$ in
tier $k$;

  * •

one balk between any two of the stems $s_{1},\dots,s_{n}$ in the tier $l$.

(So, if the subgraph $H$ is not part of one stem, then it has $k(n+1)+1$
vertices and $k(n+1)+\frac{n(n+1)}{2}$ edges.) Then we will say, that the
subgraph $H$ _is transversal_ to the tree $T$.

######  Lemma 7.

Let the graph $G$ be geodetic, $T$ the bearing tree of the graph $G$, any two
stems of which intersect only at the root. And let a subgraph $H$ of the graph
$G$ be transversal to $T$, intersects with $n\geq 1$ stems of the graph $T$.
And let there be some stem $s_{n+1}$ that does not intersect with $H$, but
from which at least one balk goes into one of the stems intersecting with $H$.
Then one can choose a transversal subgraph containing $H$ and intersecting
$s_{n+1}$.

###### Proof.

Let us prove this statement by induction on the number of stems $n$
intersecting $H$. If it intersects with exactly 1 or 2 stems, then Lemma 3 and
Proposition 2 come into force. Induction base for $n=3$:

Suppose that among the first three stems there are two balks in the $k$-th
tier and one in the $l$-th (further in the course of the proof, $k$ and $l$
have the same meaning as in the Definition 8).

  1. 1.

Let the balk from the fourth stem go to one of the first three stems in the
$k$-th tier. If the balk goes to a vertex from which two balks already emerge,
then we get the condition for the Proposition 3. Therefore, we will assume
that the balk goes to another vertex (see Figure 10). Then, according to the
Proposition 2, an edge, marked with a dotted line in the Figure 10, should be
drawn. And then the subgraph induced by a cycle of length 4 is complete (as
the graph is geodetic). So in this case $k=l$.

$\dots$$\dots$$\dots$$\dots$$l$$k$$1$$s_{1}$$s_{2}$$s_{3}$$s_{4}$ Figure 10:
The balk from the fourth stem goes in the same tier as the other two.

  2. 2.

Let the balk from the fourth stem go to one of the first three stems in some
tier with a number not equal to $k$. Then, if the balk goes in the tier above
the $k$-th, then according to Proposition 2 there is a balk in the $k$-th tier
as well, and this case is already considered. Let the balk from the fourth
stem go to some stem in the $a$-th tier, which is lower than $k$.
Then,according to the Proposition 2, there should be balks to all other stems
of the given block in the same tier (see Figure 11). Then Proposition 3 comes
into force, which states that $k=l$ in this case.

$\dots$$\dots$$\dots$$\dots$$\dots$$\dots$$l$$k$$a$$1$$s_{1}$$s_{2}$$s_{3}$$s_{4}$
Figure 11: The balk from the fourth stem goes below.

We will prove the induction step from $n-1$ stems intersecting $H$ to $n$ as
follows:

To begin with, we will prove that if at least one balk from the stem goes to
some stem of $H$, then in fact, balks go from this stem into all stems
intersecting with $H$. Indeed, suppose we have a transversal subgraph $H$ with
$n$ stems $s_{1},\dots s_{n}$ and the stem $s_{n+1}$ from which the balk goes
into the stem $s_{i}$ where $1\leq i\leq n$. Then, since the subgraph $H$ is
transversal, there are balks between any two stems from $H$. Then from $s_{i}$
there are balks to all the other considered stems, as Proposition 2 comes into
force.

Further, suppose we have proved the assertion of the lemma for the $n-1$ stems
intersecting $H$. Let us prove for $n$ stems: let the stems of $H$ be
$s_{1},\dots s_{n}$, and from the stem $s_{n+1}$ there are balks into all
these $n$ stems. And let, without loss of generality, in the stem $s_{1}$
there is a vertex in the lower tier, from which balks go into the stems
$s_{2},\dots s_{n}$ (a vertex in the tier $k$).

  1. 1.

If $k>l$, then in the tier $l$ the vertices of the stems $s_{2},\dots,s_{n}$
induce a complete graph, since these stems form $H$. Then consider the stems
$s_{1},\dots s_{n-1},s_{n+1}$. The first $n-1$ stems form a transversal
subgraph, and there is a balk from $s_{n+1}$ into this subgraph; therefore,
according to the induction hypothesis for the $n-1$ stem, the parts of the
stems $s_{1},\dots s_{n-1},s_{n+1}$ also form a transversal subgraph. Then in
the tier $l$ the vertices of the stems $s_{2},\dots s_{n-1},s_{n+1}$ induce a
complete graph. Indeed, because we have $n-1\geq 3$ and $k>l$, that is, we
have only one option to add to the transversal graph intersecting $n-1$ stems
$s_{1},\dots s_{n-1}$ one more stem, since the tiers $k$ and $l$ are already
fixed, and there can not be two balks between two stems, according to Lemma 3.
Thus, the vertices of the stems $s_{2},\dots s_{n}$ and the stems $s_{2},\dots
s_{n-1},s_{n+1}$ form complete graphs in the tier $l$, and $n-2\geq 2$, that
is, the vertices of the stems $s_{n}$ and $s_{n+1}$ of the stems in the tier
$l$ must also be adjacent, since at least one cycle on 4 vertices is formed,
and since the graph is geodetic this cycle must induce a complete subgraph.

  2. 2.

If $k=l$, that is, vertices of $n$ stems form a complete graph in the $k$-th
tier. Let some balk goes from the stem $s_{n+1}$ in a tier higher than $k$,
let it go into the stem $s_{i}$, then, according to Proposition 2, in the
$k$-th tier there are also balks between $s_{j}$ and $s_{n+1}$, where $1\leq
j\leq n,\ j\neq i$. Then, since $n\geq 4$, there is a cycle on 4 vertices in
the tier $k$ containing the vertices of the stems $s_{i}$ and $s_{n+1}$. The
subgraph induced by this cycle must be complete. So, we got a contradiction
with Lemma 3, since there are two balks between the stems $s_{i}$ and
$s_{n+1}$.

Then let there be at least one balk from $s_{n+1}$ to $s_{i}$ in the $k$-th
tier, then according to Proposition 2, there is a balk between $s_{n+1}$ and
each of the other stems in one of the tiers not lower than $k$, but there
cannot be a balk higher, since this case has already been considered above.
That is, in this case, we get a complete graph in the $k$-th tier in stems
$s_{1},\dots s_{n+1}$.

If there is at least one balk from $s_{n+1}$ to $s_{i}$ in the tier below the
$k$ -th, let it be in the $a$-th tier. Then, according to Proposition 2, there
is a balk from $s_{n+1}$ to all other stems in the same $a$-th tier.

In all cases, we obtained either the impossibility of their existence, or
their transversality. ∎

######  Theorem 2.

Let the graph $G$ be geodetic, $T$ the bearing tree of the graph $G$, any two
stems of which intersect only at the root. A graph $G$ is geodetic if and only
if any of its blocks is transversal to $T$.

The Figure 12 shows a geodetic graph with a bearing tree, as in the theorem.
It has two large transversal blocks (they contain the root of the tree and are
not contained by any stem) and four blocks with one edge (each of them is part
of some stem 111If a path is a block, then the length of this path is equal to
1, otherwise it contains a cut vertex. So a transversal block that is
contained by some stem consists of two vertices connected by an edge.).

###### Proof.

Necessity. Consider an arbitrary block $B$ of the geodetic graph $G$.

Let us prove its transversality by induction on $n$, where $n$ is the number
of stems of the block, parts of which form a transversal subgraph. The base
for one stem is obvious. Step: let for $n$ stems intersecting with a block, we
already know that parts of these stems form a transversal subgraph. Let us
prove that if the block contains some more stems (their parts) other than the
given $n$, then we can choose a transversal subgraph such that $n+1$-th stem
intersects it. Let the transversal subgraph $H^{\prime}$ be formed by the
parts of the stems $s_{1},\dots s_{n}$. Since more than $n$ stems intersect
with a block, there is a stem $s_{n+1}$ that intersects with this block, and
from which the balk goes to one of the first $n$ stems. Indeed, after assuming
the opposite, we get that the block has a cut vertex (the root of the tree).
But then Lemma 7 comes into force, which states that one can choose a
transversal subgraph containing $H^{\prime}$ and part of the stem $s_{n+1}$.

$\dots$$\dots$$\dots$$\dots$$\dots$$Two\ blocks$$Three\ blocks$$One\ blocks$
Figure 12: An example of a geodetic graph with 6 blocks.

As a result, we get that there is a transversal subgraph $H$ contained in $B$.
However, note that there can be no two edges between two stems in a geodetic
graph, and that there are no balks between two different blocks, we get that
in fact our achieved transversal subgraph $H$ is the block $B$. Indeed, the
achieved subgraph $H$ is contained by the same stems that intersect the block
$B$, that is, if there are some vertices or edges in the block $B$ other than
the vertices and edges in the subgraph $H$, then they are contained in the
same stems, but note that there can be no more edges between the stems, since
$H$ has edges between any two stems, and there can be no leafs in the block by
definition.

Sufficiency. From Lemma 6 it follows that every block is geodetic (choosing
for the function $\phi$ in for $K_{n}^{\phi}$ only two vertices, one of which
is the root of the bearing tree), and from Lemma 5 it follows that the whole
graph $G$ is geodetic. ∎

###  2.3 Hamiltonian graphs

Let $\pi_{r}$ denote the projective plane of order $r$.

######  Definition 9.

The _Levi graph_ of the projective plane $\pi_{n}$, denoted by
$Levi(\pi_{n})$, is a graph in which the vertices correspond to lines and
points of the plane and there is an edge between two vertices if and only if
one of the vertices correspond to a point, and the second corresponds to a
line containing this point.

In other words $Levi(\pi_{r})$ is the bipartite graph, associated with an
incidence structure of the projective plane $\pi_{r}$.

######  Lemma 8 (James Singer [5]; Lazebnik, Mellinger, Vega [6]).

The graph $Levi(\pi_{r})$ is Hamiltonian.

The constructions that we independently found and describe in Theorem 3 and
Theorem 4 had also been presented before us in the papers [7] and [8],
respectively. However, the authors did not notice that the graphs are
Hamiltonian.

######  Theorem 3.

For any natural $n$ that is a power of a prime number, there exists a regular
geodetic Hamiltonian graph of diameter four with $(n+1)^{3}+1$ vertices.

###### Proof.

Let us describe an algorithm for constructing the required graph with the
degree of each vertex equal to $n+1$, where $n$ is a power of a prime number.

As well known, there exists a projective plane of order $n$. Consider a
bipartite graph $Levi(\pi_{n})$. Let us denote by $P$ one of its parts. Let
$u$ be any vertex from the second part and $v_{1},\dots,v_{n+1}\in P$ –
adjacent vertices from the first part. We replace $u$ with the complete
subgraph $K_{n+1}$, and instead of edges from $u$ draw exactly one edge from
each vertex of the subgraph into vertices $v_{1},\dots,v_{n+1}$ so that no two
edges were drawn to the same vertex (in fact, it is a bijection from vertices
of $K_{n+1}$ to vertices $v_{1},\dots,v_{n+1}$). Let’s do this with each
vertex from the second part.

Let us prove that the achieved graph $G$ is geodetic, regular, Hamiltonian,
and of diameter 4.

Consider an arbitrary vertex $v$ from $P$. It is possible to get from $v$ to
any other vertex of $P$ moving along three edges. Indeed, take an arbitrary
vertex $v^{\prime}$ from $P$ and consider the complete subgraph of the graph
$G$, with which we have replaced the common neighbor of the vertices $v$ and
$v^{\prime}$ in $Levi(\pi_{n})$. In this complete subgraph, $v$ and
$v^{\prime}$ have exactly one neighbor, and these neighbors are connected by
an edge. So there is a path of length three between $v$ and $v^{\prime}$.
Moreover, such a path is unique, since no other vertices adjacent to $v$ and
$v^{\prime}$ from the second part of the graph $G$ are connected by an edge.
Hence, between any two vertices of $P$ there is exactly one geodesic (of
length 3).

Figure 13: The case $n=2$.

Now take an arbitrary vertex $u$ from the complement $V(G)\setminus V(P)$.
There are two options.

1) If $u$ belongs to the complete subgraph appeared instead of the vertex
which was adjacent to $v$ in $Levi(\pi_{n})$, then between $v$ and $u$ there
is obviously exactly one geodesic (of length 1 or 2).

2) Otherwise, $u$ belongs to the complete subgraph appeared instead of the
vertex which was not adjacent to $v$ in $Levi(\pi_{n})$. The vertex $u$ has
exactly one neighbor $v^{\prime}\neq v$ in the first part $P$, and there is
exactly one geodesic (of length 3) between $v^{\prime}$ and $v$. The path
between $u$ and $v$ that doesn’t go through $v^{\prime}$ has the length more
than 4. Therefore, there is also exactly one geodesic (of length 4) between
$u$ and $v$. The Figure 13 shows an example for $n=2$.

Finally, consider two arbitrary vertices $u,u^{\prime}\in V(G)\setminus V(P)$
from different complete subgraphs. Since in the graph $Levi(\pi_{n})$ any two
vertices from one part have a common neighbor from the other part, and also by
the construction of the graph $G$, we have three cases:

1) $u$ and $u^{\prime}$ have a common vertex in $P$;

2) the neighbor $u$ from its complete subgraph and $u^{\prime}$ has a common
vertex in $P$;

3) the neighbor $u$ from its complete subgraph and the neighbor $u^{\prime}$
from its complete subgraph have a common vertex in $P$.

In all these cases, between $u$ and $u^{\prime}$ we get exactly one geodesic
of length 2, 3, or 4, respectively.

Thus, the graph $G$ is a regular geodetic and of diameter four. Besides,
according to Lemma 8 it’s also Hamiltonian. Indeed, we can consider a cycle
from Lemma 8 and at the moment when the cycle passes through the vertex of the
second part of the graph $Levi(\pi_{n})$, in the graph of the theorem expand
the cycle so that it passes through all the vertices of the complete subgraph.
The Figure 13 shows an example for $n=2$ (Geodetic regular Hamiltonian graph
of diameter four on 28 vertices). ∎

######  Theorem 4.

For any natural $n$ that is a power of a prime number, there exists a geodetic
Hamiltonian graph of diameter two with $2n^{2}+2n+1$ vertices.

###### Proof.

Consider the graph $Levi(\pi_{n})$, where $n$ is a power of a prime number.
Take some Hamiltonian cycle in this graph (it exists according to the Lemma 8)
and choose an arbitrary pair of adjacent vertices $v$ and $v^{\prime}$ in the
cycle. We replace these vertices with one so that it is adjacent to all
neighbors $v$ and $v^{\prime}$. We denote this vertex by $u$.

Further, we connect all neighbors of the vertex $u$ from the first part of the
graph $Levi(\pi_{n})$ with each other and do the same with the vertices of the
second part. Then in the bearing tree $T$ of the achieved graph with the root
$u$ in the first tier there will be two complete subgraphs on $n$ vertices.

Each vertex of the first tier of $T$ has $n$ different neighbors in the second
tier. Then we split the vertices of the first part of the graph
$Levi(\pi_{n})$ from the second tier of the tree $T$ into $n$ groups so that
in each group any two vertices have a common vertex in the first tier, and
connect by an edge all vertices belonging to the same group. So, in the Figure
14 for $n=2$ there will be two groups of such vertices: $\\{1,2\\}$ and
$\\{3,4\\}$. The set of all vertices from these $n$ groups, as well as
adjacent to them vertices from the first tier, will be denoted by $A$.

Let us prove that the obtained graph $G$ satisfies all the conditions of the
theorem.

In the graph $Levi(\pi_{n})$, any two vertices of the same part have exactly
one common neighbor. Then obviously between any two non-adjacent vertices from
$A$ there is the unique path of length two. Similarly, there is a unique path
of length two between any vertex from $A$ from the first tier of $T$ and any
vertex from the set $B=V(G)-A-\\{u\\}$ from the second tier $T$ (such path
cannot pass through $u$ or through another vertex of the first tier $T$ from
$A$). Also obviously there is a unique geodesic from the vertex of the first
tier from $A$ to the vertex of the first tier from $B$ (otherwise such
vertices would have a common neighbor in the second tier, which would
contradict the bipartition of the graph $Levi(\pi_{n})$). The case with
geodesics going out from the vertices of the set $B$ of the first tier $T$ is
considered analogously.

$u$$1$$2$$3$$4$$A$$B$ Figure 14: Geodetic Hamiltonian graph of diameter two on
13 vertices (the case $n=2$).

Consider now two vertices $x$ and $y$ of the graph $G$ from the second tier
$T$.

1) If they both belong to the same set $A$ or $B$, then there is a path of
length one or two between them, since in the graph $Levi(\pi_{n})$ they
correspond to the vertices of the same part. The uniqueness of such geodesic
also follows from the property of the graph $Levi(\pi_{n})$.

2) Let $x\in A$ and $y\in B$. Consider the group which contains $x$ in $A$
(see above). By construction, any vertex from the set $B$ of the second tier
$T$ is adjacent to exactly one vertex of this group (since it has exactly one
common neighbour with each vertex from $A$ of the first tier of $T$ in the
$Levi(\pi_{n})$). Hence, $x$ and $y$ are adjacent or there is exactly one path
of length two between them.

Thus, the graph $G$ is geodetic and of diameter 2. And since it is obtained
from the Hamiltonian graph $Levi(\pi_{n})$ by replacing two consequent
vertices in an Hamiltonian cycle with a vertex adjacent to all their neighbors
and adding several edges, the graph $G$ is also Hamiltonian. ∎

###  2.4 Subclasses of Hamiltonian graphs

######  Definition 10.

A graph is called _locally connected_ if an open neighborhood111a subgraph
induced by vertices that are adjacent to a given one of any vertex of this
graph induces a connected subgraph.

######  Proposition 4.

Let $G$ be a geodetic locally connected graph. Then $G$ is a complete graph.

###### Proof.

Consider a bearing tree, fixing an arbitrary vertex as the root. According to
the lemma 4, all vertices of the first tier of this tree are divided into
several complete subgraphs. Therefore, due to local connectivity, there is
always exactly one complete subgraph in the first tier. So the whole graph $G$
is complete. ∎

######  Definition 11.

A cycle $C$ in a graph $G$ is _extendable_ if there is a cycle $C^{\prime}$ in
$G$ that contains all the vertices of C and exactly one additional vertex. A
graph $G$ is _cycle extendable_ if every non-Hamiltonian cycle in G is
extendable. If in addition every vertex of G belongs to a 3-cycle, then $G$ is
_fully cycle-extendable_.

######  Lemma 9.

Let $G$ be a geodetic fully cycle extendable graph. Then $G$ is a complete
graph.

###### Proof.

Let the graph $G$ is not complete, and in the maximal by the number of
vertices clique $K_{m}$ of the graph $G$ there are $m$ vertices. Then, since
this clique is a complete subgraph containing at least three vertices, and the
graph $G$ is cycle extendable, then there is a cycle on $m+1$ vertex
containing this clique $K_{m}$. If $v$ is a vertex from this cycle that is not
contained in $K_{m}$, then $v$ is adjacent to all vertices of $K_{m}$. Indeed,
otherwise, if the vertex $u\in K_{m}$ is not adjacent to $v$, then there would
be two different geodesics of length two between $u$ and $v$ (there are at
least two edges from $v$ to the complete graph $K_{m}$). Thus we got a
contradiction, since we got a click on $m+1$ vertices. ∎

######  Proposition 5.

Let $G$ be a geodetic cycle expandable graph. Then $G$ is a complete graph or
a tree.

###### Proof.

It follows from the proof of the Lemma 9 that if there is a triangle in a
geodetic cycle extendable graph, then the graph is complete. We show that the
graph $G$ has a triangle if it is not a tree. Consider a cycle of the smallest
length, let it be a cycle $C$ of length $k$. Then consider a cycle
$C^{\prime}$ of length $k+1$ containing all vertices of the cycle $C$. Some
edges of the cycle $C$ are edges that do not belong to the the edges of cycle
$C^{\prime}$ . Consider one of such edges, it divides the cycle $C^{\prime}$
into two smaller ones. And then either $k=3$, or the length of one of the
cycles is less than $k$, which contradicts the assumption that $C$ is the
cycle of the smallest length. ∎

###  2.5 Hereditary classes for geodetic graphs

######  Definition 12.

A class $X$ of graphs is called _hereditary_ if for each graph $G\in X$ all
induced subgraphs of $G$ also belong to $X$. In other words, $X$ is hereditary
if and only if $G\in X$ implies $G-v\in X$ for any vertex $v$ of $G$, where
$G-v$ denotes the graph obtained from $G$ by removing $v$ together with all
edges incident to it.

######  Definition 13.

Given a class of graphs $M$ (maybe infinite), we denote by $Free(M)$ the class
of graphs containing no graph from $M$ as an induced subgraph. We say that
graphs in $M$ are _forbidden induced subgraphs_ for the class $Free(M)$ and
that graphs in $Free(M)$ are _$M$ -free_.

######  Lemma 10 (Kitaev and Lozin [4]).

A class $X$ of graphs is hereditary if and only if there is a set $M$ such
that $X=Free(M)$.

######  Definition 14.

A graph $G$ is a minimal forbidden induced subgraph for a hereditary class $X$
if $G$ does not belong to $X$ but every induced subgraph of $G$ not equal to
$G$ belongs to $X$ (or alternatively, the deletion of any vertex from $G$
results in a graph that belongs to $X$).

Let us denote by $Forb(X)$ the set of all minimal forbidden induced subgraphs
for a hereditary class $X$.

######  Lemma 11 (Kitaev and Lozin [4]).

For any hereditary class $X$, we have $X=Free(Forb(X))$.

######  Definition 15.

Let $P$ be an arbitrary class of graphs (not necessarily hereditary). We
denote by $\lfloor P\rfloor$ the maximum hereditary subclass of the class $P$,
and by $\lceil P\rceil$ the minimal superclass of class $P$.

######  Lemma 12.

$\lfloor P\rfloor$ и $\lceil P\rceil$ are uniquely defined.

###### Proof.

Let $\lfloor P_{1}\rfloor$ and $\lfloor P_{2}\rfloor$ be two hereditary
subclasses of class $P$, and neither of them contains the other. Then,
considering the union of $\lfloor P_{1}\rfloor$ and $\lfloor P_{2}\rfloor$, we
obtain a subclass of the class $P$, the heredity of which obviously follows
from the fact that $\lfloor P_{1}\rfloor$ and $\lfloor P_{2}\rfloor$ are also
hereditary classes. So we achieved that one subclass contains the others.

Let $\lceil P_{1}\rceil$ and $\lceil P_{2}\rceil$ be two hereditary
superclasses of class $P$, and neither of them contains the other. Then,
considering the intersections of these classes, we get a hereditary superclass
of the class $P$. Indeed, the heredity of this superclass will follow from the
following property of hereditary classes: if $\lceil P_{1}\rceil=Free(Z_{1})$
and $\lceil P_{2}\rceil=Free(Z_{2})$, then $\lceil P_{1}\rceil\cap\lceil
P_{2}\rceil=Free(Z_{1}\cup Z_{2})$. This property has been proved in the
article [4]. ∎

Further we consider $\mathcal{G}$ – the class of geodetic graphs. We will
assume that every connected component of an induced subgraph of a graph from
the class $\lfloor\mathcal{G}\rfloor$ must be geodetic. So we may consider
only connected induced subgraphs of graphs from the class
$\lfloor\mathcal{G}\rfloor$.

We denote by $\mathcal{C}^{\prime}_{2k}$ the set of graphs obtained from a
cycle on $2k$ vertices by adding one edge dividing the cycle into two odd
cycles. The example is shown in the Figure 15.

Figure 15: The set $\mathcal{C}^{\prime}_{8}$ consists of two graphs.

######  Lemma 13.

$\lfloor\mathcal{G}\rfloor=Free(C_{2k},\mathcal{C}^{\prime}_{2k}\
|k\geq\nolinebreak 2)$.

###### Proof.

Find all subgraphs of $H$ that are not geodetic. Then the graph $H$ contains
two vertices $u$ and $v$, between which there are at least two geodesics.

$\dots$$\dots$$\dots$$\dots$$u$$v$$v_{0}$$u_{0}$ Figure 16: A forbidden
subgraph of $\lfloor\mathcal{G}\rfloor$.

Consider some two geodesics between two vertices $u$ and $v$. Let the first
time they diverge at the vertex $u_{0}$ (the first from the vertex $u$), and
the first time they converge at the vertex $v_{0}$. Then consider a cycle
whose opposite ends are $u_{0}$ and $v_{0}$. If there are some edges in this
cycle, then they are "vertical", that is, "perpendicular" to $u_{0}v_{0}$ (see
Figure 16). Indeed, considering other edges we obtain that the path
$u_{0}v_{0}$ of the cycle has not the smallest distance between the vertices.
Let at least two "vertical" edges be drawn in this cycle. Then we can select a
smaller cycle (according to Lemma 11, it is enough to consider minimal
forbidden subgraphs). Therefore, all forbidden subgraphs - even cycles and
even cycles with an edge and there are no other minimal forbidden ones.

∎

######  Theorem 5.

Let $G\in\lfloor\mathcal{G}\rfloor$. Then each block of the graph $G$ is a
complete subgraph or an odd-length cycle.

###### Proof.

Consider an arbitrary connected graph $G$ from the class
$\lfloor\mathcal{G}\rfloor$. Choose the smallest even cycle in $G$ that does
not induce a complete subgraph. It must have at least two diagonals (edges
whose ends are the vertices of the cycle that don’t belong to the edges of the
cycle), according to Lemma 13. Then we can select an even cycle with the
length less than the length of the initial cycle - either one of the diagonals
divides the cycle into two even ones, or we can select an even <<crossing>>
cycle formed by two diagonals, unless of course this is $K_{4}$ \- a complete
graph on 4 vertices, but we do not consider it from the very beginning. Then
this smaller cycle must be a complete graph. And then there is a diagonal, let
$uv$, dividing the original even cycle into two smaller even ones. But then
each of these even cycles is a complete graph. And then each vertex of the
cycle will be adjacent to both vertices $u$ and $v$, that is, we can select
cycles of length 4, the induces complete subgraphs. And then the entire
induced subgraph of this cycle is a complete graph.

This way we can choose the smallest even cycle that does not induce a complete
subgraph in each block. That is, we got that either each block is an odd
cycle, or it is a complete subgraph.

Also note that the considered above reasoning is a necessary condition.
Sufficiency can be easily checked. ∎

######  Lemma 14.

Let $K_{4}-e$ be a graph consisting of two triangles with one common side.
Then $Free(C_{4},K_{4}-e)$ is a hereditary class of graphs containing a class
geodetic graphs.

###### Proof.

Let some geodetic graph doesn’t belong to the class $Free(C_{4},K_{4}-e)$.
Then this geodetic graph must contain $C_{4}$ or $K_{4}-e$ as an induced
subgraph. ∎

######  Remark 1.

To prove that $\lceil\mathcal{G}\rceil=Free(C_{4},K_{4}-e)$ it is necessary to
show that any graph $H$, not containing $C_{4}$ or $K_{4}-e$ as an induced
subgraph, is an induced subgraph of some geodetic graph.

##  3 Antipodal graphs

######  Proposition 6.

A tree is an antipodal graph if and only if the longest path of a tree is
unique and has an odd length.

###### Proof.

Necessity. Let the tree be an antipodal graph and assume it has two longest
simple paths. Then it is clear that these paths intersect. Indeed, since if
this were not true, their lengths could have been increased. Indeed,
considering these paths and a path $l$ connecting them we can take at least
half of each of the longest path (depending on the points of intersection of
$l$ and longest paths) and the path $l$ itself, receiving a longer path.

Let, without loss of generality, the longest paths be $ab$ and $cd$. And they
intersect at the path $uv$ (see Figure 17). Then $d(a,v)\geq d(c,v)$, because
otherwise $ab$ could be chosen longer (the path $bc$). Similarly, we obtain
that $d(c,v)\geq d(a,v)$, that is, $d(a,v)=d(c,v)$, similarly we obtain the
equality $d(u,d)=d(u,b)$. Let, without loss of generality, $d(a,v)\leq
d(u,b)$, but then the vertex $a$ has at least two antipodes - $b$, $d$.

Thus, we have proved that if a tree is an antipodal graph, then it has exactly
one longest path, but then if it is unique, then it is obviously odd. Indeed,
if it were even, then there would be the middle of the given path, equidistant
from the ends of the path. Therefore, there would be some vertex even further
from the middle than the ends of the longest paths. This would mean that the
initially chosen path is not the longest.

$a$$c$$b$$d$$v$$u$ Figure 17: Two longest simple paths $ab$ and $cd$ intersect
at the path $uv$.

Sufficiency. Let the longest simple path of a tree be unique and odd (denote
this path by $P$ with endpoints $a$ and $b$). It is clear that each vertex of
a given path has exactly one antipode. Therefore, further we will consider the
other vertices. Suppose some vertex $c$ has an antipode $d$ which is neither
of the ends of $P$. Let the closest to $c$ vertex from the path $P$ be the
vertex $u$. Then $d(u,d)\geq d(u,a)$, otherwise, the path $cd$ would be
shorter than the path $ca$ as the following is true $d(c,a)=d(c,u)+d(u,a)\leq
d(c,d)\leq d(c,u)+d(u,d)$. But from the inequality $d(u,d)\geq d(u,a)$ follows
that the longest path $P$ is not unique. Also it’s obvious that there is no
vertex that can be equidistant from $a$ and $b$, since the longest path is
odd. ∎

######  Proposition 7.

It’s possible to add few vertices and edges to any graph $G$ so that it
becomes antipodal.

###### Proof.

Let the diameter of the graph $G$ be equal to $d$. Then we add a simple path
of length $2d+1$ passing through exactly one arbitrary vertex of the graph
$G$. Moreover, this vertex is one of the midpoints of this simple path. In the
Figure 18 the considered vertex is $v_{0}$. It is clear that the antipode of
any vertex of the graph $G$ is $v_{-(d+1)}$. Now consider the antipodes of
$v_{i}$. The antipode of $v_{0}$ is $v_{-(d+1)}$, since in the graph $G$ the
maximum distance to $v_{0}$ is equal to $d$. Now consider the vertex $v_{i}$,
where $i\in\mathbb{N}$. On the added path, its antipode is $v_{-(d+1)}$, which
is at a distance of $i+d+1$ from it. Moreover, any vertex of the graph $G$ is
at the distance no more than $i+d$ from $v_{i}$ (the distance to $v_{0}$, and
the maximum distance from $v_{0}$ to the vertices of the graph $G$). Thus,
$v_{i}$ has exactly one antipode for $i\geq 0$.

$...$$v_{0}$$v_{-1}$$v_{-(d+1)}$$...$$v_{1}$$v_{d}$$...$ Figure 18: Converting
an arbitrary graph to an antipodal graph.

The case $v_{-i}$ is checked analogously to the case $v_{i}$, where $i$ is
positive. ∎

Let $\mathcal{A}$ be the class of antipodal graphs. We will assume that every
connected component of an induced subgraph of a graph from the class
$\lfloor\mathcal{A}\rfloor$ is antipodal. So, we may consider only connected
induced subgraphs of graphs from the class $\lfloor\mathcal{A}\rfloor$.

######  Theorem 6.

Subclass $\lfloor\mathcal{A}\rfloor=\\{P_{1},P_{2}\\}$, where $P_{1},P_{2}$
are paths on one and two vertices, respectively. The superclass
$\lceil\mathcal{A}\rceil$ contains all connected graphs.

###### Proof.

Let us prove that no graph $G\in\lfloor\mathcal{A}\rfloor$ contains a
triangle. Suppose the opposite, then we choose this triangle as the induced
subgraph of the graph $G$, by definition it must be antipodal, but each vertex
has 2 antipodes.

Besides, graph $G\in\lfloor\mathcal{A}\rfloor$ does not contain a simple path
of length two as an induced subgraph. Assuming the opposite, consider this
path as an induced subgraph, it must be an antipodal graph by the definition,
but the central vertex of the path has two antipodes.

Now suppose that some connected subgraph doesn’t belong to
$\lceil\mathcal{A}\rceil$. Then, according to Lemma 10, there must exist some
nonempty forbidden induced subgraph, let it be a graph $H$ that is not
contained in any graph $G\in\lceil\mathcal{A}\rceil$. However, from the proof
of Proposition 7, there is an antipodal graph containing $H$ as an induced
subgraph. ∎

######  Proposition 8.

Let $G$ be a geodetic graph and the degree of each vertex is at least two.
Then any of its vertices of the graph $G$ has at least two antipodes.

###### Proof.

Let’s prove the statement assuming the opposite. Let some vertex $a$ has
exactly one antipode $b$. Then let’s build a bearing tree with the root vertex
$a$. Then in the last, let’s say the $k$th tier (Figure 19), there is exactly
one vertex, since vertex $a$ has exactly one antipode. Let’s add edges that
are not in the bearing tree, but are in the graph $G$. Then consider vertex
$b$ and the edges coming out of it. Edges cannot go to the tier with the
number $k+1$, since $b$ is the antipode of the vertex $a$, also only one edge
can go to the $k-1$-th tier, according to the Lemma 2. Thus, there is at least
one more vertex in the $k$-th tier, connected with vertex $b$.

$\dots$$\dots$$a$$b$$k-1$$k$$k-2$$0$$1$ Figure 19: A bearing tree with the
root $a$ and exactly one antipode.

∎

######  Corollary 2.

Any vertex of a geodetic Hamiltonian graph has at least two antipodes.

##  4 Weighted graphs

######  Definition 16.

The _length_ of a path in a weighted graph is the sum of the weights of its
edges. A _geodesic_ between two vertices of a weighted graph is the path
between the given vertices with the smallest length. A weighted graph is
called _geodetic_ if there is exactly one geodesic between any two of its
vertices.

######  Theorem 7.

It’s possible to assign weights to edges of any connected graph $G$ so that it
becomes geodetic and antipodal simultaneously.

###### Proof.

  1. (a)

Let us prove that we can assign weights so that the graph becomes geodetic. We
do this using mathematical induction on $n$, the number of vertices in the
graph. The assertion of the induction coincides with the assertion of the
theorem.

Base: $n=2$, two vertices connected by one edge, obviously, assigning the
weight 1, the graph will be geodetic.

Induction step: assume the statement is proved for $n$ vertices, we will prove
it for $n+1$. We remove some vertex $v$ and edges outgoing from it so that the
graph remains connected (for instance, fix a spanning tree of the graph and
remove one of its leafs), obtaining a subgraph $H$ of the graph $G$. In the
graph $H$ there are $n$ vertices, we assign weights to its edges so that it
becomes geodetic (we can do this according to the induction hypothesis). Let
the sum of the weights of the edges at this moment be equal to $S$.

Now we assign weights to the edges outgoing from $v$. Let one of the edges
$uv$ have weight $S+1$, and all the others going out from $v$ have weight
$2S+2$. Then the graph will be geodetic.

Indeed, if we select the given weights, then between any two vertices other
than $v$ the geodesic will not change after adding the vertex $v$ and the
edges going out from it. And also geodesics going out from $v$ will always
pass through exactly one edge $uv$ with weight $S+1$, and then the geodesic
will be the only one since it is a geodesic in the graph $H$ with added edge
$uv$. See the example in the Figure 20.

$The\ initial\ graph$$v$$u$

$1$$2$$4$$8$$16$$32$$64$$128$$128$$v$$u$$The\ obtained\ graph$

Figure 20: Constructing weighted geodetic antipodal graphs.

  2. (b)

Let us prove that the same assignments of weights to the edges from the part
$(a)$ also guarantees us that the achieved graph is antipodal. We use the same
induction hypothesis, but for the antipodes. We check that the same base for
two vertices is also true for antipodal graphs. Then for the induction step we
use the same notations as previously in the part $(a)$. Then the antipode of
vertices different from $v$ is obviously the vertex $v$, and the antipode of
the vertex $v$ is the antipode of the vertex $u$ in the subgraph $H$.

∎

######  Theorem 8.

Let $G$ be a connected weighted graph on $n$ vertices. Then it is possible to
check whether the graph $G$ is geodetic/antipodal or not for $O(n^{3})$.

###### Proof.

The main idea is Dijkstra’s algorithm (similar to building a spanning tree
using Breadth First Search).

We will check the graph is geodetic or not at the stages of constructing the
spanning tree $T$ of the graph $G$. Let us take as the root of the tree an
arbitrary vertex of the graph $G$ vertex $v_{1}$ – it constitutes the zero
tier. Further, add to $T$ all vertices adjacent to $v_{1}$ (together with
edges from $v_{1}$) – let, without loss of generality, these are
$v_{2},v_{3},...v_{k}$. Let the weight of the edge from $v_{1}$ to $v_{i}$ be
equal to $k_{i}$, then we add the vertex $v_{i}$ to the $k_{i}$-th tier.

Further, consider the vertex of the topmost tier from $T$, other than $v_{1}$.
Let, without loss of generality, this is the vertex $v_{2}$. Now we consider
the neighbors of the vertex $v_{2}$ in the graph $G$. Two options are
possible:

  1. 1)

If some of the neighbors $v_{2}$ was not added earlier, then add it to the
tree $T$ in a tier different from the tier $v_{2}$ by the number corresponding
to the edge between $v_{2}$ and this vertex.

  2. 2)

If some of the neighbors of $v_{2}$, let $v_{k}$, have already been added to
the tree $T$, then we look at the weight of the edge $v_{2}v_{k}$ and the
difference between the tiers $v_{2}$ and $v_{k}$. If the weight of the edge is
less, then we transfer the vertex to a tier different from the tier $v_{2}$ by
the weight of the edge and remove another edge from $v_{k}$ so that there are
no cycles in $T$. If the weight of the edge is greater, then we do nothing. If
the weights of the edges are equal, then we draw this edge (we will have a
cycle, if after repeating this operation the cycle remains, then the graph is
not geodetic)

After that, the vertices $v_{1},v_{2}$ are already fixed in their tiers.

Next, we do the same with the rest of the vertices. We consider a vertex of
the uppermost tier from $T$ that differs from the vertices already considered
and fixed in their tiers. Let, without loss of generality, this is the vertex
$v$. If two edges go to this vertex $v$ from the upper tiers, then the graph
is not geodetic, otherwise we consider the neighbors of the vertex. Two
options are possible:

  1. 1)

If some of the neighbors $v$ was not added earlier, then add it to the tree
$T$ in a tier different from the tier $v$ by the number corresponding to the
edge between $v$ and the given vertex.

  2. 2)

If some of the neighbors of $v$, let $u$, have already been added to the tree
$T$, then look at the weight of the edge $vu$ and the difference between the
tiers $v$ and $u$. If the weight of the edge is less, then we transfer the
vertex $u$ to a tier that differs from the tier of $v$ by the weight of the
edge and remove other edges coming from $u$. If the weight of the edge is
greater, we do nothing. If the weight of the edge is equal to the difference
in tiers of $u$ and $v$, then we draw this edge (we will have a cycle).

After that, the vertex $v$ is fixed in its tier.

At the end of the algorithm, we will find out whether there is exactly one
geodesic from the root to other vertices (if there are no cycles in the tree
$T$, each geodesic is unique), and also by the number of vertices in the last
tier, we will understand whether the graph is antipodal or not. To construct
such an algorithm, we need $O(n^{2}+m)$, where $m$ is the number of edges in
the graph. Repeating this algorithm, choosing other vertices as the root of
the tree, we need $O(n^{3})$. ∎

######  Theorem 9.

Let $H$ be an arbitrary weighted graph with integer weights of edges that does
not contain vertices between which there are several geodesics of length two.
Then there is a weighted geodetic graph $G$ which contains $H$ as an induced
subgraph, and the weights of the added edges are equal to one or two.

###### Proof.

Let us describe the algorithm for constructing the graph $G$.

  1. 1)

Take the graph $G$ isomorphic to $H$.

  2. 2)

Let us fix an arbitrary vertex $v$ from $V(H)$ and construct a bearing tree,
described in Theorem 8, of the graph $G$ with the root $v$. If in some tier
below the second there is a vertex $u\in V(H)$, then we add a vertex $t$ to
the graph $G$ and draw edges $vt$ and $ut$ with weights equal to one. It is
easy to see that in this case there will be no vertices with two geodesics of
length two between them. Fixing all vertices of $V(H)$ as the root of the
bearing tree one by one, we obtain a graph in which there is exactly one
geodesic of length one or two between any two vertices from $V(H)$.

  3. 3)

Let us fix an arbitrary vertex $v$ from $V(G)\setminus V(H)$ as the root of
the bearing tree of the graph $G$. Let there be some vertex $u$ in the tier
below the third. Then add an edge $uv$ of length one to the graph $G$. It is
easy to see that in this case there will be no vertices with two geodesics of
length two between any two vertices of $G$, since if the added edge of length
one is contained in some such geodesic, then it would mean that the vertex $u$
is in one of the first three tiers. And also multiple edges will not appear,
since only edges with weight one emerge from the considered vertex. Further,
we consider a bearing tree with the root $v$ of the achieved graph $G$ until
all the vertices are in the first three tiers. Then, we will fix all the
vertices from $V(G)\setminus V(H)$ as the root of the bearing tree.

  4. 4)

Suppose the obtained graph is not geodetic. Then note that if there are
several geodesics between some vertices, then these geodesics are necessarily
of length three. Then if there are several geodesics between some two
vertices, draw an edge of length two between them. Note that multiple edges
cannot appear, since both vertices between which we draw an edge cannot belong
to $V(H)$, and edges with weights two and one emerge from the vertices
$V(G)\setminus V(H)$ and there are no other edges. After this operation of
adding new edge, no pairs of vertices with multiple geodesics of length two
between them will appear.

  5. 5)

Repeat step four as long as possible.

The algorithm will stop, since we do not add vertices after step one, so there
are finitely many of them. This means that number of pairs of vertices between
which there can be a geodesic of length three is also finite. ∎

##  5 Problems

###  5.1 Isomorphic graphs

######  Lemma 15 (Rasin [10]).

Any two cacti can be checked for isomorphism in polynomial time.

######  Open problem 1.

Let two geodetic graphs $G$ and $G^{\prime}$ be given. Is it possible to check
whether these graphs are isomorphic or not in polynomial time?

######  Conjecture 1.

An invariant for isomorphic geodetic graphs is a bijection from the bearing
trees of the graph $G$ to the bearing trees of the graph $G^{\prime}$ such
that the trees corresponding to each other are isomorphic.

Note that if the geodetic graphs $G$ and $G^{\prime}$ are isomorphic, then
their bearing trees will also be isomorphic, which follows from the Corollary
3 below. Generally speaking, this is not true for arbitrary non-geodetic
graphs, since the bearing tree can be defined non-uniquely, for example, see
Figure 21:

Initial graph

Bearing tree 1

Bearing tree 2

Figure 21: Non-unique bearing trees.

######  Corollary 3.

The bearing tree of a geodetic graph with a fixed root is uniquely defined,
which follows from the Lemma 1.

###  5.2 Open problems

We conclude with two open problems:

  * •

Is it true that for any graph $H$ not containing $C_{4}$ and $K_{4}-e$ as an
induced subgraph there exists a geodetic graph $G$ such that $H$ is an induced
subgraph of the graph $G$?

The following problem appears in [11] that was rephrased in terms of graph
theory in [6]: Is every finite bipartite $C_{4}$-free graph a subgraph of the
Levi graph of a finite projective plane?

So, in particular, it’s curious to find out whether there exists a geodetic
graph that contains $Levi(\pi_{r})$ as an induced subgraph or not.

  * •

Let two geodetic graphs $G$ and $G^{\prime}$ are given. Is it possible to
check whether these graphs are isomorphic or not in polynomial time?

## References

  * [1] Oystein Ore, _Theory of Graphs_ , American Mathematical Society, Providence, R. I., 1962.
  * [2] Joel G. Stemple and Mark E. Watkins, _On Planar Geodetic Graphs_ , Journal of Combinatorial Theory 4, 1968, no. 2, pp. 101-117.
  * [3] C. E. Frasser, _k-Geodetic graphs and their application to the topological design of computer networks_ , Proc. Argentinian Workshop on Theoretical Computer Science, 28 JAIIO-WAIT’99 (1999), pp. 187–203.
  * [4] S. Kitaev, V. Lozin, _Words and Graphs, Monographs in Theoretical Computer Science_ , Springer International Publishing Switzerland 2015, pp. 7-30.
  * [5] James Singer, _A Theorem in finite projective geometry and some applications to number theory_ Trans. Amer. Math. Soc. 43 (1938), 377-385.
  * [6] Felix Lazebnik, Keith E. Mellinger, Oscar Vega, _Embedding cycles in finite planes_ , the Electronic Journal of Combinatorics 20(3) (2013)
  * [7] Srinivasan, N., Opatrny, J., Alagar, V.S.: _Construction of Geodetic and Bigeodetic Blocks of Connectivity k $\geq$ 3 and their Relation to Block Designs_. Ars Combinatoria 24 (1987) 101-114
  * [8] Pavol Híc, _A construction of geodetic blocks_ , Mathematica Slovaca, Vol. 35 (1985), No. 3, 251–261
  * [9] Stemple, Joel G. , _Geodetic graphs homeomorphic to a complete graph_ , Second International Conference on Combinatorial Mathematics (New York, 1978), Annals of the New York Academy of Sciences, 319, 1979, pp. 512–517.
  * [10] Rasin. O. V., _Algorithm for checking the isomorphism of Husimi trees_ , Proceedings of the Ural State University. - 2004. - No. 30. - pp. 126-136, in Russian.
  * [11] P. Erdos, _Some old and new problems in various branches of combinatorics_ , Proceedings of the Tenth Southeastern Conference in Combinatorics, Graph Theory, and Computing, Florida Atlantic Univ., Boca Raton, Fla. (1979) 19–37.

_E-mail address:_<EMAIL_ADDRESS>
_E-mail address:_<EMAIL_ADDRESS>