ASKSAGE: Sage Q&A Forum - Latest question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 13 Apr 2019 18:37:28 -0500Find copy of subgraph and check if graph induced by neighborhood of particular vertex is bipartitehttp://ask.sagemath.org/question/46149/find-copy-of-subgraph-and-check-if-graph-induced-by-neighborhood-of-particular-vertex-is-bipartite/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!merluzaSat, 13 Apr 2019 18:37:28 -0500http://ask.sagemath.org/question/46149/Create program to find which graphs contain specific subgraphhttp://ask.sagemath.org/question/45952/create-program-to-find-which-graphs-contain-specific-subgraph/ Hello, I am pretty new to Sage, and am discovering all the wonderful things it can do. I know how to ask Sage to generate a list of graphs that satisfy particular properties. To do this I "call" a program named "nauty". For example, if I would like to generate all graphs with 10 vertices, 25 edges, and clique number 4 I type the following:
sage: g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
Now say that I want to check which of these graphs contain a particular subgraph. For example, say I want to know which one of these graphs contain a 5-cycle. How can I ask Sage to go through the list of graphs in g10 and tell me this information?
Thank you in advance!merluzaSat, 30 Mar 2019 12:56:30 -0500http://ask.sagemath.org/question/45952/Graph.subgraph_search() obtaining the indices?http://ask.sagemath.org/question/44792/graphsubgraph_search-obtaining-the-indices/It is nice that Graph.subgraph_search() returns a subgraph, but I need the indices of the larger graph to manipulate it, for example finding the subgraph neighbors. Is there a way to obtain the original indices?RushBackThu, 27 Dec 2018 08:56:10 -0600http://ask.sagemath.org/question/44792/Paths beginning with a certain vertexhttp://ask.sagemath.org/question/38452/paths-beginning-with-a-certain-vertex/So I have a graph $G$ and a distinguished vertex, labeled with $0$ say. I would like to create a list of all paths of length $k$ that start with $0$.
One way I see how to do this with subgraph_search is to change $0$ into a large clique (larger than the clique number of $G$) and then use subgraph_search_iterator to find all subgraphs with a large clique connected to a path of length $k-1$. However, this seems pretty inefficient. Is there a better way?
vukovMon, 31 Jul 2017 17:09:40 -0500http://ask.sagemath.org/question/38452/How can I search and count all induced subgraphs in a directed graph with edge labels?http://ask.sagemath.org/question/26630/how-can-i-search-and-count-all-induced-subgraphs-in-a-directed-graph-with-edge-labels/Hello all,
I can extract all induced subgraphs and count them in a graph. My question is how I can search and count all induced subgraphs in a labeled graph (a graph with edge labels)? In documentation of g.subgraph() and g.subgraph_search_count() is mentioned that these functions should work on labeled graphs as well. but it does not work. Here is an example:
sage: g=DiGraph()
sage: g.add_vertex(0)
sage: g.add_vertex(1)
sage: g.add_vertex(2)
sage: g.add_edge(0,1,label="a")
sage: g.add_edge(1,2,label="b")
sage: g.plot(color_by_label="true")
sage: g.plot(color_by_label=true)
sage: s=DiGraph()
sage: s.add_vertex(0)
sage: s.add_vertex(1)
sage: s.add_edge(0,1,label="a")
sage: s.plot(color_by_label=true)
sage: g.subgraph_search_count(s)
2
While it should return 1 not 2.
bsstenissThu, 23 Apr 2015 05:29:44 -0500http://ask.sagemath.org/question/26630/