PARADIGMA BARU PENDIDIKAN MATEMATIKA DAN APLIKASI ONLINE INTERNET PEMBELAJARAN


CONTACT:  

Marsidi,                    marsidiarin@gmail.com                  Department of Mathematics Education, Universitas 

PGRI Argopuro Jember, Indonesia 

 

       The article can be accessed here. https://doi.org/10.15642/mantik.2022.8.2.78-88 

Developing A Secure Cryptosystem with Rainbow Vertex 

Antimagic Coloring of Cycle Graph 
 

 

Marsidi 

Universitas PGRI Argopuro Jember, Indonesia 

 

 

Article history: 

Received Aug 8, 2022 

Revised, Nov 9, 2022 

Accepted, Nov 30, 2022 

 

Kata Kunci:  

Graf siklus, 

pewarnaan pelangi 

titik anti ajaib, nilai 

pewarnaan pelangi 

titik anti ajaib, 

modifikasi Affine 

Cipher, kriptosistem. 

 

Abstrak. Pelabelan sisi pada graf 𝐺 adalah fungsi 𝑔 dari 
himpunan sisi dari graf 𝐺 ke bilangan asli pertama sampai dengan 
kardinalitas himpunan sisi. Graf 𝐺 mempunyai pewarnaan pelangi 
titik anti ajaib jika untuk setiap dua titik terdapat suatu lintasan 

dengan warna berbeda dari semua titik dalam. Warna titik dari 

graf 𝐺 ditentukan oleh bobot titik. Bobot titik pada graf 𝐺 
diperoleh dengan menjumlahkan semua label sisi yang terkait 

dengan simpul tersebut. Nilai pewarnaan pelangi titik anti ajaib 

dari graf 𝐺, dilambangkan dengan 𝑟𝑣𝑎𝑐(𝐺) adalah jumlah 
minimum warna yang diinduksi oleh pewarnaan pelangi titik anti 

ajaib. Dalam makalah ini, kami menentukan batas atas nilai 

pewarnaan pelangi titik anti ajaib (𝑟𝑣𝑎𝑐) pada graf siklus (𝐶𝑛) 
dan mengembangkan modifikasi Affine Cipher dari pewarnaan 

pelangi titik anti ajaib untuk membuat kriptosistem yang aman. 

 

Keywords:  

Cycle graph, rainbow 

vertex antimagic 

coloring, rainbow 

vertex antimagic 

connection number, 

modified Affine 

Cipher, cryptosystem. 

 

 

Abstract. An edge labeling of graph 𝐺 is a function 𝑔 from the 
edge set of graph 𝐺 to the first natural numbers up to the number 
of the edge set. Graph 𝐺 admits a rainbow vertex antimagic 
coloring if, for any two vertices, there is a path with different 

colors of all internal vertices. The vertex color of graph 𝐺 is 
assigned by vertex weight. The vertex weight of graph 𝐺 is 
obtained by summing all edge labels that incident with that vertex. 

The rainbow vertex antimagic connection number of graph 𝐺, 
denoted by 𝑟𝑣𝑎𝑐(𝐺) is the smallest number of different colors 
induced by rainbow vertex antimagic coloring. In this research, we 

determine the upper bound of the rainbow vertex antimagic 

connection number (𝑟𝑣𝑎𝑐) on a cycle graph (𝐶𝑛) and create a 
secured cryptosystem using a modified Affine Cipher based on 

rainbow vertex antimagic coloring.  

  

How to cite: 

Marsidi, “Developing A Secure Cryptosystem with Rainbow Vertex Antimagic Coloring of 

Cycle Graph”, J. Mat. Mantik, vol. 8, no. 2, pp. 78-88, October 2022 

 

 

 

  

Jurnal Matematika MANTIK 

Vol. 8, No. 2, October 2022, 78-88 

 

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

mailto:sadiq.taha@uod.ac
https://doi.org/10.15642/mantik.2021.7.1.9-19
http://u.lipi.go.id/1458103791


Marsidi 

Developing A Secure Cryptosystem with Rainbow Vertex Antimagic Coloring of Cycle Graph 

79 
 

1. Introduction 

Graph theory is one of the studies of mathematics that has applications in the field of 

mathematics. One of the popular graph theory studies is coloring theory. Coloring theory 

is developed from a Four-Color Theorem. The theorem states that each map can be 

colored using four colors, so that adjacent areas do not have the same color. The 

development of graph coloring theory covers vertex coloring, edge coloring, face 

coloring, 𝒓-dynamic coloring, and rainbow coloring. 
In this paper, we discuss rainbow vertex antimagic coloring which begins with the 

following definition. The graph that is discussed in this study is a simple and connected 

graph, definitively it can be seen in [1]. The concept of rainbow connection has several 

interesting variants, one of them is rainbow vertex-connection. It was introduced by 

