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.
