PARADIGMA BARU PENDIDIKAN MATEMATIKA DAN APLIKASI ONLINE INTERNET PEMBELAJARAN


CONTACT:  

Mohammad Nafie Jauhari           nafie.jauhari@uin-malang.ac.id          Department of Mathematics, UIN 
Maulana Malik Ibrahim, Malang, East Java 65144 

 

       The article can be accessed here. https://doi.org/10.15642/mantik.2022.8.1.99-104 

 On the Relation of the Total Graph of a Ring and a Product of 

Graphs 
 

 

Mohammad Nafie Jauhari 

  Universitas Islam Negeri Maulana Malik Ibrahim, Malang, Indonesia,  

 

Article history: 

Received Aug 31, 2022 

Revised, Dec 25, 2022 

Accepted, Dec 31, 2022 

 

Kata Kunci:  

Grup, Total graf, 

Isomorfisma, 

Perkalian Kartesius 

Abstrak. Graf total atas suatu ring 𝑅, dinotasikan dengan 𝑇(Γ(𝑅)), 

didefinisikan sebagai suatu graf dengan himpunan titik 

𝑉 (𝑇(Γ(𝑅))) = 𝑅 dan dua titik berbeda 𝑢,𝑣 ∈ 𝑉(𝑇(Γ(𝑅))) 

bertetangga jika dan hanya jika 𝑢 + 𝑣 ∈ 𝑍(𝑅), di mana 𝑍(𝑅) 
merupakan pembagi nol dari 𝑅. Perkalian Kartesius dari dua graf 
𝐺 dan 𝐻 merupakan suatu graf yang dinotasikan dengan 𝐺 × 𝐻 
di mana himpunan titiknya adalah 𝑉(𝐺 × 𝐻) = 𝑉(𝐺) × 𝑉(𝐻) 
dan dua titik berbeda (𝑢1,𝑣1) dan (𝑢2,𝑣2) di 𝑉(𝐺 × 𝐻) 
bertetangga jika dan hanya jika: 1) 𝑢1 = 𝑢2 dan 𝑣1𝑣2 ∈ 𝐻; atau 
2) 𝑣1 = 𝑣2 dan 𝑢1𝑢2 ∈ 𝐸(𝐺). Isomorfisma dari graf 𝐺 dan 𝐻 
adalah suatu fungsi bijektif 𝜙:𝑉(𝐺) → 𝑉(𝐻) sedemikian 
sehingga 𝑢,𝑣 ∈ 𝑉(𝐺) bertetangga jika dan hanya jika 
𝑓(𝑢),𝑓(𝑣) ∈ 𝑉(𝐻) bertetangga.  Akan dibuktikan bahwa graf 

𝑇(Γ(ℤ2𝑝)) isomorf dengan graf 𝑃2 × 𝐾𝑝 untuk setiap bilangan 

prima 𝑝. 
 

Keywords:  

Group, Total graph, 

Isomorphism, 

Cartesian product 

Abstract. The total graph of a ring 𝑅, denoted as 𝑇(Γ(𝑅)), is 

defined to be a graph with vertex set 𝑉 (𝑇(Γ(𝑅))) = 𝑅 and two 

distinct vertices 𝑢,𝑣 ∈ 𝑉 (𝑇(Γ(𝑅))) are adjacent if and only if 𝑢 +

𝑣 ∈ 𝑍(𝑅), where 𝑍(𝑅) is the zero divisor of 𝑅. The Cartesian 
product of two graphs 𝐺 and 𝐻 is a graph with the vertex set 
𝑉(𝐺 × 𝐻) = 𝑉(𝐺) × 𝑉(𝐻) and two distinct vertices (𝑢1,𝑣1) and 
(𝑢2,𝑣2) are adjacent if and only if: 1) 𝑢1 = 𝑢2 and 𝑣1𝑣2 ∈ 𝐻; or 2) 
𝑣1 = 𝑣2 and 𝑢1𝑢2 ∈ 𝐸(𝐺). An isomorphism of graphs 𝐺 dan 𝐻 is a 
bijection 𝜙:𝑉(𝐺) → 𝑉(𝐻) such that 𝑢,𝑣 ∈ 𝑉(𝐺) are adjacent if and 
only if 𝑓(𝑢),𝑓(𝑣) ∈ 𝑉(𝐻) are adjacent. This paper proved that 