Krivelevich and Yuster [2]. Let 𝐺 be a graph and 𝑐: 𝑉(𝐺) → {1,2,⋯,𝑘} be a vertex 𝑘-
coloring, for some 𝑘 ∈ 𝑁. A path 𝑃 in 𝐺 with a vertex 𝑘-coloring is said to be a rainbow 
vertex-path, if all internal vertices of 𝑃 have distinct colors. The graph 𝐺 is said to be a 
rainbow vertex connected, if for any two vertices 𝑢 and 𝑣 in 𝑉(𝐺) there is a rainbow 
vertex-path. A vertex 𝑘-coloring of 𝐺 is said rainbow vertex coloring, if 𝐺 rainbow vertex 
connected under 𝑐. The rainbow vertex connection number, denoted by 𝑟𝑣𝑐(𝐺), is the 
smallest positive integer k such that 𝐺 has rainbow vertex k-coloring. Krivelevich and 
Yuster also gave the lower bound for a graph 𝐺, namely 𝑟𝑣𝑐(𝐺) ≥  𝑑𝑖𝑎𝑚(𝐺) –  1, where 
𝑑𝑖𝑎𝑚(𝐺) is the diameter of the graph 𝐺 [3]. Several other concepts as a result of 
developing the concept of rainbow vertex coloring can be seen in  [4][5][6][7][8][9][10]. 

Septory et al. [11] developed rainbow coloring into rainbow antimagic coloring, 

while Marsidi et al. developed rainbow vertex coloring into rainbow vertex antimagic 

coloring. A formal definition related to rainbow vertex antimagic coloring can be seen in 

[12]. In this paper, we determine the upper bound of the rainbow vertex antimagic 

connection number of cycle graph (𝑟𝑣𝑎𝑐(𝐶𝑛)). Some other results on rainbow antimagic 
coloring of graphs can be seen in Antimagic labeling, rainbow coloring, rainbow 

antimagic coloring, and rainbow antimagic connection number[13][14]. 

Furthermore, we apply the concept of rainbow vertex antimagic coloring of graphs 

for developing a secured cryptosystem. Cryptography is a common approach for 

maintaining the secrecy of information dispersed across an insecure network [15]. A 

cryptosystem is a set of cryptographic algorithms used to implement a specific security 

service, such as confidentiality (encryption). The cryptosystem is a set of cryptographic 

techniques and infrastructure used to provide information security services. The 

cryptosystem is also known as a cipher system.  

The cryptosystem is typically formed by three algorithms: one for key generation, 

one for encryption, and one for decryption. The term cipher (or cypher) refers to a pair of 

algorithms, one for encryption and one for decryption. As a result, when the key 

generation algorithm is important, the term cryptosystem is most generally used. The 

term cryptosystem is commonly used to refer to public key techniques; however, for 

symmetric key techniques, both "cipher" and "cryptosystem" are used. The strength of 

cryptography protocols relies on the encryption-decryption keys management: how to 

protect the keys from disclose to unauthorized parties [16]. 

The Affine Cipher and rainbow vertex antimagic coloring concepts are combined in 

this article to form the modified Affine Cipher. The Affine Cipher is a monoalphabetic 

substitution cipher in which each letter of an alphabet is given a numeric representation, 

encrypted with a simple mathematical function, and then converted back to a letter. 

Because of the formula, each letter encrypts to and from another letter, implying that the 

cipher is basically a regular substitution cipher with a structured which letter goes to 

which. As a result, it suffers from the same issues as all substitution ciphers. Each letter is 

encoded using the function, where denotes the length of the shift. As encryption and 



Jurnal Matematika MANTIK  

Vol 8, No 2, October 2022, pp. 78-88 

80 

decryption keys, we use labeling of rainbow vertex antimagic coloring and rainbow 

vertex antimagic connection number. 

 

2. Preliminaries 

In determining the exact value of rainbow vertex antimagic connection number of 

graph 𝐺 (𝑟𝑣𝑎𝑐(𝐺)), a lower bound is needed. The lower bound of 𝑟𝑣𝑎𝑐(𝐺) has been 
found by Marsidi, et al. For more details see [12]. The lower bound of 𝑟𝑣𝑎𝑐(𝐺) that 
found by Marsidi, et al is as follows. 

Remark 1 [16] 

Let 𝐺 be a connected graph, 𝑟𝑣𝑎𝑐(𝐺) ≥ 𝑟𝑣𝑐(𝐺). 

2.1 Cryptosystem 

A simple model of a cryptographic system that ensures the confidentiality of 
transmitted data is illustrated in Figure 1. The illustration below depicts this fundamental 

model.  

 

Figure 1. Basic Model of Cryptosystem. 

Before the plaintext encryption process is carried out, it must be converted first with 
the Affine Cipher method. The plaintext conversion rules with Affine Cipher are 

presented in Table 1.  
Table 1. The Conversion Rules on Affine Cipher 

A B C D E F G H I J 

0 1 2 3 4 5 6 7 8 9 

K L M N O P Q R S T 

10 11 12 13 14 15 16 17 18 19 

U V W X Y Z     

20 21 22 23 24 25     

 

Components of a Cryptosystem 

The various components of a basic cryptosystem are as follows. 

a) Plaintext.  

It is the data that must be secured during transmission. 

