Skip to main content

On a class of Hamiltonian laceable 3-regular graphs, contains the definition of the brick product of even cycles, with figures showing examples.

Definition. Let $m$, $n$ and $r$ be a positive integers. Let $C_{2n} = 0 1 2 \ldots (2n - 1) 0$ denote a cycle of order $2n$. The $(m, r)$-brick-product of $C_{2n}$, denoted by $C(2n, m, r)$, is defined in two cases as follows.

For $m = 1$, we require that $r$ be odd and greater than $1$. Then $C(2n, m, r)$ is obtained from $C_{2n}$ by adding chords $2k (2k + r)$, $k = 1, \dots, n$, where the computation is performed modulo $2n$.

For $m > 1$, we require that $m + r$ be even. Then $C(2n, m, r)$ is obtained by first taking the disjoint union of $m$ copies of $C_{2n}$, namely $C_{2n}(1), C_{2n}(2), \dots, C_{2n}(m)$, where for each odd $i = 1, 2, \dots, m-1$ and each even $k = 0, 1, \dots, 2n - 2$, an edge (called a brick edge) is drawn to join $(i, k)$ to $(i + 1, k)$, whereas, for each even $i = 1, 2, \dots, m - 1$ and each odd $k = 1, 2, \dots, 2n - 1$, an edge (also called a brick edge) is drawn to join $(i, k)$ to $(i + 1, k)$. Finally, for each odd $k = 1, 2, \dots, 2n - 1$, an edge (called a hooking edge) is drawn to join $(1, k)$ to $(m, k + r)$. An edge in $C(2n, m, r)$ which is neither a brick edge nor a hooking edge is called a flat edge.

See also Rainbow connection in brick product graphs.

Figs. 1-3: The brick products C(10,1,5), C(10,2,4), and C(10,3,5).

Carlo Beenakker
  • 188.1k
  • 18
  • 448
  • 651