On the Product \((\overrightarrow{C_m} \otimes_h \Gamma)=\{\overrightarrow{C_n} , \overleftarrow{C_n}\}\) and Other Related Topics

Abstract

Consider a labeled and strongly oriented cycle \(\overrightarrow{C_m}\) and a set \(\mathcal{T} = \{\overrightarrow{C_n}, \overleftarrow{C_n}\}\), where \(\overrightarrow{C_n}\) and \(\overleftarrow{C_n}\) are two labeled and strongly oriented cycles with the same underlying graph and opposite orientations. Let \(h: E(\overrightarrow{C_m}) \to \Gamma\) be any function that sends every edge of \(\overrightarrow{C_m}\) to either \(\overrightarrow{C_n}\) or \(\overleftarrow{C_n}\). The primary goal of this paper is to study the underlying graph of the product \(\overrightarrow{C_m} \otimes_h \Gamma\), defined as follows:
\[ V(\overrightarrow{C_m} \otimes_h \Gamma) = V(\overrightarrow{C_m}) \times V(\overrightarrow{C_n}) \]
and
\[ ((a, b), (c, d)) \in E(\overrightarrow{C_m} \otimes_h \Gamma) \iff (a, c) \in E(\overrightarrow{C_m}) \wedge (b, d) \in h(a, c). \]
This product is of interest since it preserves various types of labelings, such as edge-magic and super edge-magic labelings. Additionally, we investigate the algorithmic complexity of determining whether a digraph \(\overrightarrow{D}\) can be factored using the product \(\otimes_h\), given a set of digraphs \(\Gamma\). This is the main topic of the third section of the paper.