b) Encryption Algorithm.  

Given a plaintext and an encryption key, it is a mathematical procedure that creates a 

ciphertext. It is a cryptographic technique that converts plaintext into ciphertext using 

an encryption key. 

 

 



Marsidi 

Developing A Secure Cryptosystem with Rainbow Vertex Antimagic Coloring of Cycle Graph 

81 
 

c) Ciphertext.  

It is the scrambled version of the plaintext generated by the encryption algorithm 

when a specific encryption key is used. 

d) Decryption Algorithm.  

It is a mathematical process that creates a unique plaintext for each ciphertext and 

decryption key combination. It is a cryptographic method that takes in ciphertext and 

a decryption key and outputs plaintext. Because it reverses the encryption technique, 

the decryption algorithm is closely related to it. 

e) Encryption Key.  

The sender knows what it is. The sender inserts the encryption key and plaintext into 

the encryption algorithm to generate the ciphertext. 

f) Decryption Key.  

To the receiver, it is a known value. The encryption key and the decryption key are 

related, but not always identical. The receiver inputs the decryption key and the 

ciphertext into the decryption algorithm to retrieve the plaintext. 

 

2.2 Affine Cipher  

An 𝑚-letter alphabet's letters are first mapped to integers in the range 0,⋯,𝑚 − 1. 
The number that corresponds to each plaintext letter is then converted into another integer 

that corresponds to a ciphertext letter using modular arithmetic. The encryption function 
of a single letter is  

𝐸(𝑥) = (𝑎𝑥 + 𝑏) mod 𝑚 

where modulus 𝑚 is the alphabet size and 𝑎 and 𝑏 are the cipher keys. The value of 𝑎 
must be chosen so that 𝑎 and 𝑚 are coprime. The decryption of a function is 

𝐷(𝑥) = 𝑎−1(𝑥 − 𝑏) mod 𝑚 

where 𝑎−1 is the modular multiplicative inverse of 𝑎 modulo 𝑚. I.e., it satisfies the 
equation  

1 = 𝑎𝑎−1 mod 𝑚 

The multiplicative inverse of 𝑎 exists if 𝑎 and 𝑚 are coprime. Without the constraint on 
𝑎, the decryption may be impossible. As shown below, the decryption function is the 
inverse of the encryption function.  

𝐷(𝐸(𝑥)) = 𝑎−1(𝐸(𝑥) − 𝑏) mod 𝑚 

 = 𝑎−1(((𝑎(𝑥) + 𝑏) mod 𝑚) − 𝑏) 𝑚𝑜𝑑 𝑚 

 = 𝑎−1(𝑎(𝑥) + 𝑏 − 𝑏) mod 𝑚 

 = 𝑎−1𝑎𝑥 mod 𝑚 

 = 𝑥 mod 𝑚 

3. Results and Discussion 

This research produces the upper bound of rainbow vertex antimagic connection 

number of cycle graph that has not been found by previous researchers, so the results of 

this study are new. In addition, researchers develop applications in cryptosystems that are 

encrypted and decrypted using the resulting rainbow vertex antimagic connection number 

of cycle graph. 

 

https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
https://en.wikipedia.org/wiki/Modular_arithmetic


Jurnal Matematika MANTIK  

Vol 8, No 2, October 2022, pp. 78-88 

82 

3.1 Rainbow Vertex Antimagic Coloring of Cycle Graph 

Theorem 2  

If 𝐶𝑛 is a cycle graph with orders 𝑛 and 𝑛 ≥ 3, then 

𝑟𝑣𝑎𝑐(𝐶𝑛) ≤