𝑇(Γ(ℤ2𝑝)) and 𝑃2 × 𝐾𝑝 are isomorphic for every odd prime 𝑝. 

 

How to cite: 

M. N. Jauhari, “On the Relation of Total Graph of a Ring and a Product of Graphs”, J. Mat. 

Mantik, vol. 8, no. 2, pp. 99-104, December 2022. 

 

 

  

Jurnal Matematika MANTIK 

Vol. 8, No. 2, December 2022, pp. 99-104 

 

ISSN: 2527-3159 (print) 2527-3167 (online) 

mailto:nafie.jauhari@uin-malang.ac.id
https://doi.org/10.15642/mantik.2021.7.1.9-19
http://u.lipi.go.id/1458103791


Jurnal Matematika MANTIK 

Vol. 8, No. 2, December 2022, pp. 99-104 

 

100 

 

1. Introduction 

Investigating group or ring properties and its structures from their graph representation 

become a new trend in graph theoretic research. Many authors proved that there are tight 

bonds between the rings and graphs. Aalipour in [1] investigated the chromatic number and 

clique number of a commutative ring. [2] gave a novel application of a central-vertex 

complete graph to a commutive ring. In 2008, [3] investigated the commutive graph of 

rings generated from matrices over a finite filed. Three years after the graph of a ring was 

introduced in [4], [5] proposed useful applications of semirings in mathematics and 

theoretical computer science. One interest in applying graph invariant on a group also 

showed in [6] in the properties of zero-divisor graphs. Another useful graph generated from 

group or ring structure is Cayley graphs which has many useful applications in solving and 

understanding a variety problem in several scientific interests [7]. 

The graph isomorphism itself has many applications in real life and many scientific 

fields [8]. [9] stated briefly about its application in the atomic structures and [10] showed 

how it can be applied in biochemical data. To prove the isomorphism of two graphs is an 

NP-problem in which there is no specific algorithm or certain way that works for all graphs 

in consideration [11]. In 1996, [12] proposed a good graph isomorphism algorithm but still 

troublesome for a large graphs. 

Considering those applications of ring generated graphs, the applications of the graph 

isomorphisms, and the isomorphism-related algorithm complexity, finding an isomorphism 

of ring-structured graphs and the graph obtained from certain operation is a challenging 

task and a potential new interest in graph theory research. This paper considers the relation 

between the total graph of ℤ𝑝 and 𝑃2 × 𝐾𝑝 for all odd prime 𝑝. 

 

2. Preliminaries 

A graph 𝐺 is a pair 𝐺 = (𝑉,𝐸) for non-empty set 𝑉 and 𝐸 ⊆ [𝑉]2 (the elements of 𝐸 
are 2-element subsets of 𝑉). For terminologies and notations concerning to a graph and its 
invariants, please consider [13]. This preliminary covers the definitions related to ring and 

the total graph of a ring. It also provides some definitions related to graph isomorphism and 

a graph operation. 

Definition 1. Ring [14] 

A ring 𝑅 is a set with two binary operations, addition and multiplication, such that for all 
𝑎,𝑏,𝑐 ∈ 𝑅: 
1. 𝑎 + 𝑏 = 𝑏 + 𝑎, 
2. (𝑎 + 𝑏)+ 𝑐 = 𝑎 + (𝑏 + 𝑐), 
3. There is an additive identity 0, 

