I would rather use https://github.com/sagemath/sage/issues/32136!
On Thu, 2 Mar 2023 at 09:36, Dima Pasechnik <[email protected]> wrote: > > > On Thu, Mar 2, 2023 at 8:42 AM Monica Bapna <[email protected]> > wrote: > >> 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? >> > > 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 [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 >> <https://groups.google.com/d/msgid/sage-support/302ef9ad-6da9-42c3-8bec-6f638e2d689an%40googlegroups.com?utm_medium=email&utm_source=footer> >> . >> > -- > 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/CAAWYfq2NWOTZRyHfW3BxzPaVSCojQtL1YMZo4iC8FaMvL4ALiw%40mail.gmail.com > <https://groups.google.com/d/msgid/sage-support/CAAWYfq2NWOTZRyHfW3BxzPaVSCojQtL1YMZo4iC8FaMvL4ALiw%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > -- 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/CAGEwAA%3DL6VCErmSN3fXZtkVfHw-X7KSfNkAzUiPg6%3DCFZainwg%40mail.gmail.com.