{
 
 
 

 
 
 

𝑛

2
, 𝑖𝑓 𝑛 ≡ 2(𝑚𝑜𝑑 4)

𝑛

2
+ 1, 𝑖𝑓 𝑛 ≡ 0(𝑚𝑜𝑑 4)

⌊
𝑛

2
⌋ + 2, 𝑖𝑓 𝑛 ≡ 1(𝑚𝑜𝑑 4)

⌊
𝑛

2
⌋ + 1, 𝑖𝑓 𝑛 ≡ 3(𝑚𝑜𝑑 4)

 

Proof. Let 𝐶𝑛 be a cycle graph with vertex set 𝑉(𝐶𝑛) = {𝑥𝑖:1 ≤ 𝑖 ≤ 𝑛} and edge set 

𝐸(𝐶𝑛) = {𝑒𝑛 = 𝑥1𝑥𝑛;  𝑒𝑖 = 𝑥𝑖𝑥𝑖+1:1 ≤ 𝑖 ≤ 𝑛 − 1}. The diameter of 𝐶𝑛 is ⌊
𝑛

2
⌋. We divide 

into four cases to prove the upper bound of 𝑟𝑣𝑎𝑐(𝐶𝑛) as follows. 
 

Case 1. For 𝑛 ≡ 2(𝑚𝑜𝑑 4) 
The edge labels in the following functions are constructed to illustrate the upper bound of 

𝑟𝑣𝑎𝑐(𝐶𝑛).  

For 1 ≤ 𝑖 ≤
𝑛

2
, we have 

𝑔(𝑒𝑖) = {
2𝑖 − 1, 𝑖 ≡ 1(𝑚𝑜𝑑 2)

2𝑖, 𝑖 ≡ 0(𝑚𝑜𝑑 2)
 

 

For 
𝑛

2
+ 1 ≤ 𝑖 ≤ 𝑛, we have 

𝑔(𝑒𝑖) = {
2𝑖 − 𝑛, 𝑖 ≡ 0(𝑚𝑜𝑑 2)

2𝑖 − 𝑛 − 1, 𝑖 ≡ 1(𝑚𝑜𝑑 2)
 

 

We have the following vertex weights based on the edge labels above. 

𝑤(𝑥1) = 𝑤(
𝑛

2
+ 1) = 𝑛 + 1 

𝑤(𝑥𝑖) = 4𝑖 − 3:2 ≤ 𝑖 ≤
𝑛

2
 

𝑤(𝑥𝑖) = 4𝑖 − 2𝑛 − 3: 
𝑛

2
+ 2 ≤ 𝑖 ≤ 𝑛 

 

From the vertex weight above, we can determine the different weight in the Table 2. 

 
Table 2. The Different Weight on The Vertices of 𝐶𝑛. 

 

𝒊 𝒘(𝒊) 𝒊 𝒘(𝒊) 

1 𝑛 + 1 
𝑛

2
+ 1 

𝑛 + 1 

2 5 
𝑛

2
+ 2 

5 

3 9 
𝑛

2
+ 3 

9 

4 13 
𝑛

2
+ 4 

13 

5 17 
𝑛

2
+ 5 

17 

⋮ ⋮ ⋮ 
⋮ 

𝑛

2
 2𝑛 − 3 𝑛 

2𝑛 − 3 



Marsidi 

Developing A Secure Cryptosystem with Rainbow Vertex Antimagic Coloring of Cycle Graph 

83 
 

We know that the number of different weights of 𝐶𝑛 is 
𝑛

2
. It concludes that the upper 

bound of 𝑟𝑣𝑎𝑐(𝐶𝑛) is 
𝑛

2
. Furthermore, we prove that every pair of 𝐶𝑛 vertices have 

rainbow vertex antimagic coloring. Suppose that 𝑣 ∈ 𝑉(𝐶𝑛), Table 3 shows the rainbow 
vertex path in accordance with the vertex weight. 

 
Table 3. The Path of Rainbow Vertex on Cycle of Order 𝑛. 

 

Case 𝒖 𝒗 
Rainbow Vertex Coloring of 𝒖 − 𝒗 

Path 

𝑖 < 𝑗;𝑗 − 𝑖 ≤
𝑛

2
 

 
𝑣𝑖 𝑣𝑗 

𝑣𝑖,𝑣𝑖+1,𝑣𝑖+2, 𝑣𝑖+3, ⋯,𝑣𝑗−1, 𝑣𝑗 

𝑖 < 𝑗;𝑗 − 𝑖 >
𝑛

2
 𝑣𝑖 𝑣𝑗 

𝑣𝑗,𝑣𝑗+1 ,𝑣𝑗+2,⋯,𝑣𝑛 ,𝑣1,⋯,𝑣𝑖 

 
Case 2. For 𝑛 ≡ 0(𝑚𝑜𝑑 4) 
The edge labels in the following functions are constructed to illustrate the upper bound of 

𝑟𝑣𝑎𝑐(𝐶𝑛).  

For 1 ≤ 𝑖 ≤
𝑛

2
, we have 

𝑔(𝑒𝑖) = {
2𝑖 − 1, 𝑖 ≡ 1(𝑚𝑜𝑑 2)

2𝑖, 𝑖 ≡ 0(𝑚𝑜𝑑 2)
 

 

For 
𝑛

2
+ 1 ≤ 𝑖 ≤ 𝑛, we have 

𝑔(𝑒𝑖) = {
2𝑖 − 𝑛, 𝑖 ≡ 1(𝑚𝑜𝑑 2)

2𝑖 − 𝑛 − 1, 𝑖 ≡ 0(𝑚𝑜𝑑 2)
 

 

We have the following vertex weights based on the edge labels above. 
𝑤(𝑥1) = 𝑛 

𝑤(𝑥𝑖) = 4𝑖 − 3:2 ≤ 𝑖 ≤
𝑛

2
 

𝑤(
𝑛

2
+ 1) = 𝑛 + 2 

𝑤(𝑥𝑖) = 4𝑖 − 2𝑛 − 3: 
𝑛

2
+ 2 ≤ 𝑖 ≤ 𝑛 

 

From the vertex weight above, we can determine the different weight in the Table 4. 

 
Table 4. The Different Weight on The Vertices of 𝐶𝑛. 

 

𝒊 𝒘(𝒊) 𝒊 𝒘(𝒊) 

1 𝑛 
𝑛

2
+ 1 𝑛 + 2 

2 5 
𝑛

2
+ 2 5 

3 9 
𝑛

2
+ 3 9 

4 13 
𝑛

2
+ 4 13 

5 17 
𝑛

2
+ 5 17 

⋮ ⋮ ⋮ ⋮ 

𝑛

2
    2𝑛 − 3 𝑛 2𝑛 − 3 



Jurnal Matematika MANTIK  

Vol 8, No 2, October 2022, pp. 78-88 

84 

We know that the number of different weights of 𝐶𝑛 is 
𝑛

2
+ 1. It concludes that the upper 

bound of 𝑟𝑣𝑎𝑐(𝐶𝑛) is 
𝑛

2
+ 1. Furthermore, we prove that every pair of 𝐶𝑛 vertices have 

rainbow vertex antimagic coloring. Suppose that 𝑣 ∈ 𝑉(𝐶𝑛), Table 5 shows the rainbow 
vertex path in accordance with the vertex weight. 

 
Table 5. The Path of Rainbow Vertex on Cycle of Order 𝑛. 

 

Case 𝒖 𝒗 
Rainbow Vertex Coloring of 𝒖 − 𝒗 

Path 

𝑖 < 𝑗;𝑗 − 𝑖 ≤
𝑛

2
 𝑣𝑖 𝑣𝑗 𝑣𝑖,𝑣𝑖+1,𝑣𝑖+2, 𝑣𝑖+3, ⋯,𝑣𝑗−1, 𝑣𝑗 

𝑖 < 𝑗;𝑗 − 𝑖 >
𝑛

2
 𝑣𝑖 𝑣𝑗 𝑣𝑗,𝑣𝑗+1 ,𝑣𝑗+2,⋯,𝑣𝑛 ,𝑣1,⋯,𝑣𝑖 

 

 

Case 3. For 𝑛 ≡ 1(𝑚𝑜𝑑 4) 
The edge labels in the following functions are constructed to illustrate the upper bound of 

𝑟𝑣𝑎𝑐(𝐶𝑛).  

For 1 ≤ 𝑖 ≤ ⌈
𝑛

2
⌉, we have 

𝑔(𝑒𝑖) = {
2𝑖 − 1, 𝑖 ≡ 1(𝑚𝑜𝑑 2)

2𝑖, 𝑖 ≡ 0(𝑚𝑜𝑑 2)
 

𝑔(𝑒
⌈
𝑛
2
⌉
) = 𝑛 

For ⌈
𝑛

2
⌉ + 1 ≤ 𝑖 ≤ 𝑛, we have 

𝑔(𝑒𝑖) = {
2𝑖 − 𝑛 − 1, 𝑖 ≡ 0(𝑚𝑜𝑑 2)
2𝑖 − 𝑛 − 2, 𝑖 ≡ 1(𝑚𝑜𝑑 2)

 

 

We have the following vertex weights based on the edge labels above. 
𝑤(𝑥1) = 𝑛 − 1 

𝑤(𝑥𝑖) = 4𝑖 − 3:2 ≤ 𝑖 ≤ ⌈
𝑛

2
⌉ 

𝑤(⌈
𝑛

2
⌉ + 1) = 𝑛 + 2 

𝑤(𝑥𝑖) = 4𝑖 − 2𝑛 − 5: ⌈
𝑛

2
⌉ + 2 ≤ 𝑖 ≤ 𝑛 

 

From the vertex weight above, we can determine the different weight in the Table 6. 

 

Table 6. The Different Weight on The Vertices of 𝐶𝑛. 
 

𝒊 𝒘(𝒊) 𝒊 𝒘(𝒊) 

1 𝑛-1 ⌈
𝑛

2
⌉ + 1 𝑛 + 2 

2 5 ⌈
𝑛

2
⌉ + 2 5 

3 9 ⌈
𝑛

2
⌉ + 3 9 

4 13 ⌈
𝑛

2
⌉ + 4 13 

5 17 ⌈
𝑛

2
⌉ + 5 17 

⋮ ⋮ ⋮ ⋮ 

⌈
𝑛

2
⌉ 

 
2𝑛 − 1 𝑛 2𝑛 − 5 

 



Marsidi 

Developing A Secure Cryptosystem with Rainbow Vertex Antimagic Coloring of Cycle Graph 

85 
 

We know that the number of different weights of 𝐶𝑛 is ⌊
𝑛

2
⌋ + 2. It concludes that the 

upper bound of 𝑟𝑣𝑎𝑐(𝐶𝑛) is ⌊
𝑛

2
⌋ + 2. Furthermore, we prove that every pair of 𝐶𝑛 vertices 

have rainbow vertex antimagic coloring. Suppose that 𝑣 ∈ 𝑉(𝐶𝑛), Table 7 shows the 
rainbow vertex path in accordance with the vertex weight. 

 
Table 7. The Path of Rainbow Vertex on Cycle of Order 𝑛. 

 

Case 𝒖 𝒗 
Rainbow Vertex Coloring of 𝒖 − 𝒗 

Path 

𝑖 < 𝑗;𝑗 − 𝑖 ≤ ⌈
𝑛

2
⌉ 𝑣𝑖 𝑣𝑗 𝑣𝑖,𝑣𝑖+1,𝑣𝑖+2, 𝑣𝑖+3, ⋯,𝑣𝑗−1, 𝑣𝑗 

𝑖 < 𝑗;𝑗 − 𝑖 > ⌈
𝑛

2
⌉ 𝑣𝑖 𝑣𝑗 𝑣𝑗,𝑣𝑗+1 ,𝑣𝑗+2,⋯,𝑣𝑛 ,𝑣1,⋯,𝑣𝑖 

 

Case 4. For 𝑛 ≡ 3(𝑚𝑜𝑑 4) 
The edge labels in the following functions are constructed to illustrate the upper bound of 

𝑟𝑣𝑎𝑐(𝐶𝑛).  

For 1 ≤ 𝑖 ≤ ⌈
𝑛

2
⌉, we have 

𝑔(𝑒𝑖) = {
2𝑖 − 1, 𝑖 ≡ 1(𝑚𝑜𝑑 2)

2𝑖, 𝑖 ≡ 0(𝑚𝑜𝑑 2)
 

𝑔(𝑒
⌈
𝑛
2
⌉
) = 𝑛 

For ⌈
𝑛

2
⌉ + 1 ≤ 𝑖 ≤ 𝑛, we have 

𝑔(𝑒𝑖) = {
2𝑖 − 𝑛 − 1, 𝑖 ≡ 1(𝑚𝑜𝑑 2)
2𝑖 − 𝑛 − 2, 𝑖 ≡ 0(𝑚𝑜𝑑 2)

 

 

We have the following vertex weights based on the edge labels above. 

 
𝑤(𝑥1) = 𝑛 

𝑤(𝑥𝑖) = 4𝑖 − 3:2 ≤ 𝑖 ≤ ⌈
𝑛

2
⌉ − 1 

𝑤(⌈
𝑛

2
⌉) = 2𝑛 − 2 

𝑤(⌈
𝑛

2
⌉ + 1) = 𝑛 + 2 

𝑤(𝑥𝑖) = 4𝑖 − 2𝑛 − 5: ⌈
𝑛

2
⌉ + 2 ≤ 𝑖 ≤ 𝑛 

 

From the vertex weight above, we can determine the different weight in the Table 8. 

 
Table 8. The Different Weight on The Vertices of 𝐶𝑛. 

 

𝒊 𝒘(𝒊) 𝒊 𝒘(𝒊) 

1 𝑛 ⌈
𝑛

2
⌉ + 1 𝑛 + 2 

2 5 ⌈
𝑛

2
⌉ + 2 5 

3 9 ⌈
𝑛

2
⌉ + 3 9 

4 13 ⌈
𝑛

2
⌉ + 4 13 

5 17 ⌈
𝑛

2
⌉ + 5 17 

⋮ ⋮ ⋮ ⋮ 

⌈
𝑛

2
⌉ 2𝑛 − 2 𝑛 2𝑛 − 5 



Jurnal Matematika MANTIK  

Vol 8, No 2, October 2022, pp. 78-88 

86 

 

We know that the number of different weights of 𝐶𝑛 is ⌊
𝑛

2
⌋ + 1. It concludes that the 

upper bound of 𝑟𝑣𝑎𝑐(𝐶𝑛) is ⌊
𝑛

2
⌋ + 1. Furthermore, we prove that every pair of 𝐶𝑛 vertices 

have rainbow vertex antimagic coloring. Suppose that 𝑣 ∈ 𝑉(𝐶𝑛), Table 9 shows the 
rainbow vertex path in accordance with the vertex weight. 

 
Table 9. The Path of Rainbow Vertex on Cycle of Order 𝑛. 

 

Case 𝒖 𝒗 
Rainbow Vertex Coloring of 𝒖 − 𝒗 

Path 

𝑖 < 𝑗;𝑗 − 𝑖 ≤ ⌈
𝑛

2
⌉ 𝑣𝑖 𝑣𝑗 𝑣𝑖,𝑣𝑖+1,𝑣𝑖+2, 𝑣𝑖+3, ⋯,𝑣𝑗−1, 𝑣𝑗 

𝑖 < 𝑗;𝑗 − 𝑖 > ⌈
𝑛

2
⌉ 𝑣𝑖 𝑣𝑗 𝑣𝑗,𝑣𝑗+1 ,𝑣𝑗+2,⋯,𝑣𝑛 ,𝑣1,⋯,𝑣𝑖 

 
As a result, the vertex coloring on 𝐶𝑛 is rainbow vertex antimagic coloring. Thus, we 
obtain  

𝑟𝑣𝑎𝑐(𝐶𝑛) ≤

{
 
 

 
 

𝑛

2
, 𝑖𝑓 𝑛 ≡ 2(𝑚𝑜𝑑 4)

𝑛

2
+ 1, 𝑖𝑓 𝑛 ≡ 0(𝑚𝑜𝑑 4)

⌊
𝑛

2
⌋ + 2, 𝑖𝑓 𝑛 ≡ 1(𝑚𝑜𝑑 4)

⌊
𝑛

2
⌋ + 1, 𝑖𝑓 𝑛 ≡ 3(𝑚𝑜𝑑 4)

. ∎ 

 

3.2 Application 

The encryption and decryption process can implement the result of labeling and the 

chromatic number of rainbow vertex coloring, which is used as the key for the encryption 

and decryption process. We developed a new algorithm to generate encryption and 

decryption keys with rainbow vertex antimagic chromatic numbers and labels. 

Algorithm 1. Role of Extra Key 

a) Define 𝑓 as the function of graph element labels of graph 𝐺. 
b) If 𝑓 is a bijective function, do 3, and bring it back to 1 otherwise. 
c) Define 𝑏 as the rainbow vertex antimagic chromatic number.  
d) To use the vertex weight, define 𝑧𝑖

1:1 ≤ 𝑖 ≤ 𝑛, where 𝑛 is the number of vertexes. 

e) Add 𝑧𝑖
1 and arrange the sequence according to the vertex notation 𝑥𝑖: 1 ≤ 𝑖 ≤ 𝑛, 

where 𝑛 is the number of vertices. 
f) To use the edge label, define 𝑧𝑗

2:1 ≤ 𝑗 ≤ 𝑚, where 𝑚 is the number of edges. 

g) Add 𝑧𝑗
2 and arrange the sequence according to the edge notation 𝑒𝑗:1 ≤ 𝑗 ≤ 𝑚. 

h) Set 𝑘 as element of the 𝑧𝑖
1 and 𝑧𝑗

2 sequence. 

In Algorithm 1, it will use the process of developing the key in the encryption and 

decryption process. Algorithm 2 developed the Affine Cipher based on the results of 

Algorithm 1, which includes an encryption and description process.  

  



Marsidi 

Developing A Secure Cryptosystem with Rainbow Vertex Antimagic Coloring of Cycle Graph 

87 
 

Algorithm 2. Modified Affine Cipher  

a) Given that the plaintext and its conversion with Affine Cipher  𝑃𝑖: 1 ≤ 𝑖 ≤ 𝑛. 
b) Compute the ciphertext using Equation 1 and compute the plaintext blocks using 

