I want to find out undirected, connected, non-isomorphic graphs having upto
9 vertices which are induced subgraphs of a 3D integer lattice.
Step 1. I generate connected, bipartite, triangle free graphs with N
vertices with vertices having maximum degree 6 using:
graphs.nauty_geng("%d -c -t -b -D6"%N)
Step 2. I am trying to use is_partial_cube() to filter out graphs from Step
1. However, is_partial_cube() also allows graphs which can be embedded in
integer lattices of dimensions greater than 3.
eg.
Code:
g=Graph({8:[2,3,4,5,6,7],7:[0,1]})
if sage.graphs.partial_cube.is_partial_cube(g, certificate=False)==True:
print 'Graph can be embedded in a hypercube'
g.show()
Output:
But this cannot be an induced subgraph of 3D integer lattice - either of
the vertices 0 or 1 should be connected to one of the vertices 2 to 6.
Questions:
A. Is there a way to get only induced subgraphs of 3D cubic integer lattice
using is_partial_cube()?
B. Alternatively, I tried using subgraph_search(g1,induced=True) to check
if a graph, g1, of N vertices generated in Step 1 is a subgraph of the
graph GridGraph([N,N,N]). However, the processing time is very large even
for N=7. What would be the most efficient way to generate the required
graphs using sagemath?
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-support/302ef9ad-6da9-42c3-8bec-6f638e2d689an%40googlegroups.com.
