3
$\begingroup$

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?

$\endgroup$
1
  • 6
    $\begingroup$ It might help if you would tell us where you have found the term used. $\endgroup$ Oct 11, 2020 at 11:15

2 Answers 2

3
$\begingroup$

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).

$\endgroup$
0
1
$\begingroup$

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.

Figure 1.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.