Equation 2. 

 Φ𝑖 = ((𝑃𝑖 + 𝐾1𝑖) + 𝐾2𝑖) 𝑚𝑜𝑑 26  (1)  

 𝑃𝑖 = ((Φ𝑖 − 𝐾2𝑖) − 𝐾1𝑖) 𝑚𝑜𝑑 26 (2) 

where 𝑃𝑖, 𝐾1𝑖, 𝐾2𝑖, and Φ𝑖 are the 𝑖-th of conversion plaintext, key sequence, and 
conversion ciphertext, respectively. Note that, for 𝑛 = 1, Φ𝑛−1 is a null vector. 

For an illustration how the algorithms are working, we give the following examples. 

Given that a plaintext 𝑃 = 𝑈𝑁𝐼𝑃𝐴𝑅𝐽𝐸𝑀𝐵𝐸𝑅, by mean the two algorithms above we 
have a ciphertext Φ = 𝐻𝑊𝑊𝐾𝐴𝑌𝑍𝑀𝐵𝑉𝐹𝑋. The cryptosystem process can be described 
in the following tables. 

Table 9. Encryption process. 

Plaintext 𝑼 𝑵 𝑰 𝑷 𝑨 𝑹 𝑱 𝑬 𝑴 𝑩 𝑬 𝑹 