4. There is an element −𝑎 ∈ 𝑅 such that 𝑎 + (−𝑎) = 0, 
5. 𝑎(𝑏𝑐) = (𝑎𝑏)𝑐, and 
6. 𝑎(𝑏 + 𝑐) = 𝑎𝑏 + 𝑎𝑐 and (𝑏 + 𝑐)𝑎 = 𝑏𝑎 + 𝑐𝑎. 
 

With this definition, ℤ2𝑝, an integer modulo 2𝑝 set, equipped with addition and 

multiplication modulo 2𝑝 operation is a ring. 
 

Definition 2. Zero Divisor [14] 

A zero-divisor is a nonzero element 𝑎 of a commutative ring 𝑅 such that there is a nonzero 
element 𝑏 ∈ 𝑅 with 𝑎𝑏 = 0. 



Mohammad Nafie Jauhari 

On the Relation of Total Graph of a Ring and a Product of Graphs 

101 

 

Definition 3. Total Graph of a Ring [15] 

Let 𝑅 be a ring and 𝑍(𝑅) denotes the zero divisor of 𝑅. The total graph of 𝑅, denoted by 

𝑇(Γ(𝑅)) is an undirected graph with elements of 𝑅 as its vertices, and for distinct 𝑥,𝑦 ∈ 𝑅, 

the vertices 𝑥 and 𝑦 are adjacent if and only if 𝑥 + 𝑦 ∈ 𝑍(𝑅). 
 

From those definitions of zero divisor and total graph, we will construct a total graph 

of ℤ2𝑝 for an odd prime 𝑝. 

 

Definition 4. Graph Homomorphism and Isomorphism [13] 

Let 𝐺 = (𝑉𝐺,𝐸𝐺) and 𝐻 = (𝑉𝐻,𝐸𝐻) be graphs. A map 𝜑:𝑉𝐺 → 𝑉𝐻 is a homomorphism 
from 𝐺 to 𝐻 if it preserves the adjacency of the vertices. In another word, {𝑥,𝑦} ∈ 𝐸𝐺 ⇒
{𝜑(𝑥),𝜑(𝑦)} ∈ 𝐸𝐻. If 𝜑 is bijective and 𝜑

−1 is also a homomorphism, then 𝜑 is an 
isomorphism and 𝐺 is said to be isomorphic to 𝐻. 
 

Definition 5. Cartesian Product [13] 

The Cartesian product of two graphs 𝐺 and 𝐻 is a graph with the vertex set 𝑉(𝐺 × 𝐻) =
𝑉(𝐺) × 𝑉(𝐻) and two distinct vertices (𝑢1,𝑣1) and (𝑢2,𝑣2) are adjacent if and only if: 1) 
𝑢1 = 𝑢2 and 𝑣1𝑣2 ∈ 𝐻; or 2) 𝑣1 = 𝑣2 and 𝑢1𝑢2 ∈ 𝐸(𝐺). An isomorphism of graphs 𝐺 dan 
𝐻 is a bijection 𝜙:𝑉(𝐺) → 𝑉(𝐻) such that 𝑢,𝑣 ∈ 𝑉(𝐺) are adjacent if and only if 
𝑓(𝑢),𝑓(𝑣) ∈ 𝑉(𝐻) are adjacent. 
 

3. Main Results 

In this section we will prove the isomorphism of the total graph of ℤ2𝑝 and 𝑃2 × 𝐾𝑝. 

We will investigate several properties of 𝑇(Γ(ℤ2𝑝)) before we proof the isomorphism. 

Those investigations will be provided as lemmas and theorems equipped with their proofs. 

To characterize 𝑇(Γ(ℤ2𝑝)), we consider its vertex set, the degree of each vertex, and the 

clique it has as subgraphs, since 𝑃2 × 𝐾𝑝 can easily be considered and seen from those 

properties. 

Lemma 1. The zero divisor of ℤ2𝑝 is 

