search

math1um / objects-invariants-properties

Objects, Invariants and Properties for Graph Theory (GT) automated conjecturing: in particular with the Sage program CONJECTURING: http://nvcleemp.github.io/conjecturing/
GNU General Public License v3.0
14 stars 6 forks source link

Add property: is_diameter_two_critical #573

Open math1um opened 6 years ago

math1um commented 6 years ago

A graph is diameter-2-critical if the diameter is 2 and the removal of any edge increases the diameter.

C_5, the cycle on 5 vertices, is an example.

This shows up in a well-studied conjecture of Simon and Murty (see attached 2015 survey):

Haynes, Teresa W., et al. "Progress on the Murty–Simon Conjecture on diameter-2 critical graphs: a survey." Journal of Combinatorial Optimization 30.3 (2015): 579-595.

haynes-henning-diameter-2-critical-graphs-conjecture-survey-2015.pdf

This property is efficient (as its a distance property, although iteration of diameter over each edge may make this relatively slow in practice).

nvcleemp commented 6 years ago

The concept of being critical for some properties is quite common. Maybe we can make a general factory method that can be used for different properties.