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

New utility: make_alpha_critical #640

Closed math1um closed 2 years ago

math1um commented 3 years ago 
def make_alpha_critical(g): 
    """
    assumes g is connected, produces connected alpha_critical_subgraph with same independence number.
    """
    alpha = independence_number(g)

    E = g.edge_iterator(labels=False)
    for (v,w) in E:
        h = copy(g)
        h.delete_edge(v,w)
        if h.is_connected() and (alpha == independence_number(h)):
            g = h
    return g
jaritaes99 commented 2 years ago

Added to utilities