𝑍(ℤ2𝑝) = {𝑝} ∪ {2𝑛:𝑛 = 1,2,…,𝑛 − 1} 

for every odd prime 𝑝. 
Proof. 

For each 𝑥 ∈ ℤ2𝑝, the exactly one of the following holds: 𝑥 = 𝑝, 𝑥 is even, and 𝑥 ≠ 𝑝 is 

odd. 

Case 1, 𝑥 = 𝑝 

Since 2𝑝 = 0 and 2 ∈ ℤ2𝑝, we conclude that 𝑝 ∈ 𝑍(ℤ2𝑝). 

 

Case 2, 𝑥 is even 
Let 𝑥 = 2𝑚 for some 𝑚 ∈ ℤ. Since 𝑥𝑝 = 2𝑚𝑝 = 𝑚 ⋅ 2𝑝 = 𝑚 ⋅ 0 = 0 and 𝑝 ∈ ℤ2𝑝, we 

conclude that 𝑥 ∈ 𝑍(ℤ2𝑝) for all even 𝑥 ∈ ℤ2𝑝. 

 

Case 3, 𝑥 ≠ 𝑝 is odd 
If 𝑥 = 1, then 𝑥𝑦 ≠ 0 for all 0 ≠ 𝑦 ∈ ℤ2𝑝. 

We will show that 1 ≠ 𝑥 ∉ 𝑍(ℤ2𝑝) by using a contradiction. Suppose on the contrary, that 

𝑥 ∈ 𝑍(ℤ2𝑝). Consequently, there exists 0 ≠ 𝑦 ∈ ℤ2𝑝 such that 𝑥𝑦 = 0. It follows that 

gcd(𝑥,2𝑝) > 1. Since the factor of 2𝑝 is 2 and 𝑝, we obtain that 𝑥 divides 𝑝. It is a 
contradiction since 𝑝 is a prime number. 



Jurnal Matematika MANTIK 

Vol. 8, No. 2, December 2022, pp. 99-104 

 

102 

 

Lemma 2. Let 𝑝 be an odd prime. Let 𝐴 ⊆ ℤ2𝑝 be the set of all odd elements of ℤ2𝑝 and 

𝐵 ⊆ ℤ2𝑝 be the set of all even elements of ℤ2𝑝. {𝑢,𝑣} ∈ 𝐸(𝑇(Γ(ℤ2𝑝))) for all 𝑢,𝑣 ∈ 𝐴 

and {𝑥,𝑦} ∈ 𝐸(𝑇(Γ(ℤ2𝑝))) for all 𝑥,𝑦 ∈ 𝐵. In another word, the vertices in 𝐴 dan 𝐵 

form cliques in 𝑇(Γ(ℤ2𝑝)). 

Proof. 

Let 𝑢,𝑣 ∈ 𝐴 and let 𝑢 = 2𝑠 + 1 and 𝑣 = 2𝑡 + 1 for some 𝑠,𝑡 ∈ ℤ. We obtain 
𝑢 + 𝑣 = 2𝑠 + 1 + 2𝑡 + 1

= 2(𝑠 + 𝑡 + 1) ∈ 𝑍(ℤ2𝑝).
 

Therefore {𝑢,𝑣} ∈ 𝐸(𝑇(Γ(ℤ2𝑝))) for all 𝑢,𝑣 ∈ 𝐴. 

Let 𝑥,𝑦 ∈ 𝐴 and let 𝑥 = 2𝑠 and 𝑦 = 2𝑡 for some 𝑠,𝑡 ∈ ℤ. We obtain 
𝑥 + 𝑦 = 2𝑠 + 2𝑡

= 2(𝑠 + 𝑡) ∈ 𝑍(ℤ2𝑝).
 

Therefore {𝑥,𝑦} ∈ 𝐸(𝑇(Γ(ℤ2𝑝))) for all 𝑥,𝑦 ∈ 𝐵. 

