The unit graph of a commutative ring with a non-zero identity is a graph with vertices as ring elements, and there is an edge between two distinct vertices if their sum is a unit. This study investigates the decomposition of the unit graph by examining its induced subgraphs and analyze key graph invariants, such as connectivity, diameter, and girth, for a finite local ring. We further decompose the unit graph of certain finite commutative rings into fundamental structures, such as cycle and star graphs.
Grimaldi [13] introduced the notion of the unit graph, which is represented as \(G(\mathbb{Z}_{\textit{n}})\), for the commutative ring \(\mathbb{Z}_{\textit{n}}\). Ashrafi et al. [7] carried out further investigation and provided a generalization of the unit graph \(G(\mathbb{Z}_{\textit{n}})\) to the unit graph \(G(\mathrm{R})\) for an arbitrary ring \(\mathrm{R}\) with unity. In this order, Heydari and Nikmehr [15] studied the structural properties of the unit graph of a left Artinian ring. Later, Su and Wei [21] studied the diameter of the unit graph of commutative rings. Afkhami and Khosh-Ahang [1] evaluated some structural properties and some graph invariants of the unit graph of the polynomial ring. Various aspects of the unit graph of a commutative ring have been studied extensively by various researchers [3, 10, 19]. In this paper, we study the structural properties of unit graphs of specific rings by decomposing them into induced subgraphs.
Graph decomposition is a fundamental tool in computer science that offers a powerful means of simplifying and analyzing complex networks by breaking them into manageable substructures such as trees, paths, stars, or cycles. In large-scale data systems, decomposition methods like hierarchical or core decomposition enable scalable algorithms for graph mining, pattern recognition, and information retrieval [2, 9]. As a result, decomposition of graphs into simple graphs like \(P_{\textit{n}}\), \(C_{\textit{n}}\), or \(S_{\textit{n}}\) has been thoroughly investigated by many researchers in the field of graph theory. One may refer to [6, 14, 17, 16, 18]. The potential of complex networks modeled as a unit graphs makes the decomposition of unit graphs a compelling problem to explore.
Let \(E(G)\) be the edge set and \(V(G)\) be the vertex set of a graph \(G\). A partition of \(G\) into edge-disjoint subgraphs \(D_{1}, D_{2},\dots, D_{\textit{k}}\) such that \(E(G)= E(D_{1})\cup E(D_{2}) \cup\cdots \cup E(D_{\textit{k}})\), is called a decomposition of \(G\), and denoted as \(G= D_1\oplus D_2\oplus\cdots\oplus D_{\textit{k}}\). If \(D_{i}\cong D\), for \(1\leq i\leq \textit{k}\), then \(G\) has a \(D\)-decomposition; otherwise, it is called multi-decomposition. If \(G\) has a decomposition into \(\alpha\) copies of \(D_{1}\), \(\beta\) copies of \(D_{2}\), and \(\gamma\) copies of \(D_{3}\) then \(G\) has a \(\{\alpha D_{1}, \beta D_{2}, \gamma D_{3}\)}- decomposition. For \(\gamma=0\), \(G\) follows a {\({\alpha} D_{1}, {\beta} D_{2}\)}- decomposition [11].
The question of how a unit graph can be systematically decomposed into substructures remains unanswered. In particular, decomposing the unit graph into its induced subgraphs addresses two significant problems:
1. Determining some structural properties of unit graphs for various classes of commutative rings such as local rings and ring of integers modulo \(\textit{n}\).
2. Classifying the various graph properties using the subgraphs of the unit graph for some particular commutative rings.
Anderson and Badawi [5] studied induced subgraphs in the total graph of commutative rings. They studied the connectivity, diameter, and girth in the (induced) subgraphs of the total graph. Motivated by their work, we study the (induced) subgraphs of \(G(\mathrm{R})\) with the vertex set \( {Z}\) (set of zero divisors of \(\mathrm{R}\)) and the \(Reg(\mathrm{R})\) (set of regular elements of \(\mathrm{R}\)) denoted as \(G_{ {Z}}(\mathrm{R})\) and \(G_{R}(\mathrm{R})\), respectively. We further find some graph properties, such as the decomposition of the unit graph for a finite local ring and the ring of integers modulo \(\textit{n}\). Additionally, we decompose \(G(\mathbb{Z}_{\textit{p}^{r}})\) and \(G(\mathbb{Z}_{\textit{p}\textit{q}})\) into cycle and star graphs.
This paper is organized as follows: In Section 2, we address the first problem and study the connectivity, diameter, and girth of the unit graph of a finite local ring and study the \(\{\alpha D_1, \beta D_2, \gamma D_3\}\)-decomposition of \(G(\mathrm{R})\) for a finite local ring. In Sections 3 and 4, we focus on the second problem and study the decomposition of \(\mathbb{Z}_{n}\) into its subgraphs. Moreover, we decompose \(G(\mathbb{Z}_{\textit{p}^{r}})\), \(G(\mathbb{Z}_{\textit{p}\textit{q}})\) into cycle and star graphs.
Throughout this paper, all graphs are considered to be simple and undirected unless specified otherwise. We use the following standard notations: \(\mathsf{K}_{\textit{n}}\) represents a complete graph with \(\textit{n}\) vertices, and \(\mathsf{K}_{\textit{m}, \textit{n}}\) denotes a complete bipartite graph consisting of two vertex sets with cardinalities \(\textit{m}\) and \(\textit{n}\). When these sets have equal cardinality, the graph is denoted as \(\mathsf{K}_{\textit{m}, \textit{m}}\), signifying a balanced, complete bipartite graph. \(\mathsf{K}_{\textit{m}_1,\textit{m}_2,\dots,\textit{m}_l }\), represents a complete multipartite graph with \(\textit{l}\) parts and \(\textit{m}_1,\textit{m}_2,\dots,\textit{m}_l\) vertices in each parts while \(\mathsf{K}_{\textit{l}(\textit{m})}\) represents a balanced complete multipartite graph with \(\textit{l}\) parts and \(\textit{m}\) vertices in each part. A \(d-\) regular graph on \(\textit{n}\) vertices is represented as RG\((\textit{n}, d)\). SRG(\(\textit{n}\), \(d\), \(\lambda\), \(\mu\)) represents a strongly regular graph with \(\textit{n}\) vertices each having degree \(d\). In addition, \(\lambda\) denotes the number of vertices in the common neighbours of any two adjacent vertices, and \(\mu\) denotes the number of vertices in the common neighbours of any two nonadjacent vertices [8, 22]. Furthermore, \(C_{\textit{n}}\) stand for the cycle graphs with \(\textit{n}\) vertices and \(S_{\textit{n}}\) refers to a star graph where a central vertex is connected to \(\textit{n}\) other vertices.
Let \(\mathrm{R}\) be a finite commutative ring with a non-zero identity. In this section, we study the (induced) subgraphs of \(G(\mathrm{R})\), where \(\mathrm{R}\) is a finite local ring. If \(\mathrm{R}\) is a finite local ring, then it has a unique maximal ideal equal to the set of zero divisors, \( {Z}\) and \(|\mathrm{R}|= \textit{p}^r\), \(| {Z}|= \textit{p}^{s}\), where \(1\leq s<r\), see [12]. Since \( {Z}\) is closed under addition, \(G_{ {Z}}(\mathrm{R})\) is an edgeless induced subgraph of \(G(\mathrm{R})\). Consequently, we focus on analyzing the subgraph \(G_{R}(\mathrm{R})\). If \(\mathrm{R}= \mathbb{Z}_3\) or \(|\mathrm{R}|= 2^r\), \(r\ge 1\), with \(|\mathrm{R}/ {Z}|=2\), then \(G(\mathrm{R})\) is a complete bipartite graph (see [19, Theorem 2.7]). In these cases, \(G_{R}(\mathrm{R})\) is also an edgeless graph. Thus, the study reduces to the case when \(|\mathrm{R}|= \textit{p}^{r}\), \(r\ge 1\), and \(p\) is an odd prime. Note that the vertex set of \(G_{R}(\mathrm{R})\) is the disjoint union of cosets \(a_i+ {Z}\), where \(a_i\in Reg(\mathrm{R})\) and \(|a_i+ {Z}|=\textit{p}^{s}\).
Theorem 2.1. Let \(\mathrm{R}\) be a finite local ring with \(|\mathrm{R}|= \textit{p}^{r}\), \(r\ge 1\), and \(p\) is an odd prime. Then \(G_{R}(\mathrm{R})\) is a regular graph.
Proof. Let \(\mathrm{R}\) be a finite local ring, then \(\mathrm{R}/ {Z}\) is a field of characteristic \(\textit{p}\). Let \(a_i\in Reg(\mathrm{R})\), for any vertex in the coset \(a_i+ {Z}\), its degree is the sum of edges within its coset \(a_i+ {Z}\) and the edges to vertices of other cosets. In the finite local ring, the sum of a unit and a zero divisor is a unit, therefore any two distinct vertices \(a_i+\textit{k}_1\) and \(a_i+\textit{k}_2\) are adjacent as \(2a_i+\textit{k}_1+\textit{k}_2\in {U}\). Note that \(2\in {U}\) as \(\textit{p}\) is an odd prime. Therefore, the coset \(a_i+ {Z}\) is a clique of size \(\textit{p}^s\). Thus, the degree of every vertex within the coset is \(\textit{p}^s-1\). Also a vertex in \(a_i+ {Z}\) is adjacent to all vertices of the coset \(a_j+ {Z}\) unless \(a_j+ {Z}= -a_i+ {Z}\). Since there are \(\textit{p}^{r-s}-1\) unit cosets, therefore any vertex of \(a_i+ {Z}\) is adjacent to the vertices of remaining \((\textit{p}^{r-s}-3)\) costes (excluding the coset \(a_i+ {Z}\) and \(-a_i+ {Z}\)). This adds \((\textit{p}^{r-s}-3)\textit{p}^s\) more degree. Therefore, the total degree is \(\textit{p}^{r}-2\textit{p}^{s}-1\). Hence \(G_{R}(\mathrm{R})\) is a \(d\)-regular graph, where \(d =\textit{p}^{r}-2\textit{p}^{s}-1\). ◻
Example 2.2. For \(\mathrm{R}= \mathbb{Z}_{25}\), \( {Z}=\{0, 5, 10, 15, 20\}\) and \( {U}=\{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13,\\ 14, 16, 17, 18, 19, 21, 22, 23, 24\}\). Figure 1 shows that each vertex of the unit coset \(1+ {Z}\) is not connected to any vertex of the unit coset \(4+ {Z}\). Also, no vertex of the unit coset \(2+ {Z}\) is connected to any vertex of the unit coset \(3+ {Z}\). In Figure 1, dark line means that each vertex of a coset is adjacent to every vertex of the corresponding coset. In addition, each unit coset forms a clique of size \(5\). Thus, the degree of every vertex in \(G_{\mathrm{R}}(\mathbb{Z}_{25})\) is equal to \(\textit{p}^{r}-2\textit{p}^{s}-1=14\).
Corollary 2.3. Let \(\mathrm{R}\) be a finite local ring of order \(\textit{p}^{r}\), where \(\textit{p}\) is an odd prime and \(| {Z}|= \textit{p}^{s}\). The total number of edges in \(G(\mathrm{R})\) is \(E[G(\mathrm{R})]= \frac{(\textit{p}^{r}-1)(\textit{p}^{r}-\textit{p}^{s})}{2}\).
Proof. If \(\mathrm{R}\) is a finite local ring, then \( {Z}\) contains all the nilpotent elements of \(\mathrm{R}\). Since the sum of a nilpotent element and a unit element is always a unit in \(\mathrm{R}\), all the vertices of \( {Z}\) are adjacent to \(Reg(\mathrm{R})\). Therefore, there are \(\textit{p}^{s}(\textit{p}^{r}-\textit{p}^{s})\) edges whose one end point is in \( {Z}\) and the other is in \(Reg(\mathrm{R})\). Also, by Theorem 2.1, \(G_{R}(\mathrm{R})\) is a regular graph, and hence the number of edges in \(G_{R}(\mathrm{R})\) are \(\frac{(\textit{p}^{r}-\textit{p}^{s})(\textit{p}^{r}-2\textit{p}^{s}-1)}{2}\). Adding all the edges, we get the desired result. ◻
In particular, for \(\mathrm{R}= \mathbb{Z}_{\textit{p}^{r}}\), where \(\textit{p}\) is an odd prime, the total number of edges in \(G(\mathrm{R})\) is \(\frac{(\textit{p}^{r}-1)(\textit{p}^{r}-\textit{p}^{r-1})}{2}\).
Corollary 2.4. Let \(\mathrm{R}\) be a finite local ring of order \(\textit{p}^{r}\), where \(p\) is an odd prime, then diam\((G(\mathrm{R}))=2\).
Proof. It suffices to show that the distance between any two vertices in \(G(\mathrm{R})\) is at most \(2\). First let \(z_1, z_2\in {Z}\). Since \(G_Z(\mathrm{R})\) is an edgeless graph, so \(d(z_1, z_2)\geq 1\). Also every vertex of \( {Z}\) is adjacent to every vertex of \(Reg(\mathrm{R})\). Pick any \(a_i\in Reg(\mathrm{R})\), then there is a path \(z_1-a_i-z_2\) connecting \(z_1\) and \(z_2\), and hence \(d(z_1,z_2)=2\). Now, let \(a_i, a_j\in Reg(\mathrm{R})\), as in the proof of Theorem 2.1, \(d(a_i,a_j)=1\), except \(a_j=-a_i\). In that case, pick any \(z\in {Z}\), then \(a_i-z-a_j\) is a path joining \(a_i\) and \(a_j\), and hence \(d(a_i,a_j)=2\). Furthermore, for any \(z\in {Z}\) and \(a_i\in Reg(\mathrm{R})\), \(d(z,a_i)=1\). Thus, the maximum distance between any two vertices of \(G(\mathrm{R})\) is \(2\). Hence diam\((G(\mathrm{R}))=2\). ◻
Corollary 2.5. Let \(\mathrm{R}\) be a finite local ring of order \(\textit{p}^{r}>3\), where \(\textit{p}\) is an odd prime. Then, \(girth(G(\mathrm{R}))=3\).
Proof. Note that each coset of the form \(a_i+ {Z}\subset Reg(\mathrm{R})\) is a clique. Thus, whenever \(|a_i+ {Z}|\geq 3\), there exists a \(3\)-cycle. Further, if \(|a_i+ {Z}|\leq 2\), for \(a_{1}, a_{2}\in Reg(\mathrm{R})\), pick any \(z\in {Z}\), such that \(a_{1}- z- a_{2}- a_{1}\) form a \(3\)-cycle. Thus, \(girth(G(\mathrm{R}))=3\). ◻
Corollary 2.6. Let \(\mathrm{R}=\mathbb{Z}_{\textit{p}^{r}}\), where \(\textit{p}\) is an odd prime, then \(G(\mathrm{R})\) has an edge disjoint decomposition into a \(\left(\textit{p}^{r}-2\textit{p}^{r-1}-1\right)\)– regular graph \(G_{R}(\mathrm{R})\) with \(\textit{p}^{r-1}(\textit{p}-1)\) and a complete bipartite graph \(\mathsf{K}_{\textit{p}^{r-1},\:\textit{p}^{r-1}(\textit{p}-1)}\).
Proof. From Theorem 2.1, there exists an edge disjoint \(d-\)regular induced subgraph \(G_{R}(\mathrm{R})\) consisting of the unit set of \(\mathrm{R}\), where \(d=\textit{p}^{r}-2\textit{p}^{r-1}-1\). Therefore, the rest of the adjacency lies between the zero divisors and unit elements. Since each vertex of \( {Z}\) is adjacent to every vertex of \(Reg(\mathrm{R})\). So, there is an edge disjoint subgraph \(\mathsf{K}_{\textit{p}^{r-1},\: \textit{p}^{r-1}(\textit{p}-1)}\) in \(G(\mathrm{R})\). Hence, the result follows. ◻
Example 2.7. Let \(\mathrm{R}=\frac{\mathbb{Z}_{3}[x]}{(x^3)}\), \(|\mathrm{R}|= 3^3\). The set of regular elements contains elements of the form \(bx^2+cx+d\), where \(b, c\in\mathbb{Z}_{3}\) and \(d\in \{1,2\}\). Divide the elements of \(G_{R}(\mathrm{R})\) as \(V_{i}=\{i+cx+bx^2\mid b, c\in \mathbb{Z}_3\}\) for \(i=1,2\) with \(|V_{i}|=9\). It is evident that no vertex from \(V_1\) is adjacent to any vertex of \(V_2\). Also, the sum of any two vertices of \(V_1\) or \(V_2\) is a unit. Hence \(V_1\) and \(V_2\) form complete induced subgraphs of \(G_{R}(\mathrm{R})\) and \(G(\mathrm{R})\).
Theorem 2.8. Let \(\mathrm{R}\) be a finite local ring with \(|\mathrm{R}|= \textit{p}^{r}\), \(r\ge 1\) and \(\textit{p}\) is an odd prime. Then \(G(\mathrm{R})\) has an edge disjoint decomposition into a subgraph isomorphic to SRG\((\textit{n},d,\lambda,\mu)\) where \(\textit{n}= \textit{p}^r-\textit{p}^s, d= \textit{p}^r-3\textit{p}^s, \lambda= \textit{p}^r-5\textit{p}^s\) and \(\mu= \textit{p}^r-3\textit{p}^s\), \((\textit{p}^{r-s}-1)\) subgraphs isomorphic to \(\mathsf{K}_{\textit{p}^{s}, \textit{p}^{s}}\), and \((\textit{p}^{r-s}-1)\) subgraphs isomorphic to \(\mathsf{K}_{\textit{p}^{s}}\), i.e. \(G(\mathrm{R})\) has a \(\{(\textit{p}^{r-s}-1)\mathsf{K}_{\textit{p}^{s}, \textit{p}^{s}}, (\textit{p}^{r-s}-1) \mathsf{K}_{\textit{p}^{s}}, \text{SRG}(\textit{n}, d, \lambda, \mu)\}\)-decomposition.
Proof. Let \(\mathrm{R}\) be a finite local ring, then \(\mathrm{R}/ {Z}\) is a field with \(\textit{p}^{r-s}\) elements. Note that the elements of \(\mathrm{R}/ {Z}\) partition the vertex set of \(G(\mathrm{R})\) into the cosets \( {Z}\) and \(a_i+ {Z}\), where \(a_i\in Reg(\mathrm{R})\). This decomposition of \(G(\mathrm{R})\) is based on the adjacency between vertices that lie in the same coset and the adjacency between vertices that lie in different cosets. Clearly, the vertex set \( {Z}\) induces an edgeless subgraph of \(G(\mathrm{R})\). Also every vertex of \( {Z}\) is adjacent to each vertex of all the cosets \(a_i+ {Z}\), \(a_i\in Reg(\mathrm{R})\), as the sum of a zero divisor and a unit is always a unit in a finite local ring. Thus, corresponding to \((\textit{p}^{r-s}-1)\) unit cosets, there exist \((\textit{p}^{r-s}-1)\) edge disjoint subgraphs of \(G(\mathrm{R})\) isomorphic to \(\mathsf{K}_{\textit{p}^{s}, \textit{p}^{s}}\). Furthermore, each unit coset \(a_i+ {Z}\) is a clique of size \(\textit{p}^s\), see Theorem 2.1. Therefore, there are \((\textit{p}^{r-s}-1)\) edge disjoint subgraphs of \(G(\mathrm{R})\) isomorphic to \(\mathsf{K}_{\textit{p}^{s}}\). Now the remaining adjacencies are between vertices of disjoint unit cosets. This gives, a \((\textit{p}^r-3\textit{p}^s)\)-regular multipartite graph, as all the vertices of two distinct cosets \(a_i+ {Z}\) and \(a_j+ {Z}\) are adjacent unless \(a_j+ {Z}= -a_i+ {Z}\).
Moreover, in this regular multipartite graph, take two adjacent vertices say \(a_i+z_1\in a_i+ {Z}\) and \(a_j+z_1\in a_j+ {Z}\). The neighborhood set of \(a_i+z_1\in a_i+ {Z}\), contains all the vertices of costes \(a_k+ {Z}\), where \(a_k\neq -a_i\). Similarly, the neighborhood set of \(a_j+z_1\in a_j+ {Z}\), contains all the vertices of costes \(a_k+ {Z}\), where \(a_k\neq -a_j\). Thus, the common set of neighborhood of \(a_i+z_1\in a_i+ {Z}\) and \(a_j+z_1\in a_j+ {Z}\) does not contain the vertices of the cosets \(a_i+ {Z}, a_j+ {Z}, -a_i+ {Z}\) and \(-a_j+ {Z}\). Therefore, any two adjacent vertices are adjacent to \(\lambda= \textit{p}^r-5\textit{p}^s\) vertices. Similarly, pick any two non adjacent vertices say \(a_i+z_1\in a_i+ {Z}\) and \(-a_i+z_1\in -a_i+ {Z}\). Clearly, the common set of neighborhood of \(a_i+z_1\in a_i+ {Z}\) and \(-a_i+z_1\in -a_i+ {Z}\) does not contains the vertices which belongs to cosets itself i.e \(a_i+ {Z}\) and \(-a_i+ {Z}\). Thus, any two nonadjacent vertices are adjacent to \(\mu= \textit{p}^r-3\textit{p}^s\) vertices. Hence this graph is a strongly regular graph i.e. SRG\((\textit{n},d,\lambda,\mu)\) with \(\textit{n}= \textit{p}^r-\textit{p}^s, d= \textit{p}^r-3\textit{p}^s, \lambda= \textit{p}^r-5\textit{p}^s\) and \(\mu= \textit{p}^r-3\textit{p}^s\). This provides the desired decomposition. ◻
Example 2.9. Let \(\mathrm{R}= \mathbb{Z}_{5^2}\), \(|\mathrm{R}|= 5^2\), and \(| {Z}|= 5\). The vertex set of \(G(\mathrm{R})\) follows a partition into \(V_0=\{0,5,10,15,20\}, V_1=\{1,6,11,16,21\}, V_2=\{2,7,12,17,22\},\) \(V_3=\{3,8,13,18,23\}, V_4=\{4,9,14,19,24\}\). Clearly, every vertex in \(V_0\) is adjacent to each vertex of \(V_1, V_2, V_3, V_4\). So, there exists four edge disjoint subgraphs \(\mathsf{K}_{5,5}\) with partitions \((V_0, V_1)\), \((V_0,V_2)\), \((V_0,V_3)\), and \((V_0, V_4)\). Since 2 is a unit in \(\mathbb{Z}_{5^2}\), sum of any two distinct vertices of \(V_i\) is a unit in \(\mathrm{R}\) and hence forms a complete graph \(\mathsf{K}_5\). This gives \(4\)-copies of edge disjoint subgraph \(\mathsf{K}_{5}\) corresponding to each \(V_i\), \(i=1,2,3,4\). The remaining adjacency lies only between the vertices of distinct \(V_{i}\), \(1\leq a_i\leq 4\). Note that each vertex of \(V_1\) is adjacent to every vertex of \(V_3\) and each vertex of \(V_2\) is adjacent to every vertex of \(V_4\). Furthermore, no vertex of \(V_1\) is adjacent to any vertex of \(V_4\), and no vertex of \(V_2\) is adjacent to any vertex of \(V_3\). This gives a strongly regular graph with vertex set \(V_1 \cup V_2 \cup V_3 \cup V_4\), that is, SRG\((\textit{n},d,\lambda,\mu)\), with \(\textit{n}= 20, d= 10, \lambda= 0\), and \(\mu= 10\).
In graph theory, certain special types of graphs have been decomposed in a specific way. We begin by mentioning some key results related to the decomposition of graphs into cycles and stars.
Theorem 3.1. [23, Theorem 2.2] A complete bipartite graph \(\mathsf{K}_{\textit{m},\textit{n}}\) has \(\textit{m}\textit{n}/\textit{k}\) copies of edge disjoint \(S_{\textit{k}}\), if one of the following holds
1. \(\textit{m}\equiv 0 \pmod{\textit{k}}\), when \(\textit{n}<\textit{k}\),
2. \(\textit{n}\equiv0 \pmod{\textit{k}}\), when \(\textit{m}<\textit{k}\),
3. \(\textit{m}\textit{n}\equiv0\pmod{\textit{k}}\), when \(\textit{m},\textit{n}\geq \textit{k}\).
Theorem 3.2. [4, Theorem 2.1] If \(\textit{m}\) and \(\textit{n}\) are positive integers with \(3\leq \textit{m}\leq \textit{n}\), the complete graph \(\mathsf{K}_{\textit{n}}\) has a decomposition into \(C_{\textit{k}}\) only if the total number of edges is divisible by \(\textit{m}\).
Theorem 3.3. [20, Theorem B] A complete bipartite graph \(\mathsf{K}_{\textit{m},\textit{n}}\), with \(\textit{m},\textit{n}\geq \textit{k}\), has a decomposition into a \(2\textit{k}\)– cycle, if the degree of each vertex is even or \(\textit{m}\) and \(\textit{n}\) are even and the total number of edges \(\textit{m}\textit{n}\) is divisible by \(2\textit{k}\).
Using these results, utilizing the decomposition of \(G(\mathbb{Z}_{\textit{p}^{r}})\) into a complete bipartite graph and (induced) subgraph \(G_{R}(\mathrm{R})\), we decompose \(G(\mathbb{Z}_{\textit{p}^{r}})\) into cycle and star graphs. For \(\textit{p}=2\), \(G(\mathbb{Z}_{2^{r}})\) is realized as a complete bipartite graph. Thus, from Theorem 3.3, \(G(\mathbb{Z}_{2^{r}})\) has a decomposition into \(C_{4}\), with \(k=2\) and \(m=n=2^{r-1}\). Therefore, we focus only on analyzing the decomposition of \(G(\mathbb{Z}_{\textit{p}^{r}})\), with \(\textit{p}\) being an odd prime. In the following results we find a star and \(C_{4}\) decomposition in \(G(\mathrm{R})\), where \(\mathrm{R}= \mathbb{Z}_{\textit{p}}\).
Theorem 3.4. Let \(\mathrm{R}=\mathbb{Z}_{\textit{p}}\), then \(G(\mathrm{R})\) has a \(\{S_{\textit{p}-1}, \beta C_{4}\}\)– decomposition, where \(\beta=(\textit{p}-1)(\textit{p}-3)/8\).
Proof. According to Corollary 2.6, \(G(\mathrm{R})\) has a decomposition into \(\left(\textit{p}-3\right)\)– regular graph \(G_{R}(\mathrm{R})\) with \((\textit{p}-1)\) vertices and a complete bipartite graph \(\mathsf{K}_{1,\:\textit{p}-1}\) (i.e., \(S_{\textit{p}-1}\)). Now, divide the vertex set of \(G_{R}(\mathrm{R})\) into \((\textit{p}-1)/2\) pairs \((a,\textit{p}-a)\), where \(a = 1,2,\dots, (\textit{p}-1)/2\). Clearly, there is no edge between \(a\) and \((\textit{p}-a)\) however, they are adjacent to each vertex of the other pairs. Thus, \(G_{R}(\mathrm{R})\) is realized as \(\mathsf{K}_{\textit{l}(m)}\), where \(\textit{l}= (\textit{p}-1)/2\) and \(m=2\), that is \(\mathsf{K}_{\textit{l}(2)}\). To find \(C_4\) in \(G_{R}(\mathrm{R})\), \(\mathsf{K}_{\textit{l}(2)}\) is decomposed into a complete bipartite graph \(\mathsf{K}_{2,2}\) (which gives a \(4\)-cycle). For example, take pairs \((1, \textit{p}-1)\) and \((2, \textit{p}-2)\), then \(1-2-(\textit{p}-1)-(\textit{p}-2)-1\) is a cycle of length \(4\). Thus, the number of such \(C_4\) is equal to the number of edge-disjoint \(\mathsf{K}_{2,2}\) in \(\mathsf{K}_{\textit{l}(2)}\). Note that there are \((\textit{p}-3)/2\) \(\mathsf{K}_{2,2}\) which contains the pair \((1, \textit{p}-1)\), \((\textit{p}-5)/2\) edge disjoint \(\mathsf{K}_{2,2}\) containing the pair \((2, \textit{p}-2)\), and so on. Hence the total number of edge disjoint \(\mathsf{K}_{2,2}\) in \(G_{R}(\mathrm{R})\) is, \[\frac{\textit{p}-3}{2}+\frac{\textit{p}-5}{2}+\dots+ 2+1= \frac{(\textit{p}-1)(\textit{p}-3)}{8}.\]
Thus \(G(\mathrm{R})\) has an edge disjoint subgraphs \(S_{\textit{p}-1}\) and \((\textit{p}-1)(\textit{p}-3)/8\) copies of \(C_4\). ◻
For \(\textit{p}=3\), \(G(\mathbb{Z}_{\textit{p}^{r}})\) contains a particular class of subgraphs, such as complete bipartite graphs and complete graphs, which makes it easy to decompose into cycle and star graphs. Therefore, in the following theorem, we examine the decomposition of \(G(\mathbb{Z}_{3^{r}})\) into star and cycle graphs that contain the same number of edges.
Theorem 3.5. Let \(\mathrm{R}=\mathbb{Z}_{\textit{p}^r}\), where \(\textit{p}=3\) and \(r\geq 2\), then \(G(\mathrm{R})\) has a \(\{\alpha S_{3}, \beta C_{3} \}\)– decomposition, where \(\alpha= \frac{\textit{p}^{2(r-1)}(\textit{p}-1)}{3}\) and \(\beta=\frac{\textit{p}^{r-1}(\textit{p}^{r-1}-1)}{3}\).
Proof. From the Corollary 2.6, \(G(\mathrm{R})\) has an edge disjoint decomposition into a \(\left(\textit{p}^{r-1}-1\right)\)– regular graph \(G_{R}(\mathrm{R})\) with \(\textit{p}^{r-1}(\textit{p}-1)\) vertices and a complete bipartite graph \(\mathsf{K}_{\textit{p}^{r-1},\:\textit{p}^{r-1}(\textit{p}-1)}\) with partition \( {Z}\) and \( {U}\). In \(\mathsf{K}_{\textit{p}^{r-1},\:\textit{p}^{r-1}(\textit{p}-1)}\), the total number of edges is \(\textit{p}^{2(r-1)}(\textit{p}-1)\), which is divisible by \(3\). Thus, from Theorem 3.1, there exist \(\textit{p}^{2(r-1)}(\textit{p}-1)/3\) edge disjoint \(S_3\) in \(\mathsf{K}_{\textit{p}^{r-1},\:\textit{p}^{r-1}(\textit{p}-1)}\).
Since \(|\mathbb{Z}_{3^r}/ {Z}|=3\), the vertex set of \(G_{R}(\mathrm{R})\) is a disjoint union of cosets, each consisting of \(3^{r-1}\) units. As in Theorem 2.8, each coset forms a complete graph. In addition, each vertex of coset \(a_i+ {Z}\) is adjacent to every vertex of coset \(a_j+ {Z}\) only if \(a_j+ {Z}= -a_i+ {Z}\). Thus, no vertex of unit coset \(1+ {Z}\) is adjacent to any vertex of coset \(2+ {Z}\). Hence, \(G_{R}(\mathrm{R})\) is the union of two disjoint complete induced subgraphs \(\mathsf{K}_{p^{r-1}}\). Note that, for \(\mathsf{K}_{\textit{p}^{r-1}}\), the total number of vertices is odd and \(3\mid \textit{p}^{r-1}(\textit{p}^{r-1}-1)/2\), for \(\textit{p}=3\) and \(r\geq 2\). Therefore, by Theorem 3.2, there exists a \(C_3\) decomposition in \(\mathsf{K}_{\textit{p}^{r-1}}\). Since the degree of a vertex \(a_i\) is \((\textit{p}^{r-1}-1)\) or the number of edges incident to \(a_i\) is \((\textit{p}^{r-1}-1)\) and a \(3\)-cycle consumes \(2\)-degree of a vertex, thus a vertex appears in \((\textit{p}^{r-1}-1)/2\)-edge disjoint \(C_3\). This implies that there are \(\frac{\textit{p}^{r-1}}{3}\frac{\textit{p}^{r-1}-1}{2}= \frac{\textit{p}^{r-1}(\textit{p}^{r-1}-1)}{6}\) edge disjoint \(C_3\) in \(\mathsf{K}_{\textit{p}^{r-1}}\) and hence \(\textit{p}^{r-1}(\textit{p}^{r-1}-1)/3\)– edge disjoint \(C_3\) in \(G(\mathrm{R})\). ◻
Lemma 3.6. Let \(\mathrm{R}=\mathbb{Z}_{\textit{p}^2}\), where \(\textit{p}\equiv 1\pmod{4}\), then \(G(\mathrm{R})\) has a \(\{\alpha C_{\textit{p}}, \beta S_4, \gamma C_{4}\}\)– decomposition, where \(\alpha= \frac{(\textit{p}-1)^2}{2}\), \(\beta= \frac{\textit{p}^{2}(\textit{p}-1)}{4}\), and \(\gamma=\frac{\textit{p}^{2}(\textit{p}-1)(\textit{p}-3)}{8}\).
Proof. From Corollary 2.6, \(G(\mathrm{R})\) has an edge disjoint decomposition into a \((\textit{p}^{2}-2\textit{p}-1)\)– regular graph \(G_{R}(\mathrm{R})\) with \(\textit{p}(\textit{p}-1)\) vertices and a complete bipartite graph \(\mathsf{K}_{\textit{p},\:\textit{p}(\textit{p}-1)}\) with partition \( {Z}\) and \( {U}\). In \(\mathsf{K}_{\textit{p},\:\textit{p}(\textit{p}-1)}\), the total number of edges is \(\textit{p}^{2}(\textit{p}-1)\), which is divisible by \(4\), for \(\textit{p}\equiv 1\pmod{4}\). Thus, from Theorem 3.1, there exist \(\textit{p}^{2}(\textit{p}-1)/4\)-copies of \(S_{4}\) in \(\mathsf{K}_{\textit{p},\:\textit{p}(\textit{p}-1)}\). Since \(|\mathbb{Z}_{\textit{p}^2}/ {Z}|=\textit{p}\), the vertex set of \(G_{R}(\mathrm{R})\) is a disjoint union of cosets, each consisting of \(\textit{p}\) units. As in Theorem 2.8, each coset forms a complete graph, and the number of unit cosets is \(\textit{p}-1\). Thus, there exists \((\textit{p}-1)-\)copies of \(\mathsf{K}_{\textit{p}}\). By Theorem 3.2, there exists a \(C_{\textit{p}}\)– decomposition in \(\mathsf{K}_{\textit{p}}\). Since the degree of a vertex \(a_i\) is \((\textit{p}-1)\) and a \(\textit{p}\)-cycle exhausts two degrees of a vertex, thus a vertex \(a_i\) appears in \((\textit{p}-1)/2\) edge disjoint \(\textit{p}-\) cycles. This implies that there are \(\frac{\textit{p}}{\textit{p}}\frac{(\textit{p}-1)}{2}= \frac{(\textit{p}-1)}{2}\) edge disjoint \(C_{\textit{p}}\) in \(\mathsf{K}_{\textit{p}}\) and hence for \((\textit{p}-1)-\)copies of \(\mathsf{K}_{\textit{p}}\), there are \(((\textit{p}-1)^2/2)\)-edge disjoint \(C_{\textit{p}}\) in \(G_{R}(\mathrm{R})\). Note that each vertex of coset \(a_i+ {Z}\) is adjacent to every vertex of coset \(a_j+ {Z}\), except whenever \(a_i+a_j=\textit{p}\). Take one pair \((a_i, \textit{p}-a_i)\) and connect it with vertices of other cosets, it forms a \(\mathsf{K}_{\textit{l}(2)}\), where \(\textit{l}=(\textit{p}-1)/2\), see Theorem 3.4. Since there are \(\textit{p}\) vertices in each coset, taking the pair \((a_i, \textit{p}-a_i)\) and adjacent it with all vertices of other cosets, we have \(\textit{p}^{2}\)-copies of \(\mathsf{K}_{\textit{l}(2)}\). So, following the \(C_4\) decomposition in Theorem 3.4, we get \(\textit{p}^{2}(\textit{p}-1)(\textit{p}-3)/8\)-edge disjoint \(C_{4}\) from \(\textit{p}^{2}-\)copies of \(\mathsf{K}_{\textit{l}(2)}\). ◻
For \(\textit{p}\equiv 3\pmod{4}\), the total number of edges of \(\mathsf{K}_{\textit{p},\:\textit{p}(\textit{p}-1)}\), that is, \(\textit{p}^2(\textit{p}-1)\), leaves the reminder \(2\) on division by \(4\). In this case, the decomposition of complete bipartite graph \(\mathsf{K}_{\textit{p},\:\textit{p}(\textit{p}-1)}\) consists \(S_4\) and \(S_2\). Note that each vertex of \( {Z}\) is adjacent to \(\textit{p}(\textit{p}-1)\) vertices of \( {U}\). Since \(\textit{p}(\textit{p}-1)\equiv 2 \pmod{4}\), taking \(a\in {Z}\) as a central vertex and edges formed by taking disjoint vertices in \( {U}\), there are \((\textit{p}^2-\textit{p}-2)/4\) edge disjoint \(S_4\) and a \(S_2\). Corresponding to all the vertices of \( {Z}\), there are \(\textit{p}(\textit{p}^2-\textit{p}-2)/4\) edge disjoint \(S_4\) and \(\textit{p}\) edge disjoint \(S_2\) in \(\mathsf{K}_{\textit{p},\:\textit{p}(\textit{p}-1)}\). The decomposition of \(G_{R}(\mathrm{R})\) follows the same reasoning as presented in the preceding lemma.
Theorem 3.7. Let \(\mathrm{R}=\mathbb{Z}_{\textit{p}^{r}}\) where \(\textit{p}\equiv 1\pmod{4}\) and \(r\geq 2\), then \(G(\mathrm{R})\) has a \(\{\alpha C_{\textit{p}}, \beta S_4,\\ \gamma C_{4}\}\)– decomposition, where \(\alpha=\frac{\textit{p}^{r-2}(\textit{p}-1)(\textit{p}^{r-1}-1)}{2}\), \(\beta= \frac{\textit{p}^{2(r-1)}(\textit{p}-1)}{4}\), and \(\gamma=\frac{\textit{p}^{2(r-1)}(\textit{p}-1)(\textit{p}-3)}{8}\).
Proof. From Corollary 2.6, \(G(\mathrm{R})\) has an edge disjoint decomposition into a \((\textit{p}^{r}-2\textit{p}^{r-1}-1)\)– regular graph \(G_{R}(\mathrm{R})\) with \(\textit{p}^{r-1}(\textit{p}-1)\) vertices and a complete bipartite graph \(\mathsf{K}_{\textit{p}^{r-1},\: \textit{p}^{r-1}(\textit{p}-1)}\) with partition \( {Z}\) and \( {U}\). In \(\mathsf{K}_{\textit{p}^{r-1},\: \textit{p}^{r-1}(\textit{p}-1)}\), the total number of edges is \(\textit{p}^{2(r-1)}(\textit{p}-1)\), which is divisible by \(4\), for \(\textit{p}\equiv 1\pmod{4}\) and \(r\geq 2\). Thus, from Theorem 3.1, there are \(\textit{p}^{2(r-1)}(\textit{p}-1)/4\) edge disjoint \(S_{4}\) in \(\mathsf{K}_{\textit{p}^{r-1},\: \textit{p}^{r-1}(\textit{p}-1)}\). Since, \(|\mathbb{Z}_{\textit{p}^{r-1}}/ {Z}|=\textit{p}\) the vertex set of \(G_{R}(\mathrm{R})\) is a disjoint union of cosets each consisting of \(\textit{p}^{r-1}\) units. As in Theorem 2.8, each coset forms a complete subgraph. So, following the Lemma 3.6, for \((\textit{p}-1)\) copies of \(\mathsf{K}_{\textit{p}^{r-1}}\), there are \(\frac{\textit{p}^{r-1}(\textit{p}-1)(\textit{p}^{r-1}-1)}{2\textit{p}}= \frac{\textit{p}^{r-2}(\textit{p}-1)(\textit{p}^{r-1}-1)}{2}\) edge disjoint \(C_{\textit{p}}\) in \(G_{R}(\mathrm{R})\). As there are \(\textit{p}^{r-1}\) vertices in each coset \(a_i+ {Z}\) and each vertex of one coset is adjacent to every vertex of the other coset \(a_j+ {Z}\) unless \(a_j=-a_i\). By, taking any pair \((a_i,\textit{p}-a_i)\) that is adjacent to every vertices of another cosets, we obtain \(\textit{p}^{2(r-1)}\)-copies of \(\mathsf{K}_{\textit{l}(2)}\), where \(\textit{l}=(\textit{p}-1)/2\). So, following Theorem 3.4, we get \(\textit{p}^{2(r-1)}(\textit{p}-1)(\textit{p}-3)/8\) edge disjoint \(C_{4}\) in \(G_{R}(\mathrm{R})\). Hence the result. ◻
For \(\textit{p}\equiv 3\pmod{4}\), the total number of edges of \(\mathsf{K}_{\textit{p}^{r-1},\:\textit{p}^{r-1}(\textit{p}-1)}\), that is, \(\textit{p}^{2(r-1)}(\textit{p}-1)\) leaves the reminder \(2\) on division by \(4\). In this case, the decomposition of complete bipartite graph \(\mathsf{K}_{\textit{p}^{r-1},\:\textit{p}^{r-1}(\textit{p}-1)}\) consists \(S_4\) and \(S_2\) decomposition. Note that, each vertex of \( {Z}\) is adjacent to \(\textit{p}^{r-1}(\textit{p}-1)\) vertices of \( {U}\). Since, \(\textit{p}^{r-1}(\textit{p}-1)\equiv2\pmod{4}\), taking \(a\in {Z}\), as a central vertex and edges formed by taking disjoint vertices in \( {U}\), there exist \((\textit{p}^r-\textit{p}^{r-1}-2)/4\)-edge disjoint \(S_4\) and a \(S_2\). Corresponding to all the vertices of \( {Z}\), there exist \((\textit{p}^{(r-1)}(\textit{p}^r-\textit{p}^{r-1}-2))/4\)-edge disjoint \(S_4\) and \(\textit{p}^{r-1}\)-edge disjoint \(S_2\) in \(\mathsf{K}_{\textit{p}^{r-1},\:\textit{p}^{r-1}(\textit{p}-1)}\). Note that, the decomposition of \(G_{R}(\mathrm{R})\) follows the same reasoning as presented in the preceding Theorem.
In this section, we focus on the decomposition of \(G(\mathbb{Z}_{\textit{p}\textit{q}})\) into cycle and star graphs. In this case, \( {Z}\) is not an ideal, so there exists at least one pair of zero divisors such that their sum does not belong to the set of zero divisors, that is, \(z_1+ z_2\notin {Z}\) for some \(z_1, z_2\in {Z}\backslash\{0\}\). Therefore, \(G_{ {Z}\backslash\{0\}}(\mathrm{R})\) is not an edgeless graph.
For \(\mathrm{R}= \mathbb{Z}_{2\textit{p}}\) where \(\textit{p}\) is any odd prime, \(2\in {Z}\) and hence \(G(\mathrm{R})\) is a \((\textit{p}-1)\) regular graph [7, Proposition 2.4]. Also \(G(\mathrm{R})\) is realized as a bipartite graph, where each vertices has \(deg(v)=( \textit{p}-1)\) with \(|V_{1}|=|V_{2}|= \textit{p}\) ([19, Theorem 2.4]). Therefore, whenever \(\textit{p}\equiv1\pmod{4}\), \(G(\mathrm{R})\) has a \(\textit{p}(\textit{p}-1)/4\)– copies of \(S_{4}\). On the contrary, when \(\textit{p}\equiv3\pmod{4}\), \(G(\mathrm{R})\) has a decomposition into \(\{\alpha S_{4}, \beta S_{2}\}\), where \(\alpha =\textit{p}(\textit{p}-3)/4\) and \(\beta= \textit{p}\). Thus, in the subsequent theorem, we decompose \(G(\mathbb{Z}_{\textit{p}\textit{q}})\) into its subgraph, where both \(\textit{p}\) and \(\textit{q}\) are regarded as distinct odd primes.
Lemma 4.1. Let \(\mathrm{R}=\mathbb{Z}_{\textit{p}\textit{q}}\), with \(\textit{p}<\textit{q}\), then \(G(\mathrm{R})\) has an edge disjoint decomposition into a complete bipartite graph \(G_{ {Z}\backslash\{0\}}(\mathrm{R})\) realized as \(\mathsf{K}_{\textit{p}-1,\:\textit{q}-1}\), a bipartite graph with partitions \( {Z}\) and \( {U}\) and a \((\textit{p}\textit{q}-2\textit{p}-2\textit{q}+3)\)-regular graph \(G_{R}(\mathrm{R})\) with \((\textit{p}\textit{q}-\textit{p}-\textit{q}+1)\) vertices.
Proof. For \(G(\mathbb{Z}_{\textit{p}\textit{q}})\), \(| {U}|= \phi(\textit{p}\textit{q})= (\textit{p}-1)(\textit{q}-1)\) and \(| {Z}|= \textit{p}+\textit{q}-1\). Since \(2\in {U}\), from [7, Proposition 2.4], \(deg(\textit{x})= (\textit{p}-1)(\textit{q}-1)\), when \(\textit{x}\) belongs to \( {Z}\) and \(deg(\textit{y})= \textit{p}\textit{q}-\textit{p}-\textit{q}\), when \(\textit{y}\) belongs to \( {U}\). Consider \(V_{\textit{p}}=\{\textit{p}, 2\textit{p}, 3\textit{p},\dots, (\textit{q}-1)\textit{p}\}\) and \(V_{\textit{q}}=\{\textit{q}, 2\textit{q}, 3\textit{q}, \dots, (\textit{p}-1)\textit{q}\}\). Note that, for any \(x,y \in V_{\textit{p}}\), \(x+y\in V_{\textit{p}}\). Similarly, for any \(x,y \in V_{\textit{q}}\), \(x+y\in V_{\textit{q}}\). Clearly, \(V_{\textit{p}}\) and \(V_{\textit{q}}\) form a partition of \( {Z}\backslash\{0\}\). Note that \(gcd(a\textit{p}+b\textit{q}, \textit{p}\textit{q})=1\) whenever \(1\leq a\leq \textit{q}-1\) and \(1\leq b\leq \textit{p}-1\). Hence, for any \(\textit{x}_{i}\in V_{\textit{p}}\) and \(\textit{x}_{j}\in V_{\textit{q}}\), \(\textit{x}_{i}+\textit{x}_{j}\in {U}\). Thus, there exists an edge disjoint subgraph \(G_{ {Z}\backslash\{0\}}(\mathrm{R})\) realized as \(\mathsf{K}_{\textit{p}-1,\:\textit{q}-1}\).
Since \(G_{ {Z}\backslash\{0\}}(\mathrm{R})\) and \(G_{R}(\mathrm{R})\) are not disjoint subgraphs of \(G(\mathrm{R})\), there exists some connectivity between them. After removing the edges of \(G_{ {Z}\backslash\{0\}}(\mathrm{R})\), every vertex of \(V_{\textit{p}}\) is adjacent to \((\textit{p}-2)(\textit{q}-1)\) vertices of \(U\) and every vertex of \(V_{\textit{q}}\) is adjacent to \((\textit{p}-1)(\textit{q}-2)\) vertices of \(U\). Also \(0\) is adjacent to every vertex in \( {U}\). Thus, there exists an edge disjoint bipartite subgraph with partitions \( {Z}\) and \( {U}\) such that for any \(\textit{y}\in {U}\), \(deg(\textit{y})= \textit{p}+ \textit{q}-3\).
Since every vertex of \( {U}\) has degree \(| {U}|-1\) [7, Proposition 2.4], there are \((\textit{p}\textit{q}-2\textit{p}-2\textit{q}+3)\) more edges incident of every vertex after removing the edges of bipartite subgraph. This gives an edge disjoint \((\textit{p}\textit{q}-2\textit{p}-2\textit{q}+3)\) -regular subgraph \(G_{R}(\mathrm{R})\) with \((\textit{p}\textit{q}-\textit{p}-\textit{q}+1)\) vertices. Hence the result. ◻
Example 4.2. From Figure 3, \(G(15)\) has a \(\mathsf{K}_{2,4}\), a bipartite graph with partitions \( {Z}\) and \( {U}\) such that for each \(\textit{y}\in {U}\) degree is \(5\) and a \((8,2)-\)regular graph \(G_{R}(\mathrm{R})\).
Using the decomposition given in Lemma 4.1, we
can easily compute the total number of edges in the unit graph of \(\mathbb{Z}_{\textit{p}\textit{q}}\), note
that \(|E(\mathsf{K}_{\textit{p}-1,\:\textit{q}-1})|=(\textit{p}-1)(\textit{q}-1)\),
the total number of edges in the bipartite graph is \((\textit{p}-1)(\textit{q}-1)(\textit{p}+\textit{q}-3)\)
and \(|E(G_{R}(\mathrm{R}))|=
(\textit{p}\textit{q}-2\textit{p}-2\textit{q}+3)(\textit{p}-1)(\textit{q}-1)/
2\). Thus, the total number of edges in \(G(\mathrm{R})\) are \((\textit{p}-1)(\textit{q}-1)\big(\frac{\textit{p}\textit{q}-1}{2}\big)\).
By utilizing the decomposition of \(G(\mathbb{Z}_{\textit{p}\textit{q}})\) into
a complete bipartite graph, a bipartite graph, and a regular graph, in
the subsequent results we study the cycle and star decomposition in
\(G(\mathbb{Z}_{\textit{p}\textit{q}})\).
Lemma 4.3. Let \(\mathrm{R}=\mathbb{Z}_{3\textit{p}}\), where \(\textit{p}>3\) and \(\textit{p}\equiv1\pmod{4}\), then \(G(\mathrm{R})\) has a \(\{\alpha C_{4}, \beta S_{4}, \\ \gamma S_{2}\}\)-decomposition, where \(\alpha=\frac{(\textit{p}-1)}{2}\), \(\beta= \frac{(\textit{p}-1)(2\textit{p}-1)}{4}\), and \(\gamma=\frac{(\textit{p}-1)(\textit{p}-3)}{2}\).
Proof. According to Lemma 4.1, \(G(\mathrm{R})\) has an edge disjoint decomposition into a complete bipartite graph \(G_{ {Z}\backslash\{0\}}(\mathrm{R})\) realized, as \(\mathsf{K}_{2,\:\textit{p}-1}\), a bipartite graph with partitions \( {Z}\) and \( {U}\), and a \((\textit{p}-3)\)-regular graph \(G_{R}(\mathrm{R})\) with \(2(\textit{p}-1)\) vertices.
In \(\mathsf{K}_{2,\:\textit{p}-1}\), the degree of each vertex is even and the total number of edges is divisible by \(4\), as \(\textit{p}\equiv1\pmod{4}\). Thus, from Theorem 3.3, there exist \(2(\textit{p}-1)/4\) edge disjoint copies of \(C_{4}\) in \(\mathsf{K}_{2,\:\textit{p}-1}\). In the bipartite graph with partitions \( {Z}\) and \( {U}\), \(0\) is connected to every vertex of \( {U}\). So, decompose this bipartite graph into \(\mathsf{K}_{1,\:2 (\textit{p}-1)}\) and a bipartite graph with partitions \( {Z}\backslash\{0\}\) and \( {U}\). Clearly, in \(\mathsf{K}_{1,\:2 (\textit{p}-1)}\), \(4\mid 2 (\textit{p}-1)\), as \(\textit{p}\equiv1\pmod{4}\). Thus, from Theorem 3.1, there exist \((\textit{p}-1)/2\) edge disjoint copies of \(S_{4}\). Further, in the bipartite graph with partitions \( {Z}\) and \( {U}\), \(deg(\textit{y})=\textit{p}\) for all \(\textit{y}\in {U}\), see Lemma 4.1. After removing edges of \(\mathsf{K}_{1,\:2 (\textit{p}-1)}\), in the bipartite graph with partitions \( {Z}\backslash\{0\}\) and \( {U}\), \(deg(\textit{y})= \textit{p}-1\), for all \(\textit{y}\in {U}\). Clearly, the number of edges to a vertex \(\textit{y}\in {U}\), is a multiple of \(4\) to the vertices \(\textit{x} \in {Z}\backslash\{0\}\), as \(\textit{p}-1\equiv 0\pmod{4}\). Thus, there correspond \((\textit{p}-1)/4\) edge disjoint copies of \(S_{4}\), for every \(\textit{y}\in {U}\) and hence for \(2(\textit{p}-1)\) vertices in \( {U}\), there exist \((\textit{p}-1)^2/2\) edge disjoint copies of \(S_{4}\) in the bipartite graph with partitions \( {Z}\backslash\{0\}\) and \( {U}\). Combining the total number of \(S_4\), there exist \((\textit{p}-1)(2\textit{p}-1)/4\) edge disjoint copies of \(S_{4}\) in the bipartite graph with partitions \( {Z}\) and \( {U}\).
Now for the \((\textit{p}-3)\)-regular graph \(G_{R}(\mathrm{R})\), the total number of edges are \((\textit{p}-1)(\textit{p}-3)\), which is even and always divisible by \(2\). Hence, for \(2(\textit{p}-1)\)-vertices, there exist \((\textit{p}-1)(\textit{p}-3)/2-\) edge disjoint copies of \(S_{2}\) in \(G_{R}(\mathrm{R})\). ◻
Lemma 4.4. Let \(\mathrm{R}=\mathbb{Z}_{5\textit{p}}\), where \(\textit{p}>5\) and \(\textit{p}\equiv3\pmod{4}\), then \(G(\mathrm{R})\) has a \(\{\alpha C_{4}, \beta S_{4}, \\ \gamma S_{2}\}\)-decomposition, where \(\alpha=(\textit{p}-1)\), \(\beta= (\textit{p}-1)(\textit{p}+2)\), and \(\gamma=(\textit{p}-1)(3\textit{p}-7)\).
Proof. By Lemma 4.1, \(G(\mathrm{R})\) has an edge disjoint decomposition into a complete bipartite graph \(G_{ {Z}\backslash\{0\}}(\mathrm{R})\) realized as \(\mathsf{K}_{4,\:\textit{p}-1}\), a bipartite graph with partition \( {Z}\) and \( {U}\) and a \((3\textit{p}-7)\)-regular graph \(G_{R}(\mathrm{R})\) with \(4(\textit{p}-1)\) vertices. In \(\mathsf{K}_{4,\:\textit{p}-1}\), the total number of edges is \(4(\textit{p}-1)\), which is divisible by \(4\). Consequently, from Theorem 3.3, there exist \((\textit{p}-1)\) edge disjoint copies of \(C_{4}\) in \(\mathsf{K}_{4,\:\textit{p}-1}\).
In the bipartite graph with partitions \( {Z}\) and \( {U}\), \(0\) is connected to every vertex of \( {U}\). Now, decompose this bipartite graph into \(\mathsf{K}_{1,\:4 (\textit{p}-1)}\) and a bipartite graph with partitions \( {Z}\backslash\{0\}\) and \( {U}\). Clearly, in \(\mathsf{K}_{1,\:4 (\textit{p}-1)}\), \(4\mid 4(\textit{p}-1)\). Thus, from Theorem 3.1, there exist \((\textit{p}-1)\) edge disjoint copies of \(S_{4}\) in \(\mathsf{K}_{1,\:4 (\textit{p}-1)}\). After removing the edges of \(\mathsf{K}_{1,\:4 (\textit{p}-1)}\), in the bipartite graph with partitions \( {Z}\backslash\{0\}\) and \( {U}\), \(deg(\textit{y})= \textit{p}+1\) for all \(\textit{y}\in {U}\). Note that, \(\textit{p}\equiv3 \pmod{4}\), implies \(\textit{p}+1\equiv0 \pmod{4}\). Therefore, the adjacency to a vertex \(\textit{y}\in U\) is a multiple of \(4\) to all the vertices \(\textit{x}\in {Z}\backslash\{0\}\). Thus, there correspond \((\textit{p}+1)/4\) edge disjoint copies of \(S_{4}\), for each \(\textit{y}\in {U}\). Thus, for \(4(\textit{p}-1)\) vertices of \( {U}\), there exist \((\textit{p}^2-1)\) edge disjoint copies of \(S_{4}\) in the bipartite graph with partitions \( {Z}\backslash\{0\}\) and \( {U}\). Combining both numbers, there exist \((\textit{p}-1)(\textit{p}+2)\) edge disjoint copies of \(S_4\) in the bipartite graph with partitions \( {Z}\) and \( {U}\).
Now for the \((3\textit{p}-7)\)-regular graph \(G_{R}(\mathrm{R})\), the total number of edges is \(4(\textit{p}-1)(3\textit{p}-7)/2\), which is even and always divisible by \(2\). Hence, for \(4(\textit{p}-1)\)-vertices, there exist \((\textit{p}-1)(3\textit{p}-7)\) edge disjoint copies of \(S_{2}\) in \(G_{R}(\mathrm{R})\). Hence the result. ◻
Theorem 4.5. Let \(\mathrm{R}=\mathbb{Z}_{\textit{p}\textit{q}}\), with \(\textit{p}<\textit{q}\) and \(\textit{p}+\textit{q}\equiv 0\pmod{4}\), then \(G(\mathrm{R})\) has a, \(\{\alpha C_{4}, \beta S_{4}, \gamma S_{2}\}\)-decomposition, where \(\alpha=\frac{(\textit{p}-1)(\textit{q}-1)}{4}\), \(\beta= \frac{(\textit{p}-1)(\textit{q}-1)(\textit{p}+\textit{q}-3)}{4}\) and \(\gamma=\frac{(\textit{p}\textit{q}-2\textit{p}-2\textit{q}+3)(\textit{p}-1)(\textit{q}-1)}{4}\).
Proof. According to Lemma 4.1, \(G(\mathrm{R})\) has an edge disjoint decomposition into a complete bipartite graph \(G_{ {Z}\backslash\{0\}}(\mathrm{R})\) realized as \(\mathsf{K}_{\textit{p}-1,\:\textit{q}-1}\), a bipartite graph with partitions \( {Z}\) and \( {U}\) and a \((\textit{p}\textit{q}-2\textit{p}-2\textit{q}+3)\)-regular graph \(G_{R}(\mathrm{R})\) with \((\textit{p}\textit{q}-\textit{p}-\textit{q}+1)\) vertices. In \(\mathsf{K}_{\textit{p}-1,\:\textit{q}-1}\), the total number of edges is \((\textit{p}-1)(\textit{q}-1)\) and divisible by \(4\). By Theorem 3.3, we have \((\textit{p}-1)(\textit{q}-1)/4\) edge disjoint copies of \(C_{4}\) in \(\mathsf{K}_{\textit{p}-1,\:\textit{q}-1}\). As in Lemma 4.3 and 4.4, there exist a \(\mathsf{K}_{1,\:(\textit{p}-1)(\textit{q}-1)}\) and a bipartite graph with partitions \( {Z}/\{0\}\) and \( {U}\). Clearly, there exist \((\textit{p}-1)(\textit{q}-1)/4\) edge disjoint copies of \(S_{4}\) in \(\mathsf{K}_{1,\:(\textit{p}-1)(\textit{q}-1)}\). Also, \(deg(\textit{y})= \textit{p}+\textit{q}-4\), for all \(\textit{y}\in {U}\), for the bipartite graph with partitions \( {Z}\backslash\{0\}\) and \( {U}\). If \(\textit{p}+\textit{q}\equiv 0\pmod{4}\) that is, adjacency to a vertex \(\textit{y}\in {U}\), is multiple of \(4\) to the vertices \(\textit{x} \in {Z}/\{0\}\), then there corresponds \((\textit{p}+\textit{q}-4)/4\) edge disjoint copies of \(S_{4}\) for each \(\textit{y}\in {U}\). Thus, there exist \((\textit{p}-1)(\textit{q}-1)(\textit{p}+\textit{q}-4)/4\) edge disjoint copies of \(S_{4}\) in the bipartite graph with partitions \( {Z}/\{0\}\) and \( {U}\). Combining both, we have \((\textit{p}-1)(\textit{q}-1)(\textit{p}+\textit{q}-3)/4\) edge disjoint copies of \(S_{4}\) in the bipartite graph with partitions \( {Z}\) and \( {U}\).
Now for the \((\textit{p}\textit{q}-2\textit{p}-2\textit{q}+3)\)-regular graph \(G_{R}(\mathrm{R})\), the total number of edges is even and always divisible by \(2\). Thus, there exist \((\textit{p}\textit{q}-2\textit{p}-2\textit{q}+3)(\textit{p}-1)(\textit{q}-1)/4\) edge disjoint copies of \(S_{2}\) in \(G_{R}(\mathrm{R})\). ◻
If \(\textit{p}+\textit{q}\equiv 2\pmod{4}\), that is, adjacency to a vertex \(\textit{y}\in {U}\), is of the form \(4k+2\) to the vertices \(\textit{x} \in {Z}/\{0\}\), then there corresponds \((\textit{p}+\textit{q}-2)/4\) edge disjoint copies of \(S_{4}\) and a \(S_{2}\) to a vertex \(\textit{y}\in {U}\). In this case the bipartite graph with partitions \( {Z}/\{0\}\) and \( {U}\), has a decomposition into \((\textit{p}-1)(\textit{q}-1)(\textit{p}+\textit{q}-2)/4\) edge disjoint copies of \(S_{4}\) and \((\textit{p}-1)(\textit{q}-1)\) edge disjoint copies of \(S_{2}\). Combining both numbers, there exist \((\textit{p}-1)(\textit{q}-1)(\textit{p}+\textit{q}-1)/4\) edge disjoint copies of \(S_{4}\) and \((\textit{p}-1)(\textit{q}-1)\) edge disjoint copies of \(S_{2}\) in the bipartite graph with partitions \( {Z}\) and \( {U}\). For \((\textit{p}\textit{q}-2\textit{p}-2\textit{q}+3)\)-regular graph \(G_{R}(\mathrm{R})\), \(S_2\) decomposition remains same as in the above theorem. Thus, combining the total copies of \(S_2\), there is \((\textit{p}\textit{q}-2\textit{p}-2\textit{q}+4)(\textit{p}-1)(\textit{q}-1)/4\) edge disjoint copies of \(S_2\) in \(G(\mathrm{R})\). This gives the following result.
Corollary 4.6. Let \(\mathrm{R}=\mathbb{Z}_{\textit{p}\textit{q}}\), with \(\textit{p}<\textit{q}\) and \(\textit{p}+\textit{q}\equiv 2\pmod{4}\), then \(G(\mathrm{R})\) has a, \(\{\alpha C_{4}, \beta S_{4}, \gamma S_{2}\}\)-decomposition, where \(\alpha=\frac{(\textit{p}-1)(\textit{q}-1)}{4}\), \(\beta= \frac{(\textit{p}-1)(\textit{q}-1)(\textit{p}+\textit{q}-1)}{4}\) and \(\gamma=\frac{(\textit{p}\textit{q}-2\textit{p}-2\textit{q}+4)(\textit{p}-1)(\textit{q}-1)}{4}\).
Note that when \(\textit{n}=\textit{p}^{r_{1}}_{1}\textit{p}^{r_{2}}_{2}\dots \textit{p}^{r_{t}}_{t}\) is even, then \(G( \mathbb{Z}_n)\) is isomorphic to a bipartite graph [7, Theorem 3.5]. So, in the next theorem we decompose \(G( \mathbb{Z}_n)\) into its subgraphs, where each \(\textit{p}_i\)’s are distinct odd primes, \(t\geq 2\), and at least one of the \(r_i>1\). Recently, Alsaluli et al. [3], partitions the vertex set of \(G(\mathrm{R})\), when \(\mathrm{R}= \mathbb{Z}_n\), into disjoint cosets \(i+J(\mathrm{R})\), where \(i\in \mathbb{Z}_n\) and \(J(\mathrm{R})\) is the jacobson radicals of \(\mathrm{R}\). Following this observation in the next theorem we decompose \(G(\mathrm{R})\) into multipartite subgraph, complete graphs and complete bipartite graphs.
Theorem 4.7. Let \(\mathrm{R}= \mathbb{Z}_n\), where \(\textit{n}\) is defined as above. Then \(G(\mathrm{R})\) has an edge disjoint decomposition into a multipartite subgraph \(H\), \(\phi(L)\) subgraphs isomorphic to \(\mathsf{K}_{|J(\mathrm{R})|, |J(\mathrm{R})|}\), and \(\phi(L)\) subgraphs isomorphic to \(\mathsf{K}_{|J(\mathrm{R})|}\), where \(L= \textit{p}_1\textit{p}_2\dots \textit{p}_t\), i.e., \(G(\mathrm{R})\) has a \(\{(\phi(L))\mathsf{K}_{|J(\mathrm{R})|, |J(\mathrm{R})|}, H, (\phi(L))\mathsf{K}_{|J(\mathrm{R})|}\}\)-decomposition.
Proof. Divide the vertex set of \(G(\mathrm{R})\) as \(V_i=\{i+J(\mathrm{R})\mid 0\leq i\leq L-1\}\) such that \(|V_i|=|J(\mathrm{R})|\) (see [3]). If \(i=0\), \(V_0= J(\mathrm{R})\), and hence every vertex of \(V_0\) is adjacent to each vertex of \(V_i\), whenever \(V_i\subseteq {U}\). Since the representative of \(V_i\) corresponds to elements of \(\mathbb{Z}_{\textit{p}_1\textit{p}_2\dots \textit{p}_t}\) and \(|V_i|=|J(\mathrm{R})|\) for each \(i\). Therefore, there exist \(\phi(L)\) edge disjoint complete bipartite subgraph \(\mathsf{K}_{|J(\mathrm{R})|, |J(\mathrm{R})|}\) with vertex set \(V_0\) and \(V_i\), whenever \(gcd(i, \textit{p}_1\textit{p}_2\dots \textit{p}_t)=1\). Moreover, each vertex of \(V_i\) is adjacent to every vertex of \(V_j\) if and only if \(gcd(i+j,n)=1\) [3, Lemma 1]. Thus, between each vertices of \(V_i\) and \(V_j\) for \(\{1\leq i,j\leq L-1\}\), there exists an edge disjoint multipartite subgraph \(H\), where number of partitions are \(L-1\) and vertices in each partitions are \(|J(\mathrm{R})|\). The rest of the adjacency lies between the vertices within \(V_i\subseteq {U}\). Note that, for all \(x, x'\in V_i\), whenever \(V_i\subseteq {U}\), \(x+x'\in {U}\) (see [7, Lemma 2.7]). Thus for each \(V_i\subseteq {U}\) there exist \(\phi(L)\) copies of edge disjoint complete subgraph \(\mathsf{K}_{|J(\mathrm{R})|}\). Because this decomposition exhausts all the adjacency (edges), no further decomposition exists. ◻
Using the decomposition of \(G(\mathbb{Z}_n)\) into a complete bipartite graph, a multipartite graph, and a complete graph, one can evaluate the total number of edges in \(G(\mathrm{R})\) for \(\mathrm{R}= \mathbb{Z}_n\). Moreover, by this decomposition, one can further decompose the unit graph into cycle, star, and path graphs for various values of \(\textit{n}\).
In this study, we decompose \(G(\mathrm{R})\), where \(\mathrm{R}\) is a finite local ring and a ring of integers modulo \(\textit{n}\), into its edge-disjoint subgraphs. Utilizing this decomposition approach, we further find the number of edges in \(G(\mathrm{R})\), where \(\mathrm{R}\) is a finite local ring. Furthermore, we find cycle and star decomposition in unit graph for some finite commutative rings. In general, the decomposition of a unit graph of commutative rings enhances the decomposition of other algebraic structures. This refined structure can be effectively utilized in various networking applications. For further study, one can decompose the unit graph of the Artinian ring into its subgraphs and can use these subgraphs to evaluate other properties of unit graphs.