𝑃𝑖 20 13 8 15 0 17 9 4 12 1 4 17 

𝐾1𝑖 12 5 9 13 17 21 14 5 9 13 17 21 

𝑃𝑖 + 𝐾1𝑖 32 18 17 28 17 38 23 9 21 14 21 38 

𝐾2𝑖 1 4 5 8 9 12 2 3 6 7 10 11 

(𝑃𝑖 + 𝐾1𝑖) + 𝐾2𝑖 33 22 22 36 26 50 25 12 27 21 31 49 

Φ𝑖 7 22 22 10 0 24 25 12 1 21 5 23 

Ciphertext 𝑯 𝑾 𝑾 𝑲 𝑨 𝒀 𝒁 𝑴 𝑩 𝑽 𝑭 X 

 

Table 10. Decryption process. 

Ciphertext 𝑯 𝑾 𝑾 𝑲 𝑨 𝒀 𝒁 𝑴 𝑩 𝑽 𝑭 X 

Φ𝑖 7 22 22 10 0 24 25 12 1 21 5 23 

𝐾2𝑖 1 4 5 8 9 12 2 3 6 7 10 11 

Φ𝑖 − 𝐾2𝑖 6 18 17 2 -9 12 23 9 -5 14 -5 12 

𝐾1𝑖 12 5 9 13 17 21 14 5 9 13 17 21 

