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 auxiliary function: make_diameter_critical #631

Open math1um opened 3 years ago

math1um commented 3 years ago

a connected graph with diameter d is diameter-critical if removing any edge increases its diameter

c5, the cycle on 5 vertices, is an example

add this to the AUXILIARY FUNCTIONS

def make_diameter_critical(g): #not unique, return connected graph with same diameter but diameter-critical

if not g.is_connected():
    print("error in make_diameter_critical: graph is not connected, returning None")
    return None

E = g.edges()
V = g.vertices()
h = copy(g)
D = g.diameter()

for e in E:
    Eh = list(h.edges())
    Eh.remove(e)
    h_temp = Graph([V,Eh])
    if h_temp.is_connected():
        if h_temp.diameter() == D:
            h = h_temp

return h