Repository: networkx/networkx

Issue:
Parameter off by one in dorogovtsev_goltsev_mendes_graph
<!-- If you have a general question about NetworkX, please use the discussions tab to create a new discussion -->

<!--- Provide a general summary of the issue in the Title above -->

### Current Behavior

The parameter `n` of `dorogovtsev_goltsev_mendes_graph` is off by one.
According to the docs and the [original paper](https://arxiv.org/pdf/cond-mat/0112143), 

> for a given n: - Total number of nodes = 3 * (3**n + 1) / 2 - Total number of edges = 3 ** (n + 1)

However that's not the case, e.g.
 ```python
[len(nx.dorogovtsev_goltsev_mendes_graph(i).nodes) for i in range(4)]
# Output: [2, 3, 6, 15]

[len(nx.dorogovtsev_goltsev_mendes_graph(i).edges) for i in range(4)]
# Output: [1, 3, 9, 27]
```
instead of [3, 6, 15, 42] and [3, 9, 27, 81] respectively.

### Expected Behavior

`dorogovtsev_goltsev_mendes_graph(n)` should return what is currently returned by `dorogovtsev_goltsev_mendes_graph(n+1)`, as claimed in the docs. `n=-1` should be a valid value (as in the paper).

 ```python
[len(nx.dorogovtsev_goltsev_mendes_graph(i).nodes) for i in range(4)]
# Output: [3, 6, 15, 42]


### Environment

<!--- Please provide details about your local environment -->

Python version: 3.12
NetworkX version: 3.3

Discussion:
Peiffap: The documentation for DGM graphs still looks like it could use a revamp. Let me know if this is something we want to add to this PR.
Peiffap: @dschult @rossbar As discussed in #7472, I've updated the PR. Let me know if this looks good to you.
Peiffap: As a side note, is it supposed to be quite messy to get documentation built locally, or to run doctests? I find myself having to manually purge several files every time I run `pytest --doctest-modules networkx` or `make html` (even after using `make clean` for the latter).
Peiffap: I merged with the latest commits on main to get rid of the test failures.

@dschult @rossbar, could I kindly request you take a quick look at this and let me know whether there are any additional changes to be made?

Patch:
diff --git a/networkx/algorithms/dominance.py b/networkx/algorithms/dominance.py
index ab841fe21..30cb8115c 100644
--- a/networkx/algorithms/dominance.py
+++ b/networkx/algorithms/dominance.py
@@ -50,9 +50,9 @@ def immediate_dominators(G, start):
 
     References
     ----------
-    .. [1] K. D. Cooper, T. J. Harvey, and K. Kennedy.
-           A simple, fast dominance algorithm.
-           Software Practice & Experience, 4:110, 2001.
+    .. [1] Cooper, Keith D., Harvey, Timothy J. and Kennedy, Ken.
+           "A simple, fast dominance algorithm." (2006).
+           https://hdl.handle.net/1911/96345
     """
     if start not in G:
         raise nx.NetworkXError("start is not in G")
@@ -118,9 +118,9 @@ def dominance_frontiers(G, start):
 
     References
     ----------
-    .. [1] K. D. Cooper, T. J. Harvey, and K. Kennedy.
-           A simple, fast dominance algorithm.
-           Software Practice & Experience, 4:110, 2001.
+    .. [1] Cooper, Keith D., Harvey, Timothy J. and Kennedy, Ken.
+           "A simple, fast dominance algorithm." (2006).
+           https://hdl.handle.net/1911/96345
     """
     idom = nx.immediate_dominators(G, start)
 
diff --git a/networkx/generators/classic.py b/networkx/generators/classic.py
index 4278a338d..156e3045c 100644
--- a/networkx/generators/classic.py
+++ b/networkx/generators/classic.py
@@ -489,12 +489,15 @@ def cycle_graph(n, create_using=None):
 
 @nx._dispatchable(graphs=None, returns_graph=True)
 def dorogovtsev_goltsev_mendes_graph(n, create_using=None):
-    """Returns the hierarchically constructed Dorogovtsev-Goltsev-Mendes graph.
+    """Returns the hierarchically constructed Dorogovtsev--Goltsev--Mendes graph.
 
-    The Dorogovtsev-Goltsev-Mendes [1]_ procedure produces a scale-free graph
-    deterministically with the following properties for a given `n`:
-    - Total number of nodes = ``3 * (3**n + 1) / 2``
-    - Total number of edges = ``3 ** (n + 1)``
+    The Dorogovtsev--Goltsev--Mendes [1]_ procedure deterministically produces a
+    scale-free graph with ``3/2 * (3**(n-1) + 1)`` nodes
+    and ``3**n`` edges for a given `n`.
+
+    Note that `n` denotes the number of times the state transition is applied,
+    starting from the base graph with ``n = 0`` (no transitions), as in [2]_.
+    This is different from the parameter ``t = n - 1`` in [1]_.
 
     .. plot::
 
@@ -503,15 +506,21 @@ def dorogovtsev_goltsev_mendes_graph(n, create_using=None):
     Parameters
     ----------
     n : integer
-       The generation number.
+        The generation number.
 
-    create_using : NetworkX Graph, optional
-       Graph type to be returned. Directed graphs and multi graphs are not
-       supported.
+    create_using : NetworkX graph constructor, optional (default=nx.Graph)
+        Graph type to create. If graph instance, then cleared before populated.
 
     Returns
     -------
-    G : NetworkX Graph
+    G : NetworkX `Graph`
+
+    Raises
+    ------
+    NetworkXError
+        If `n` is less than zero.
+
+        If `create_using` is a directed graph or multigraph.
 
     Examples
     --------
@@ -528,24 +537,29 @@ def dorogovtsev_goltsev_mendes_graph(n, create_using=None):
     .. [1] S. N. Dorogovtsev, A. V. Goltsev and J. F. F. Mendes,
         "Pseudofractal scale-free web", Physical Review E 65, 066122, 2002.
         https://arxiv.org/pdf/cond-mat/0112143.pdf
+    .. [2] Weisstein, Eric W. "Dorogovtsev--Goltsev--Mendes Graph".
+        From MathWorld--A Wolfram Web Resource.
+        https://mathworld.wolfram.com/Dorogovtsev-Goltsev-MendesGraph.html
     """
+    if n < 0:
+        raise NetworkXError("n must be greater than or equal to 0")
+
     G = empty_graph(0, create_using)
     if G.is_directed():
-        raise NetworkXError("Directed Graph not supported")
+        raise NetworkXError("directed graph not supported")
     if G.is_multigraph():
-        raise NetworkXError("Multigraph not supported")
+        raise NetworkXError("multigraph not supported")
 
     G.add_edge(0, 1)
-    if n == 0:
-        return G
     new_node = 2  # next node to be added
-    for i in range(1, n + 1):  # iterate over number of generations.
-        last_generation_edges = list(G.edges())
-        number_of_edges_in_last_generation = len(last_generation_edges)
-        for j in range(number_of_edges_in_last_generation):
-            G.add_edge(new_node, last_generation_edges[j][0])
-            G.add_edge(new_node, last_generation_edges[j][1])
+    for _ in range(n):  # iterate over number of generations.
+        new_edges = []
+        for u, v in G.edges():
+            new_edges.append((u, new_node))
+            new_edges.append((v, new_node))
             new_node += 1
+
+        G.add_edges_from(new_edges)
     return G
 
 


Test patch:
diff --git a/networkx/algorithms/tests/test_dominance.py b/networkx/algorithms/tests/test_dominance.py
index f026e4b0a..9b804c2f6 100644
--- a/networkx/algorithms/tests/test_dominance.py
+++ b/networkx/algorithms/tests/test_dominance.py
@@ -39,19 +39,20 @@ class TestImmediateDominators:
         }
 
     def test_irreducible1(self):
-        # Graph taken from Figure 2 of
-        # K. D. Cooper, T. J. Harvey, and K. Kennedy.
-        # A simple, fast dominance algorithm.
-        # Software Practice & Experience, 4:110, 2001.
+        """
+        Graph taken from figure 2 of "A simple, fast dominance algorithm." (2006).
+        https://hdl.handle.net/1911/96345
+        """
         edges = [(1, 2), (2, 1), (3, 2), (4, 1), (5, 3), (5, 4)]
         G = nx.DiGraph(edges)
         assert nx.immediate_dominators(G, 5) == {i: 5 for i in range(1, 6)}
 
     def test_irreducible2(self):
-        # Graph taken from Figure 4 of
-        # K. D. Cooper, T. J. Harvey, and K. Kennedy.
-        # A simple, fast dominance algorithm.
-        # Software Practice & Experience, 4:110, 2001.
+        """
+        Graph taken from figure 4 of "A simple, fast dominance algorithm." (2006).
+        https://hdl.handle.net/1911/96345
+        """
+
         edges = [(1, 2), (2, 1), (2, 3), (3, 2), (4, 2), (4, 3), (5, 1), (6, 4), (6, 5)]
         G = nx.DiGraph(edges)
         result = nx.immediate_dominators(G, 6)
@@ -113,10 +114,10 @@ class TestDominanceFrontiers:
         assert nx.dominance_frontiers(G, n // 2) == {i: set() for i in range(n // 2, n)}
 
     def test_irreducible1(self):
-        # Graph taken from Figure 2 of
-        # K. D. Cooper, T. J. Harvey, and K. Kennedy.
-        # A simple, fast dominance algorithm.
-        # Software Practice & Experience, 4:110, 2001.
+        """
+        Graph taken from figure 2 of "A simple, fast dominance algorithm." (2006).
+        https://hdl.handle.net/1911/96345
+        """
         edges = [(1, 2), (2, 1), (3, 2), (4, 1), (5, 3), (5, 4)]
         G = nx.DiGraph(edges)
         assert dict(nx.dominance_frontiers(G, 5).items()) == {
@@ -128,10 +129,10 @@ class TestDominanceFrontiers:
         }
 
     def test_irreducible2(self):
-        # Graph taken from Figure 4 of
-        # K. D. Cooper, T. J. Harvey, and K. Kennedy.
-        # A simple, fast dominance algorithm.
-        # Software Practice & Experience, 4:110, 2001.
+        """
+        Graph taken from figure 4 of "A simple, fast dominance algorithm." (2006).
+        https://hdl.handle.net/1911/96345
+        """
         edges = [(1, 2), (2, 1), (2, 3), (3, 2), (4, 2), (4, 3), (5, 1), (6, 4), (6, 5)]
         G = nx.DiGraph(edges)
         assert nx.dominance_frontiers(G, 6) == {
diff --git a/networkx/generators/tests/test_classic.py b/networkx/generators/tests/test_classic.py
index cf03d3ea7..70cbd9043 100644
--- a/networkx/generators/tests/test_classic.py
+++ b/networkx/generators/tests/test_classic.py
@@ -238,7 +238,15 @@ class TestGeneratorClassic:
         G = nx.dorogovtsev_goltsev_mendes_graph(1)
         assert edges_equal(G.edges(), [(0, 1), (0, 2), (1, 2)])
         assert nx.average_clustering(G) == 1.0
+        assert nx.average_shortest_path_length(G) == 1.0
         assert sorted(nx.triangles(G).values()) == [1, 1, 1]
+        assert nx.is_planar(G)
+        G = nx.dorogovtsev_goltsev_mendes_graph(2)
+        assert nx.number_of_nodes(G) == 6
+        assert nx.number_of_edges(G) == 9
+        assert nx.average_clustering(G) == 0.75
+        assert nx.average_shortest_path_length(G) == 1.4
+        assert nx.is_planar(G)
         G = nx.dorogovtsev_goltsev_mendes_graph(10)
         assert nx.number_of_nodes(G) == 29526
         assert nx.number_of_edges(G) == 59049
@@ -246,18 +254,14 @@ class TestGeneratorClassic:
         assert G.degree(1) == 1024
         assert G.degree(2) == 1024
 
-        pytest.raises(
-            nx.NetworkXError,
-            nx.dorogovtsev_goltsev_mendes_graph,
-            7,
-            create_using=nx.DiGraph,
-        )
-        pytest.raises(
-            nx.NetworkXError,
-            nx.dorogovtsev_goltsev_mendes_graph,
-            7,
-            create_using=nx.MultiGraph,
-        )
+        with pytest.raises(nx.NetworkXError):
+            nx.dorogovtsev_goltsev_mendes_graph(-1)
+        with pytest.raises(nx.NetworkXError):
+            nx.dorogovtsev_goltsev_mendes_graph(7, create_using=nx.DiGraph)
+        with pytest.raises(nx.NetworkXError):
+            nx.dorogovtsev_goltsev_mendes_graph(7, create_using=nx.MultiGraph)
+        with pytest.raises(nx.NetworkXError):
+            nx.dorogovtsev_goltsev_mendes_graph(7, create_using=nx.MultiDiGraph)
 
     def test_create_using(self):
         G = nx.empty_graph()