Revision history [back]

Have you tried the alternative definition of taking an independent set in the square of the line graph ?

def square(G):
    H = copy(G)
    for u in H:
        H.add_edges([(u, v) for v in H.vertex_boundary(H.neighbors(u, closed=True))])
    return G

def induced_matching(G):
    L = G.line_graph(labels=False)
    return square(L).independent_set()

This gives

sage: G = graphs.PetersenGraph()
sage: induced_matching(G)
[(0, 1), (2, 7), (3, 4), (5, 8), (6, 9)]

Have you tried the alternative definition of taking an independent set in the square of the line graph ?

def square(G):
    H = copy(G)
    for u in H:
        H.add_edges([(u, v) for v in H.vertex_boundary(H.neighbors(u, closed=True))])
    return G
H

def induced_matching(G):
    L = G.line_graph(labels=False)
    return square(L).independent_set()

This gives

sage: G = graphs.PetersenGraph()
sage: induced_matching(G)
[(0, 1), (2, 7), (3, 4), (5, 8), (6, [(7, 9)]

Have you tried the alternative definition of taking an independent set in the square of the line graph ?

def square(G):
    H = copy(G)
    for u in H:
G:
        H.add_edges([(u, v) for v in H.vertex_boundary(H.neighbors(u, G.vertex_boundary(G.neighbors(u, closed=True))])
    return H

def induced_matching(G):
    L = G.line_graph(labels=False)
    return square(L).independent_set()

This gives

sage: G = graphs.PetersenGraph()
sage: induced_matching(G)
[(7, 9)]
[(1, 6), (3, 4), (5, 7)]

EDIT: now method square returns H and not G...G... EDIT2: now method square is correct.