English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A graph is diameter-2-critical if its diameter is 2 but the removal of anyedge increases the diameter. A well-studied conjecture, known as theMurty-Simon conjecture, states that any diameter-2-critical graph of order nhas at most n${}^2$/4 edges, with equality if and only if G is a balancedcomplete bipartite graph. Many partial results about this conjecture have beenobtained, in particular it is known to hold for all sufficiently large graphs,for all triangle-free graphs, and for all graphs with a dominating edge. Inthis paper, we discuss ways in which this conjecture can be strengthened.Extending previous conjectures in this direction, we conjecture that, when weexclude the class of complete bipartite graphs and one particular graph, themaximum number of edges of a diameter-2-critical graph is at most ((n --1)${}^2$/4) + 1. The family of extremal examples is conjectured to consist ofcertain twin-expansions of the 5-cycle (with the exception of a set of thirteenspecial small graphs). Our main result is a step towards our conjecture: weshow that the Murty-Simon bound is not tight for non-bipartitediameter-2-critical graphs that have a dominating edge, as they have at most(n${}^2$/4) -- 2 edges. Along the way, we give a shorter proof of theMurty-Simon conjecture for this class of graphs, and stronger bounds for morespecific cases. We also characterize diameter-2-critical graphs of order n withmaximum degree n -- 2: they form an interesting family of graphs with adominating edge and 2n -- 4 edges.

Strengthening the Murty-Simon conjecture on diameter 2 critical graphs