Given a degree sequence $\mathbf{d} = (d_1, d_2, \ldots, d_n)$ with each $d_i \in \mathbb{N}$, how dissimilar can two graphs with the same degrees $\mathbf{d}$ be? Specifically, if we use the graph edit distance (GED) as the metric, what is the maximum GED we can have?
Definition: The graph edit distance between two graphs $G_1$ and $G_2$ is defined as the minimum total number of operations of node insertions/deletions and edge insertions/deletions that can modify $G_1$ into a graph isomorphism of $G_2$
- Note: Since in the question we fix a degree sequence and thus the number of nodes, we can only consider edge insertions and deletions.
Initial feeling: The maximum value definitely depends on $\mathbf{d}$.
- The extremes cases such as empty graphs ($d_i \equiv 0$) and cliques ($d_i \equiv n - 1$) imply that the GED must be $0$.
- Intuitively, when each $d_i$ is far from $0$ and $n - 1$, we have more possibilities and we may expect higher maximum GED
- The set of graphs with a given $\mathbf{d}$ can be represented as a Markov Chain with "edge rewiring" operations
Question: Can we obtain closed-form formulae for the maximum GED, or at least bounds?