Ask Your Question
1

Spanning elementary subgraphs on a given number of vertices

asked 2022-02-04 13:18:25 +0200

rewi gravatar image

updated 2022-02-08 23:04:38 +0200

Max Alekseyev gravatar image

Consider the following definition:

A subgraph H of a graph $G$ is called an elementary subgraph if each component of $H$ is either an edge or a simple cycle of length at least $3$. A spanning elementary subgraph is a subgraph having all components either edge (edge is a path on two vertices) or simple cycles.

Now my problem is: Consider the following code:

G = graphs.EmptyGraph()
G.add_edges([(1, 2), (2, 3), (3, 4), (4, 5), (5, 2), (6, 5), (6, 7)])
G.show()

Can we have a Sage code that gives all possible spanning subgraphs on $6$ vertices of the above graph?

Actually I am trying to find the all possible spanning elementary subgraphs on $6$ vertices of the above graph. By $6$ vertices, I mean the subgraphs of order 6 of the original graph.

edit retag flag offensive close merge delete

Comments

Should subgraphs be induced?

Max Alekseyev gravatar imageMax Alekseyev ( 2022-02-04 14:11:24 +0200 )edit

yes, you are correct

rewi gravatar imagerewi ( 2022-02-04 15:19:07 +0200 )edit

No no, ..there are spanning elementary subgraphs on $6$ vertices. for example, ${(1,2), (3,4),(5,6)}$ is a spanning elementary subgraphs on $6$ vertices. there are many more. another is ${(1,2),(3,4),(6,7)}$. All these spanning elementary subgraphs contains only edge components. There may be cycle components also. for example ${(2,3,4,5),(6,7)}$ is a spanning elementary subgraph on $6$ vertices. I am trying to compute all possible spanning elementary subgraphs on $6$ vertices. Is it clear now? if there is any problem, please let me know.

rewi gravatar imagerewi ( 2022-02-04 22:00:22 +0200 )edit

These subgraphs are not induced.

Max Alekseyev gravatar imageMax Alekseyev ( 2022-02-04 22:31:11 +0200 )edit

2 Answers

Sort by ยป oldest newest most voted
3

answered 2022-02-04 23:43:25 +0200

Max Alekseyev gravatar image

updated 2022-02-10 23:56:03 +0200

UPD, Solution is modified with respect to the edited question.

Here is a generator of such graphs from a given set of edges:

def add_edges_SES(E,H,i=0):
    if i == len(E):
        yield H.copy()
        return
    yield from add_edges_SES(E,H,i+1)
    e = E[i]
    if (not H.has_vertex(e[0])) and (not H.has_vertex(e[1])):
        H.add_edge(e)
        yield from add_edges_SES(E,H,i+1)
        H.delete_vertices(e[:2])

def constructSES(G):
    C = [frozenset(tuple(sorted(e[:2])) for e in c) for c in G.cycle_basis(output='edge')]
    for S in Subsets(C):
        T = set()
        for c in S:
            T = T.symmetric_difference(c)
        H = Graph()
        H.add_edges(T)
        if all( H.degree(v) == 2 for v in H.vertices() ):   # only simple cycles allowed
            yield from add_edges_SES(list(set(G.edges())-T),H)

Correspondingly, we can get a list all spanning elementary subgraphs of $G$ on 6 vertices as follows:

SES = [H for H in constructSES(G) if H.order()==6]

It turns out that for a given graph there are 6 such subgraphs on 6 vertices.

edit flag offensive delete link more

Comments

The code creates a list SES of such subgraphs. Then you can do whatever you want with it. E.g., to show them all run:

for H in SES:
    H.show()

or to print their edges run:

for H in SES:
    print(H.edges())
Max Alekseyev gravatar imageMax Alekseyev ( 2022-02-05 13:18:08 +0200 )edit

Actually I am trying to get an answer of the type given in https://ask.sagemath.org/question/435...

rewi gravatar imagerewi ( 2022-02-05 15:24:25 +0200 )edit

Actually my question is the following: Find all possible spanning elementary subgraphs on $12$ vertices of the following graph.

G=graphs.EmptyGraph()

G.add_edges([(1,2),(2,3),(3,4),(4,5),(6,7),(6,5),(1,7),(3,6),(6,8),(8,11),(8,9),(9,10),(10,11),(11,12),(12,8),(12,13)])

G.show()

rewi gravatar imagerewi ( 2022-02-06 11:34:24 +0200 )edit

For example $A={ (1,2),(7,6),(3,4),(12,13),(8,9),(10,11) }$ and $B={ (1,2,3,6,7),(8,11,12),(4,5),(9,10) }$ are two spanning elementary subgraphs on $12$ vertices of the given graph $G$. Here $A$ consists only of edges while $B$ contains both edge and cycle components. There are other spanning elementary subgraphs on $12$ vertices of the graph $G$. How to use sagemath to calculate all those spanning elementary subgraphs on $12$ vertices of the graph $G$? Am I clear now?

rewi gravatar imagerewi ( 2022-02-06 11:41:17 +0200 )edit

What's wrong with the posted solution?

Max Alekseyev gravatar imageMax Alekseyev ( 2022-02-06 15:37:51 +0200 )edit
1

answered 2022-02-05 13:37:55 +0200

updated 2022-02-08 14:52:32 +0200

This question has already been (nicely) answered https://ask.sagemath.org/question/435...

I copy here my answer (with small changes to return graphs).

def elementary_subgraphs(G, nmin=0):
    r"""
    Iterator over the elementary subgraphs of `G`.

    A subgraph `H` of a graph `G` is *elementary* if each of its connected
    components is either an edge or a cycle.

    INPUT:

    - ``G`` -- a Graph

    - ``nmin`` -- integer (default: ``0``); lower bound on the number of
      vertices involved in the elementary subgraphs of any returned
      solution. When set to ``G.order()``, the subgraphs must be spanning.
    """
    G._scream_if_not_simple()

    def rec(H, low):
        if not H.size():
            yield Graph()
            return
        if H.order() < low:
            # no solution
            return

        # We select an edge e = (u, v) of H and remove it
        u, v = next(H.edge_iterator(labels=False))
        H.delete_edge((u, v))

        # Case 1: return solutions without e
        for g in rec(H, low):
            if g.order() >= low:
                yield g

        # Case 2: select e as an isolated edge
        I = H.edges_incident([u, v])
        H.delete_vertices([u, v])
        for g in rec(H, low - 2):
            if g.order() + 2 >= low:
                g.add_edge(u, v)
                yield g
        H.add_vertices([u, v])
        H.add_edges(I)

        # Case 3: select e as part of a cycle
        for P in H.all_paths(u, v):
            K = H.copy()
            K.delete_vertices(P)
            nP = len(P)
            for g in rec(K, low - nP):
                if g.order() + nP >= low:
                    g.add_cycle(P)
                    yield g

        # Finally restore edge e
        H.add_edge(u, v)

    yield from rec(G.copy(), nmin)

We can use it like:

sage: G = Graph([(1,2),(2,3),(3,4),(4,5),(5,2),(6,5),(6,7)])
sage: ES = [H for H in elementary_subgraphs(G, nmin=6)]
sage: len(ES)
6
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2022-02-04 13:18:25 +0200

Seen: 165 times

Last updated: Feb 10