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
15
stars
6
forks
source link
Add 2 graph properties: is_diameter_critical, and is_diameter_2_critical #632
Uses make_diameter_critical() function from Issue #631
IDEA: take a connected input graph, find a diameter-critical subgraph on the same vertex set
if the number of edges doesn't change then the subgraph is the graph
and our input graph must be diameter critical
def is_diameter_critical(g): #True if graph g is connected and diameter critical
if not g.is_connected():
print("in is_diameter_critical: input graph is not connected, returning None")
return None
h = make_diameter_critical(g)
if h.size() == g.size():
return True
else:
return False
def is_diameter_2_critical(g):
if not g.is_connected():
print("in is_diameter_2_critical: input graph is not connected, returning None")
return None
if g.diameter() == 2 and is_diameter_critical(g):
return True
else:
return False
Uses make_diameter_critical() function from Issue #631
IDEA: take a connected input graph, find a diameter-critical subgraph on the same vertex set
if the number of edges doesn't change then the subgraph is the graph
and our input graph must be diameter critical
def is_diameter_critical(g): #True if graph g is connected and diameter critical
def is_diameter_2_critical(g):