I have two questions, both inspired by this thread, where it is asked what the maximum diameter a graph on $2023$ vertices and minimum degree 42 is. The answer is 140, which is approximately $\frac{3n}{\delta+1}$ where $n$ is the number of vertices and $\delta$ is the minimum degree, and it is achieved by a sequence of small and big cliques put on a path. I believe the same construction works for general $n$ and $\delta$, if we require all vertices to have degree at least $\delta$.
My questions are:
- Given a sequence of integers $A = a_1, \dots, a_n$, $a_i\geq a_{i+1}$, what can be said of the maximum diameter of a graph with degree sequence $D=d_1, \dots, d_n$, $d_i\geq d_{i+1}$, which dominates $A$, meaning $d_i\geq a_i$ for all $i$?
- Are extremal graphs for the above question always of the form of a bunch of cliques glued on a path (as in the motivating post)?
Let $v$ represent an endpoint of the longest path within the graph. Denote $S_i$ as the set of vertices situated at a distance $i$ from $v$. If there's a pair of vertices in $S_i$ not connected by an edge, adding this edge preserves the graph's adherence to the degree condition without altering any $S_i$. The same goes for adding edge between $S_i$ and $S_{i+1}$. These adjustments demonstrate that the maximum diameter can be achieved at a form of "a bunch of cliques glued on a path".