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 will be implemented in a future version of the Wolfram Language as GraphData[
"DorogovtsevGoltsevMendes",
n
] for small 
.