(Φ𝑖 − 𝐾2𝑖) − 𝐾1𝑖 -6 13 8 -11 -26 -9 9 4 -14 1 -22 -9 

𝑃𝑖 20 13 8 15 0 17 9 4 12 1 4 17 

Plaintext 𝑼 𝑵 𝑰 𝑷 𝑨 𝑹 𝑱 𝑬 𝑴 𝑩 𝑬 𝑹 

 

4. Conclusions  

We have determined the upper bound of 𝑟𝑣𝑎𝑐(𝐶𝑛). Since determining the 𝑟𝑣𝑎𝑐 of a 
graph is considered a Non-Deterministic Polynomial Time-complete problem, the exact 

value of any graph 𝐺 remains unsolved. As a result, we offer the following open 
problems.  

a) Find the exact value of the cycle graph's rainbow vertex antimagic connection 
number. 

b) Find the exact value of any graph's rainbow vertex antimagic connection number. 



Jurnal Matematika MANTIK  

Vol 8, No 2, October 2022, pp. 78-88 

88 

5. Acknowledgments  

We would like to thank the Department of Mathematics Education, Universitas 

PGRI Argopuro Jember, CGANT University of Jember in 2022, and the reviewers that 

helped us finish this research. 

References 

[1] G. Chartrand, L. Lesniak, and P. Zhang, Graphs & Digraphs, Fifth Edition. 2010. 

