How to generate induced subgraphs of 3D integer lattice?

[Monica Bapna]

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?

[Dima Pasechnik]

checking that a subgraph embeds in  GridGraph([N,N,N]) may be formulated as an integer linear optimisation problem

(without an objective function, just checking its feasibility).

Each vertex v is encoded by 3 variables (x_v, y_v, z_v), and d(v,v'):=|x_v-x_v'|+|y_v-y_v'|+|z_v-z_v'| must be 1 for

each edge (v,v') and at least 2 for each non-edge. (And 0<=t_v<=7 for all t in {x,y,z}).

To cut the number of choices one can fix the variables for one of the edges (v,v'), say ((0,0,0),(0,0,1)).

 You will also need extra variables to remove absolute values - but this is a standard integer linear optimisation

transformation. (see e.g. https://stackoverflow.com/a/73406470/557937)

 

--
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 sage-support...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/302ef9ad-6da9-42c3-8bec-6f638e2d689an%40googlegroups.com.

[Vincent Delecroix]

I would rather use https://github.com/sagemath/sage/issues/32136!

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/CAAWYfq2NWOTZRyHfW3BxzPaVSCojQtL1YMZo4iC8FaMvL4ALiw%40mail.gmail.com.