Abstract
A graph is considered diameter-two edge-critical if its diameter is exactly two, but the removal of any edge increases that diameter. The Murty-Simon Conjecture posits that the maximum number of edges in such a graph on $n$ vertices is $\lfloor n^{2}/4 \rfloor$, with the extremal case being the complete bipartite graph $K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$. This paper provides a significant advancement by proving the conjecture for graphs whose complements exhibit specific structural properties, namely vertex connectivity $\ell \in \{1, 2, 3\}$ or the presence of an independent vertex cut of cardinality at least three.
Introduction
In the study of network topology and graph efficiency, the diameter of a graph—the longest shortest path between any two nodes—is a critical metric. A graph with diameter two is highly efficient, as every node can reach any other node in at most two steps. A specific class of these graphs, known as diameter-two edge-critical, represents a state of minimal redundancy: they maintain a diameter of two, but the loss of even a single edge disrupts this property.
The Murty-Simon Conjecture, originating in the early 1970s, remains one of the most persistent problems in extremal graph theory. It suggests a strict upper bound on the density of these graphs. While the conjecture has been explored for decades, many previous attempts at a universal proof contained subtle gaps, such as only addressing graphs with an even number of vertices. This research addresses these gaps by focusing on the structural properties of the graph's complement.
Methodology: The Complementary Approach
To tackle the complexity of diameter-two edge-critical graphs, the authors utilize a classic mathematical strategy: analyzing the complement graph ($G^c$). In a complement graph, an edge exists between two vertices if and only if it does not exist in the original graph $G$.
The methodological bridge used here is the established relationship between diameter-two edge-criticality and total domination. A total dominating set is a subset of vertices where every vertex in the graph is adjacent to at least one member of that subset. The authors translate the problem of maximizing edges in $G$ into a problem of minimizing edges in $G^c$ under specific domination constraints.
By categorizing graphs based on the vertex connectivity ($\ell$) of their complements—the minimum number of nodes that must be removed to disconnect the graph—the authors apply structural induction and case-by-case analysis. This paper specifically investigates cases where $\ell = 1, 2,$ and $3$.
Key Insights and Structural Leverage
Several key insights drive the proof forward:
- Translation to Domination: The proof demonstrates that showing $|E(G)| \le \lfloor n^2/4 \rfloor$ is mathematically equivalent to proving that the complement graph $G^c$ contains at least a specific minimum number of edges.
- Independent Vertex Cuts: The authors identify that if the complement graph possesses an "independent vertex cut" (a set of non-adjacent nodes whose removal disconnects the graph) of size three or greater, the conjecture holds. This provides a powerful lever for handling complex graph structures.
- Addressing Parity Gaps: Unlike previous "series papers" in the field that often restricted their scope to even-order graphs, this work provides a robust framework that holds regardless of whether the number of vertices $n$ is even or odd.
- 4-Supercritical Link: The research utilizes the characterization of "4-supercritical" graphs—where the addition of any edge reduces the total domination number by exactly two—to resolve specific edge cases within the proof.
Results
The paper successfully confirms the Murty-Simon Conjecture for several major classes of graphs. Specifically, the conjecture is proven true for:
- Graphs where the complement has vertex connectivity 1, 2, or 3.
- Graphs where the complement has an independent vertex cut of size $\ge 3$.
In each of these cases, the research confirms that the maximum edge count is indeed $\lfloor n^2/4 \rfloor$. Furthermore, it verifies that the only graph reaching this maximum is the complete bipartite graph $K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$, reinforcing the original intuition of Murty and Simon.
Conclusion and Future Work
While this paper represents a major step toward a universal proof, the Murty-Simon Conjecture remains open for graphs with higher connectivity in their complements. The current proof techniques are optimized for $\ell \le 3$. Future research may explore whether these combinatorial tools can be generalized for $\ell \ge 4$ or if more complex, highly-interconnected complement structures will require entirely new theoretical approaches. Ultimately, this work provides a rigorous foundation for using domination theory to solve long-standing problems in extremal graph theory.
Summary updated