The Dorogovtsev-Goltsev-Mendes graph are a family of planar graphs introduced by Dorogovtsev et al. (2011) and defined as follows.
Define
as the path graph
(whose index is taken as
instead of
as in Dorogovtsev et al. 2011). To obtain
, add a new vertex associated with each edge and connect
it to the edge's endpoints. Perform this procedure a total of
times to obtain
. The order-
graph so obtained therefore has vertex
count and edge count
(1)
| |||
(2)
|
The th
Dorogovtsev-Goltsev-Mendes graph can be made by connecting three
-graphs (Dorogovtsev et al. 2011).
By construction, the Dorogovtsev-Goltsev-Mendes graphs are 2-trees.
The -Dorogovtsev-Goltsev-Mendes
graphs are untraceable (and nonhamiltonian)
for
.
Special cases are summarized in the table below,
graph | |
0 | path graph |
1 | triangle graph |
2 | 2-triangular grid graph |
These graphs are implemented in the Wolfram Language as GraphData["DorogovtsevGoltsevMendes",
n
] for small
.