A strengthening of the Murty-Simon Conjecture for diameter 2 critical graphs

A diameter 2 edge-critical graph, noted D2C graph, is a graph of diameter 2 and such that the deletion of any edge increases the diameter.

The Murty-Simon Conjecture states that all D2C graphs of order n have at most n²/4 edges and that this bound is only reached by the balanced complete bipartite graph. The conjecture has been proved for several families (triangle-free, high maximum degree...) and when the order is either small or large.

In 2015, a smaller bound of (n-1)²/4+1 was proved for non-bipartite triangle-free D2C graphs, the extremal family being certain inflations of a cycle of size 5. This, along with several observations, opens the question of strengthening the Murty-Simon Conjecture. We prove an improved bound of n²/4-2 for non-bipartite D2C graphs with a dominating edge, using a method which may be used to further improve the bound.

This is joint work with Florent Foucaud and Adriana Hansberg.