What is the definition of brick product of graphs?

Question

Can anyone help me with the exact definition of brick product of graphs, say path, cycle.

I am not able to find a paper with a clear definition on the internet. Can anyone give me a URL to such a paper?

Answer 1

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.

Answer 2

You might also want to see: Alspach, B., Hamilton cycles in cubic Cayley graphs on dihedral groups, Ars Comb. 28, 101–108 (1989). Zbl 0722.05047, MR1039136. PDF available at ResearchGate.

Let $C_n$ and $P_n$ denote the cycle and path of length $n$, respectively.

2.1 Definition: The brick product of $C_n$ with $P_m$, $m \geq 1$, is denoted $C_n^{[m+1]}$ and is defined as follows. Let $V(C_n) = \{ u_1, u_2, \dots, u_n \}$, $E(C_n) = \{ u_1 u_2, u_2 u_3, \dots, u_n u_1 \}$, $V(P_m) = \{ v_1, v_2, \dots, v_{m+1} \}$, and $E(P_m) = \{ v_1 v_2, \dots, v_m v_{m+1} \}$. The vertex-set of $C_m^{[m+1]}$ [typo: should be $C_n^{[m+1]}$] is the cartesian product $V(C_n) \times V(P_m)$. The edge-set consists of all pairs of the form $(u_i, v_t) (u_i, v_{t+1})$, where $i+t \equiv 0 \pmod{2}$, $i = 1, 2, \dots, n$, and $t = 1, 2, \dots, m$. The brick product $C_4^{[5]}$ is shown in Figure 1.