The Dorogovtsev-Goltsev-Mendes graphs are a family of planar graphs introduced by Dorogovtsev et al. (2002) and defined as follows.
Define 
as the path graph 
(whose index is taken as 
instead of 
as in Dorogovtsev et al. 2002). 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 
th 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. 2002).
By construction, the Dorogovtsev-Goltsev-Mendes graphs are k-trees with 
.
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 
.
