Find copy of subgraph and check if graph induced by neighborhood of particular vertex is bipartite

asked 2019-04-14 01:37:28 +0200

merluza gravatar image

updated 2019-04-14 01:39:11 +0200

I asked Sage to generate all graphs on 7 vertices and 12 edges with clique number 4 using the command

g7_4=[g for g in graphs.nauty_geng('7 12') if g.clique_number()==4]

Next I defined a graph H as follows:

H=graphs.CompleteGraph(4)
H.add_edges([(4,0), (4,1), (4,5)])

For every induced isomorphic copy H' of H in each graph g in g7_4 I want Sage to find out if the subgraph induced by the neighborhood of the isomorphic copy in H' of the vertex labeled 4 in H is bipartite or not.

The issue here is that I want to target the vertex in H' that plays the role of 4 in H, but I can't figure out how to do that.

Here is my feeble attempt:

for g in g7_4:
 for p in g.subgraph_search_iterator(H,induced=True):  #for each induced isomorphic copy of H in g
     N=p.subgraph(Set(H.neighbors(4)))   #let N be subgraph induced by neighborhood of 4 (vertex from H)
     if not N.is_bipartite():
          print(g7_4.index(g), 'bipartite')
     else:
          print(g7_4.index(g), 'not bipartite')

Please help me with my code! I am still new to Sage. Thank you!

edit retag flag offensive close merge delete