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 four solutions up to
isometry (cf. the main Grid subgraphs page).

Apparently, the graphs we construct here have the property that the "side-vertices" (those with two antipodal
neighbours)

and the unoccupied lattice points can be matched in adjacent pairs, and this also holds for the four graphs of girth 10.

(However, this does not hold for the induced subgraph given by {(*x, y, z*) ∈
**ℤ**^{3} | *x* + 2*y* + 3*z* ≡ 0, 1, 2, 4, 6, 8, 9 or 10 (mod 13)},

which is cubic of girth 8, and in which each vertex belongs to at most two distinct 8-cycles.)

The idea is to replace a "layer" (i.e., the vertices with a fixed *z*-value) of
*G*_{4} by two new layers.
Four consecutive

layers are thus shown in the figure. (Note that the first and the last have been shifted in the *xy*-plane relative

to each other, not only in *z*-direction.) The red vertices form an example of a pair of 8-cycles.

3D illustration, with the 8-cycle pairs marked in green: