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 .