[2] M. Krivelevich and R. Yuster, “The rainbow connection of a graph is (at most) 

reciprocal to its minimum degree,” J. Graph Theory, vol. 63, pp. 185–191, 2010. 

[3] D. N. S. Simamora and A. N. M. Salman, “The Rainbow (Vertex) Connection 

Number of Pencil Graphs,” Procedia Comput. Sci., vol. 74, pp. 138–142, 2015, 

doi: 10.1016/j.procs.2015.12.089. 

[4] G. Chartrand, G. L. Johns, K. A. McKeon, and P. Zhang, “Rainbow connection in 

graphs,” Math. Bohem., vol. 133, pp. 85–98, 2008. 

[5] G. Chartrand, G. L. Johns, K. A. McKeon, and P. Zhang, “The rainbow 

connectivity of a graph,” Networks, 2009, doi: 10.1002/net.20296. 

[6] Dafik, I. H. Agustin, A. Fajariyato, and R. Alfarisi, “On the rainbow coloring for 

some graph operations,” vol. 020004, 2016, doi: 10.1063/1.4940805. 

[7] X. Li and Y. Sun, “An Updated Survey on Rainbow Connections of Graphs- A 

Dynamic Survey,” Theory Appl. Graphs, 2017, doi: 10.20429/tag.2017.000103. 

[8] M. S. Hasan, Slamin, Dafik, I. H. Agustin, and R. Alfarisi, “On the total rainbow 

connection of the wheel related graphs,” 2018. 

[9] P. Heggernes, D. Issac, J. Lauri, P. T. Lima, and E. J. Van Leeuwen, “Rainbow 

vertex coloring bipartite graphs and chordal graphs,” Leibniz Int. Proc. 

Informatics, LIPIcs, vol. 117, no. 83, pp. 1–13, 2018, doi: 

10.4230/LIPIcs.MFCS.2018.83. 

[10] Dafik, Slamin, and A. Muharromah, “On the ( Strong ) Rainbow Vertex 

Connection of Graphs Resulting from Edge Comb Product,” 2018. 

[11] B. J. Septory, M. I. Utoyo, Dafik, B. Sulistiyono, and I. H. Agustin, “On rainbow 

antimagic coloring of special graphs,” J. Phys. Conf. Ser., vol. 1836, no. 1, 2021, 

doi: 10.1088/1742-6596/1836/1/012016. 

[12] Marsidi, I. H. Agustin, Dafik, and E. Y. Kurniawati, “On Rainbow Vertex 

Antimagic Coloring of Graphs: A New Notion,” CAUCHY – J. Mat. Murni dan 

Apl., vol. 7, no. 1, pp. 64–72, 2021. 

[13] Dafik, F. Susanto, R. Alfarisi, I. H. Agustin, and M. Venkatachalam, “On 

Rainbow Antimagic Coloring Of Graphs,” Adv. Math. Model. Appl., vol. 6, no. 3, 

pp. 278–291, 2021. 

[14] H. S. Budi, Dafik, I. M. Tirta, I. H. Agustin, and A. I. Kristiana, “On rainbow 

antimagic coloring of graphs,” J. Phys. Conf. Ser., vol. 1832, no. 1, 2021, doi: 

10.1088/1742-6596/1832/1/012016. 

[15] A. C. Prihandoko, D. Dafik, and I. H. Agustin, “Implementation of super H-

antimagic total graph on establishing stream cipher,” Indones. J. Comb., vol. 3, no. 

1, p. 14, 2019, doi: 10.19184/ijc.2019.3.1.2. 

[16] A. C. Prihandoko, Dafik, and I. H. Agustin, “Stream-keys generation based on 

graph labeling for strengthening Vigenere encryption,” Int. J. Electr. Comput. 

Eng., vol. 12, no. 4, pp. 3960–3969, 2022, doi: 10.11591/ijece.v12i4.pp3960-

3969.