It proves that 𝐴 and 𝐵 form cliques in 𝑇(Γ(ℤ2𝑝)). 

 

Lemma 3. Let 𝐴 and 𝐵 be sets defined in Lemma 2 and 𝑝 be an odd prime number. For 
each 𝑣 ∈ 𝐴 there is a unique 𝑥 ∈ 𝐵 such that  

{𝑣,𝑥} ∈ 𝐸(𝑇(Γ(ℤ2𝑝))). 

Proof. 

For each 𝑣 ∈ 𝐴, choose 𝑥 = 𝑝 − 𝑣. It can be easily verified that 𝑥 ∈ 𝐵 since 𝑝 and 𝑣 are 
both odd numbers. On the other hand, let 𝑥 ∈ 𝐵 and 𝑥 ≠ 𝑝 − 𝑣. Suppose that {𝑣,𝑥} ∈

𝐸(𝑇(Γ(ℤ2𝑝))), that is 𝑣 + 𝑥 ∈ 𝑍(ℤ2𝑝). Since 𝑣 is odd and 𝑥 is even, it follows that 𝑣 +

𝑥 is an odd number and 𝑣 + 𝑥 = 𝑝 ⟺ 𝑥 = 𝑝 − 𝑣, a contradiction. This proves that 

{𝑣,𝑝 − 𝑣} ∈ 𝐸(𝑇(Γ(ℤ2𝑝))),∀𝑥 ∈ 𝐴. 

Analogous to this proof, we can easily prove that for each 𝑥 ∈ 𝐵 there is a unique 𝑣 ∈ 𝐴 
such that  

{𝑣,𝑥} ∈ 𝐸(𝑇(Γ(ℤ2𝑝))). 

 

Before we discuss the main problem, consider Figure 1 that represents the graph 

𝑇(Γ(ℤ2𝑝)) for several 𝑝. 

  
Figure 1. 𝑇(Γ(ℤ2𝑝)) for 𝑝 ∈ {3,5,7}. 

 



Mohammad Nafie Jauhari 

On the Relation of Total Graph of a Ring and a Product of Graphs 

103 

 

Theorem 1. For any odd prime 𝑝, 𝑇(Γ(ℤ2𝑝)) is isomorph to 𝑃2 × 𝐾𝑝. 

Proof. Let 𝑉(𝑃2) and 𝑉(𝐾𝑝) be labeled as {𝑝1,𝑝2} and {𝑘0,𝑘1,…,𝑘𝑝−1} respectively. The 

vertices of the resulting graph obtained from the Cartesian product, 𝑃2 × 𝐾𝑝, is therefore 

labeled 

{(𝑝1,𝑘1),(𝑝1,𝑘2),…,(𝑝1,𝑘𝑝),(𝑝2,𝑘1),(𝑝2,𝑘2),…,(𝑝2,𝑘𝑝)} 

in which  

{(𝑝𝑠,𝑘𝑖),(𝑝𝑠,𝑘𝑗)} ∈ 𝐸(𝑃2 × 𝐾𝑝),∀𝑖,𝑗 ∈ {1,2,…,𝑝} 

 and 𝑖 ≠ 𝑗, for 𝑠 ∈ {1,2}. Other edges to consider is {(𝑝1,𝑘𝑖),(𝑝2,𝑘(𝑝−𝑖 mod 𝑝)+1)} ∈

𝐸(𝑃2 × 𝐾𝑝),∀𝑖 ∈ {1,2,…,𝑝}. Here, the “mod” in “𝑝 − 𝑖 mod 𝑝” is a modulus operator, not 

a modulus relation. 

  

Consider the function 𝜑:𝑉(𝑇(Γ(ℤ2𝑝))) → 𝑉(𝑃2 × 𝐾𝑝) defined as follows: 

𝜑(𝑥) =

