Grid subgraphs with disjoint pairs of 8-cycles
by Jan Kristian Haugland
We construct cubic
induced subgraphs of
the 3-dimensional grid with no cycles of length 4 or 6, and with some 8-cycles
that only appear in disjoint pairs. Currently, no corresponding examples with all 8-cycles being disjoint are known, while the
problem with no 8-cycles at all has been proven to have exactly 4 solutions up to isometry (cf. the main Grid subgraphs page).
The idea is to replace a "layer" (i.e., the vertices with a fixed z-value) of G4 by two new layers.
Four consecutive layers are thus shown in the figure. The red vertices form an example of a pair of 8-cycles.
3D illustration, with the 8-cycle pairs marked in green: