Let Pn + 1, Cn and Sn represent a path, cycle, and star with n edges, Qn denote the n-dimensional hypercube graph. The (ℋ1, ℋ2)−multidecomposition of G for graphs ℋ1, ℋ2, and G is a decomposition of G into copies of ℋ1 and ℋ2, where there is at least one copy of ℋ1 and at least one copy of ℋ2. In this paper, we prove that the graph Qn is (Sn − 2, C4)−multidecomposable for n ≥ 4 and (Sn − 4, P5)−multidecomposable for n ≥ 5.
The finite, simple and undirected graphs with no loops are considered in this paper. The readers has to refer [5] for better understanding about the terms of standard graph theory. Let \(P_{n+1}\) represent the path with \(n\) edges. Let \(C_n\) represent the cycle with \(n\) edges. \(S_n\) represents the complete bipartite graph \(K_{1,n}\), which is referred to a star. The \(n-\)dimensional hypercube, represented by the graph \(Q_n\), is a graph whose vertices are \(2^n-\)tuples of \(0's\) and \(1's\), and whose edge set \(E(Q_n)\) is made up of pairs of vertices that differ in only one coordinate. Whether the tuple contains an odd or even number of non-zero coordinates determines whether it is categorized as odd or even.
An edge-disjoint subgraph of a graph \(G\) is called a decomposition of \(G\) if every edge of \(G\) is exactly in one \(\mathcal{H}_i\). These subgraphs are \(\mathcal{H}_1, \mathcal{H}_2, \cdots, \mathcal{H}_n\). \(G\) is decomposed or decomposable in \(\mathcal{H}_1, \mathcal{H}_2, \cdots, \mathcal{H}_n\). The decomposition of \(G\) is denoted by \(\Psi=\{\mathcal{H}_1, \mathcal{H}_2, \cdots, \mathcal{H}_n\}\). It is also said that \(G\) admits a \(\{\mathcal{H}_1, \mathcal{H}_2, \cdots, \mathcal{H}_n\}\)-decomposition. If each \(\mathcal{H}_i \cong \mathcal{H}\), then it is said that \(G\) has a \(\mathcal{H}-\)decomposition. A \((\mathcal{H}_1, \mathcal{H}_2)-\)multidecomposition of \(G\) is a partitioning of the edge set of \(G\) into multiple copies of \(\mathcal{H}_1\) and multiple copies of \(\mathcal{H}_2\), where there is at least one copy of \(\mathcal{H}_1\) and at least one copy of \(\mathcal{H}_2\). \(G\) has a \(\{p\mathcal{H}_1, q\mathcal{H}_2\}-\)decomposition if its decomposition consists of \(p\) copies and \(q\) copies of \(\mathcal{H}_1\) and \(\mathcal{H}_2\), respectively. \(G\) should be fully \(\{\mathcal{H}_1,\mathcal{H}_2\}-\)decomposable or if a similar decomposition occurs for all values of \(p\) and \(q\) that satisfy the necessary requirements, then it has a \(\{\mathcal{H}_1, \mathcal{H}_2\}_{\{p, q\}}-\)decomposition.
Kringel [19] first demonstrated that the graph \(Q_n\) has a Hamiltonian cycle decomposition for every even \(n\) if \(n \geq 2\) and \(n\) is a power of \(2\). Ringle next asked whether \(Q_n\) has a Hamiltonian decomposition. Aubert and Schneider [4] implicitly resolved Ringel’s question, and for explicit statement refer Alspach et al. in [2]. Apart from Hamiltonian cycle decomposition, in [7] Horak showed that any graph \(H\) of size \(n\) whose blocks are \(C_n\), \(n\) is even, or \(Q_n\) is decomposed by an edge. It has been evidenced that certain \(n-\)cycle’s edge sets of \(Q_n\) are fundamental sets in [15] by Ramras. Mollard and Ramras established in [14] that the edge sets of \(2n-\)cycles in \(Q_n\) serve as fundamental sets. It has been shown that \(Q_n\) admits a path decomposition of length \(m\) for odd \(n\) with certain conditions by Anick and Ramras [3]. Wagner and Wild [20] demonstrated that the hypercube \(Q_n\) decomposed into isomorphic copies of trees, each of which contains \(n\) edges.
As demonstrated by Shyu in [17], the complete graph \(K_n\) allows a decomposition into \(p\) copies of \(P_5\) and \(q\) copies of \(C_4\), given the necessary and sufficient conditions. The necessary and sufficient conditions for the \(\{C_4,E_2\}-\) decomposition of the cartesian product and tensor product of paths, cycles, and complete graphs were obtained by Abueida and Devan in [1]. Some necessary and sufficient conditions for the existence of \(\{P_{k+1},C_k\}_{\{p, q\}}-\)decomposition of \(K_n\) and \(K_{m, n}\) were obtained by Jeevadoss and Muthusamy [10]. The above decomposition was extended to complete bipartite multigraphs \(K_{m, n}(\lambda )\) in [11]. The necessary and sufficient conditions for the existence of \(\{P_{5}, C_4\}_{\{p, q\}}-\) decomposition of tensor product and cartesian product of complete graphs were obtained by Jeevadoss and Muthusamy in [12]. Lee and Chen [13] determined the criteria required for a complete graph to be decomposed into \(p\) copies of Hamiltonian paths (cycles) and \(q\) copies of \(S_3\). Ilayaraja and Muthusamy [9] explored the conditions required for decomposing complete bipartite graphs into cycles and stars having four-edge, establishing the existence of a \(\{pC_4, qS_4\}-\) decomposition of \(K_{m,n}\). Recently, Shyu [18] proved the decomposition of \(K_r\) and \(K_{r,s}\) into \({P_5}'s\), \({C_4}'s\) and \({S_4}'s\). In [16], Saranya and Jeevadoss demonstrated that the graph \(Q_n\) is \(\{P_{5},C_4\}_{\{p, q\}}-\)decomposable. In [6], Chaadhanaa and Hemalatha explore the conditions that are both necessary and sufficient for the existence of a \(\{P_{5},Y_5\}-\) multi-decomposition of \(K_n\) and \(K_{m,n}\). In [8], Ilayaraja and Muthusamy determined the criteria required for the existence of a \(\{pP_{5},qS_4\}-\)decomposition of \(K_n\), providing both necessary and sufficient conditions.
In this paper, we prove that the graph \(Q_n\) is \((S_{n-2},C_4)-\)multidecomposable for \(n\geq 4\) and \((S_{n-4},P_5)-\)multidecomposable for \(n\geq 5\).
We represent the graph \(Q_n\) as a \(n-\)regular bipartite graph. As illustrated in Figure 1, for instance, we describe the graph \(Q_4\) as a \(4\)-regular bipartite graph. The \(4\)-regular bipartite graph has vertex bipartition \((\mathcal{X},\mathcal{Y})\) such that \(\mathcal{X}=(a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8)\) and \(\mathcal{Y}=(b_1,b_2,b_3,b_4,b_5,b_6,b_7,b_8)\).
We represent the graph \(Q_5\) into \(4\) copies of \(Q_3\) and edges between \(Q_3\) as shown in Figure 2.
The edges between \(Q_3\) as shown in Figure 3.
Similarly the graph \(Q_n\) is decomposed into \(4\) copies of \(Q_{n-2}\) and edges between \(4\) copies of \(Q_{n-2}\). The edges between \(4\) copies of \(Q_{n-2}\) of \(Q_n\) is denoted by a \(2-\)regular bipartite graph \(N_{2^{n-1},2^{n-1}}\) as shown in Figure 4. The graph \(Q_n\) can be written as \(Q_n=4Q_{n-2} \oplus N_{2^{n-1},2^{n-1}}\).
The partite sets \(\mathcal{X}\) and \(\mathcal{Y}\) are each divided into four equal subsets, labeled as \(\mathcal{X}a^{(1)}\), \(\mathcal{X}a^{(2)}\), \(\mathcal{X}a^{(3)}\), \(\mathcal{X}a^{(4)}\) and \(\mathcal{Y}b^{(1)}\), \(\mathcal{Y}b^{(2)}\), \(\mathcal{Y}b^{(3)}\), \(\mathcal{Y}b^{(4)}\). The adjacency relations between these subsets are as follow: The vertices in \(\mathcal{X}a^{(1)}\) are adjacent to those in \(\mathcal{Y}b^{(2)}\) and \(\mathcal{Y}b^{(3)}\). The vertices in \(\mathcal{X}a^{(2)}\) are adjacent to those in \(\mathcal{Y}b^{(1)}\) and \(\mathcal{Y}b^{(4)}\). The vertices in \(\mathcal{X}a^{(3)}\) are adjacent to those in \(\mathcal{Y}b^{(1)}\) and \(\mathcal{Y}b^{(4)}\). The vertices in \(\mathcal{X}a^{(4)}\) are adjacent to those in \(\mathcal{Y}b^{(2)}\) and \(\mathcal{Y}b^{(3)}\).
Remark 2.1. \(\mathcal{G} \oplus \mathcal{H}\) has a similar decomposition if \(\mathcal{G}\) and \(\mathcal{H}\) have \(\{S_{n-2},C_4\}-\) and \(\{S_{n-4},P_5\}-\) multidecomposition.
Here we use the following construction.
Construction 1. Let \({C_4}^{(1)}=(a_1 a_2 a_3 a_4)\) and \({C_4}^{(2)}=(b_1 b_2 b_3 b_4)\) be two 4-length cycles that share a single common vertex \(x\), such that \(a_1=b_1=x\). It is assumed that each cycle has at least one neighbor of \(x\) that is not shared with the other cycle \((e.g., a_4\notin{C_4}^{(2)},\,b_2\notin{C_4}^{(1)})\). This setup allows to construct two edge-disjoint paths of length \(4\). Let \({P_5}^{(1)}\) and \({P_5}^{(2)}\) be created from \({C_4}^{(1)}\) and \({C_4}^{(2)}\), as shown in Figure 5, where \({P_5}^{(1)}={C_4}^{(1)}-xa_4\cup xb_2\), \({P_5}^{(2)}={C_4}^{(2)}-xb_2 \cup xa_4.\)
The existence of \((S_{n-2},C_4)-\)multidecomposition and \((S_{n-4},P_5)-\)multidecomposition of the graph \(Q_n\) is represented in this section. The following lemmas are useful for our main theorem.
Lemma 3.1. Let \(n\) be a positive integer and \(n\geq 3\). Then the graph \(N_{2^{n-1},2^{n-1}}\) is \(C_4\) decomposable.
Proof. The graph \(N_{2^{n-1},2^{n-1}}\) has two partite sets \(\mathcal{X}\) and \(\mathcal{Y}\), the corresponding labels are \(\mathcal{X}=(a_1, a_2, a_3, \cdots,a_{2^{n-1}})\) and \(\mathcal{Y}=(b_1, b_2, b_3, \cdots,b_{2^{n-1}})\) . The following construction decomposes the bipartite graph \(N_{2^{n-1},2^{n-1}}\) into \(2^{n-2}\) copies of \(C_4\).
\[(a_{i}\,\,b_{2^{n-3}+i}\,\,a_{3*2^{n-3}+i}\,\,b_{2^{n-2}+i}\,\,a_i),\] \[(b_{i}\,\,a_{2^{n-3}+i}\,\,b_{3*2^{n-3}+i}\,\,a_{2^{n-2}+i}\,\,b_i),\] for \(i=1, 2, \cdots, 2^{n-3}\). ◻
Lemma 3.2. Let \(m\) be a positive integer and \(m\geq 2\). Then the graph \(Q_m\) is \(S_{m}\) decomposable.
Proof. The graph \(Q_m\) is represented as \(m-\)regular bipartite graph. There are \(2^{m-1}\) vertices in each partite sets \(X\) and \(Y\). Each vertices in \(X\) partite set is adjacent to exactly \(m\) distinct vertices in \(Y\) partite set. Hence the \(m-\)dimensional hypercube \(Q_m\) is decomposed into \(2^{m-1}\) copies of \(S_{m}\). ◻
Now we prove the main result of this section
Theorem 3.3. Let \(n\) be a positive integer and \(n\geq 3\). Then the graph \(Q_n\) has a \((S_{n-2},C_4)-\) multidecomposition.
Proof. The graph \(Q_n\) can be viewed as \(4Q_{n-2}\oplus N_{2^{n-1},2^{n-1}}\). By Lemma \(3.2\), the graph \(Q_{n-2}\) is \(S_{n-2}\) decomposable and by Lemma \(3.1\), the graph \(N_{2^{n-1},2^{n-1}}\) is \(C_4\) decomposable. Hence the graph \(Q_n\) for \(n\geq 3\) is \(\{2^{n-1}S_{n-2},2^{n-2}C_4\}-\)multidecomposable. ◻
Theorem 3.4. Let \(n\) be a positive integer and \(n\geq 5\). Then the graph \(Q_n\) is \((S_{n-4}\),\(P_5)-\) multidecomposable.
Proof. Represent the graph \(Q_n\) into \(4\) copies of \(Q_{n-2}\) and \(2-\)regular bipartite graph \(N_{2^{n-1},2^{n-1}}\) as shown in Figure 3. Represent the graph \(Q_{n-2}\) into \(4\) copies of \(Q_{n-4}\) and \(2-\)regular bipartite graph \(N_{2^{n-3},2^{n-3}}\). The graph \(Q_n\) can be written as \(Q_n= N_{2^{n-1},2^{n-1}}\oplus 4(N_{2^{n-3},2^{n-3}})\oplus16Q_{n-4}\). By Lemma \(3.2\), \(Q_{n-4}\) is \(S_{n-4}\) decomposable. The \(4-\)regular bipartite graph \(N_{2^{n-1},2^{n-1}}\oplus 4N_{2^{n-3},2^{n-3}}\) is decomposed into \(2^{n-1}\) copies of \(C_4\), since the \(2-\)regular bipartite graph \(N_{2^{n-1},2^{n-1}}\) is \(C_4\) decomposable and the \(2-\)regular bipartite graph \(N_{2^{n-3},2^{n-3}}\) is \(C_4\) decomposable.
Each vertex in the \(\mathcal{X}\) partite set is a common vertex of exactly \(2C_4\)s as shown in Figure 6, since the \(4-\)regular bipartite graph \(N_{2^{n-1},2^{n-1}}\oplus 4(N_{2^{n-3},2^{n-3})}\) is decomposed into \(2^{n-1}\) copies of \(C_4\) and these cycles are edge-disjoint cycles. The common vertex has four neighbors, with two belonging to one \(4\)-cycle and the other two to another \(4\)-cycle. Since at least one neighbor of a common vertex is not shared with the other cycle, by Construction \(1\) these cycles are decomposed into same copies of \(P_5\). Hence the graph \(Q_n\) for \(n\geq 5\) is \(\{2^{n-1}S_{n-4},2^{n-1}P_5\}-\)multidecomposable.