{
 
 

 
 (𝑃1,(

𝑝 − 𝑥

2
mod 𝑝) + 1), if 𝑥 is odd

(𝑃2,
𝑥

2
+ 1), if 𝑥 is even.

 

 

Since 𝜑 is a bijective function that preserves adjacency of the vertices of 𝑉(𝑇(Γ(ℤ2𝑝))) 

and 𝑉(𝑃2 × 𝐾𝑝), we conclude that 𝑇(Γ(ℤ2𝑝)) and 𝑃2 × 𝐾𝑝 are isomorphic. 

 

Figure 1 and Figure 2 show some examples of the mapping result of 𝜑. 
 

 

 
Figure 2. the mapping result of 𝜑 from 𝑇(Γ(ℤ2⋅5)) to 𝑃2 × 𝐾5 

 

 
Figure 3. the mapping result of 𝜑 from 𝑇(Γ(ℤ2⋅7)) to 𝑃2 × 𝐾7 

 

4. Conclusion 

From the discussion, we conclude that 𝑇(Γ(ℤ2𝑝)) and 𝑃2 × 𝐾𝑝 are isomorphic. 

 

  



Jurnal Matematika MANTIK 

Vol. 8, No. 2, December 2022, pp. 99-104 

 

104 

 

References  

[1] G. Aalipour and S. Akbari, “Application of some combinatorial arrays in coloring of 

total graph of a commutative ring,” May 2013. 

[2] J. D. LaGrange, “Weakly central-vertex complete graphs with applications to 

commutative rings,” J. Pure Appl. Algebr., vol. 214, no. 7, pp. 1121–1130, Jul. 2010. 

[3] A. Abdollahi, “Commuting graphs of full matrix rings over finite fields,” Linear 

Algebra Appl., 2008. 

[4] R. P. Grimaldi, “Graphs from rings,” Congr. Numer, vol. 71, pp. 95–104, 1990. 

[5] J. S. Golan, “The theory of semirings with applications in mathematics and 

theoretical computer science.,” p. 318, 1992. 

[6] D. F. Anderson, T. Asir, A. Badawi, and T. Tamizh Chelvam, Graphs from Rings. 

2021. 

[7] A. Kelarev, J. Ryan, and J. Yearwood, “Cayley graphs as classifiers for data mining: 

The influence of asymmetries,” Discrete Math., vol. 309, no. 17, pp. 5360–5369, 

Sep. 2009. 

[8] S. Y. Hsieh, C. W. Huang, and H. H. Chou, “A DNA-based graph encoding scheme 

with its applications to graph isomorphism problems,” Appl. Math. Comput., vol. 

203, no. 2, pp. 502–512, Sep. 2008. 

[9] M. Grohe and P. Schweitzer, “The graph isomorphism problem,” Commun. ACM, 

vol. 63, no. 11, pp. 128–134, 2020. 

[10] V. Bonnici, R. Giugno, A. Pulvirenti, D. Shasha, and A. Ferro, “A subgraph 

isomorphism algorithm and its application to biochemical data,” BMC 

Bioinformatics, vol. 14, no. SUPPL7, pp. 1–13, Apr. 2013. 

[11] C. S. Calude, M. J. Dinneen, and R. Hua, “QUBO formulations for the graph 

isomorphism problem and related problems,” Theor. Comput. Sci., vol. 701, pp. 54–

69, Nov. 2017. 

[12] X. Y. Jiang and H. Bunke, “Including geometry in graph representations: A 

quadratic-time graph isomorphism algorithm and its applications,” Lect. Notes 

Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), 

vol. 1121, pp. 110–119, 1996. 

[13] R. Diestel, “Graph Theory (5th Edition),” Springer, 2017. 

[14] J. Gallian, Contemporary Abstract Algebra. 2021. 

[15] D. F. Anderson and A. Badawi, “The total graph of a commutative ring,” J. Algebr., 

vol. 320, no. 7, pp. 2706–2719, Oct. 2008.