TOPICS
Search

Dorogovtsev-Goltsev-Mendes Graph


DorogovtsevGoltsevMendesGraphs

The Dorogovtsev-Goltsev-Mendes graph are a family of planar graphs introduced by Dorogovtsev et al. (2011) and defined as follows. Define DGM(0) as the path graph P_2 (whose index is taken as n=0 instead of -1 as in Dorogovtsev et al. 2011). To obtain DGM(1), add a new vertex associated with each edge and connect it to the edge's endpoints. Perform this procedure a total of n times to obtain DGM(n). The order-n graph so obtained therefore has vertex count and edge count

|V|=3/2(3^n+1)
(1)
|E|=3^n.
(2)

The nth Dorogovtsev-Goltsev-Mendes graph can be made by connecting three (n-1)-graphs (Dorogovtsev et al. 2011).

By construction, the Dorogovtsev-Goltsev-Mendes graphs are 2-trees.

The n-Dorogovtsev-Goltsev-Mendes graphs are untraceable (and nonhamiltonian) for n>2.

Special cases are summarized in the table below,

These graphs are implemented in the Wolfram Language as GraphData[{"DorogovtsevGoltsevMendes", n}] for small n.


See also

Small World Network

Explore with Wolfram|Alpha

References

Dorogovtsev, S. N.; Goltsev, A. V.; and Mendes, J. F. F. "Pseudofractal Scale-Free Web." 8 Dec 2011. https://arxiv.org/abs/cond-mat/0112143.

Cite this as:

Weisstein, Eric W. "Dorogovtsev-Goltsev-Mendes Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Dorogovtsev-Goltsev-MendesGraph.html

Subject classifications