University of Southeastern Philippines, Philippines
* Corresponding author
University of Southeastern Philippines, Philippines

Article Main Content

Let G be the graph. A topological cordial labeling of a graph G with |V (G)| = n is an injective function f from the vertex set V(G) to the set 2X where X is a nonempty set such that |X| < n and it forms a topology on X, denoted by {f (V (G))}, that induced a function f ∗ from E (G) → {0, 1} defined by

f (uv) = {1 0 if f (u) f (v)is not an empty set and not a singleton set, 0 otherwise

for all uv E (G) such that  |ef (0) ef (1) | ≤ 1 where ef (0) is the number of vertices labeled with 0 and where ef (1) is the number of vertices labeled with 1. The graph that satisfies the condition of a topological cordial labeling is called topological cordial graph.

Introduction

In this paper, the graphs considered were finite and undirected. Graph G consists of a set V of vertices and a collection E of unordered pairs. For such notations and terminologies, we refer to Balakrishnan [1]. Graph labeling is an assignment of integers to vertices, or edges, or both, under certain conditions [2]. Graph Labeling has various applications such as x-ray, coding theory, radar, circuits, etc. Cordial Labeling is a graph labeling in which the possible choices to be labeled are either 0 or 1 of the edges and vertices of a certain graph. Cordial Labeling occurs in many ways depending on the condition that must be considered. Cordial Labeling was introduced by Cahit in 1987 as a weaker version of harmonious and graceful graphs [3].

Topological cordial labelling was introduced by Selistin et al. in 2020 [4] and 2021 [5] and Prijith et al. in 2023 [6]. A graph is called a topological cordial graph subject to certain condition, that is, the function f is an injective that maps from the vertex set of G to 2X where X is the nonempty set such that the cardinality is less than the vertex set of G and it forms a topology on X that induces a function f defined by

f ( u v ) = { 1 i f   f ( u ) f ( v )   i s   n o t   a n   e m p t y   s e t   a n d   n o t   a   s i n g l e t o n   s e t 0 o t h e r w i s e ,

for all uvE(G) such that |ef(0)ef(1)|1 where ef(0) is the number of vertices labeled with 0 and where ef(1) is the number of vertices labeled with 1. The graph that satisfies the condition of a topological cordial labeling is called topological cordial graph. In this paper, we discuss the Topological cordial labeling.

Basic Concepts

Definition 1. [7] Let X be the set. A topology (or topological structure) in X is a family ???? of subsets of X that satisfies:

i) and ???? are members of ????.

ii) Each union of members of ???? is also a member of ????.

iii) Each finite intersection of members of ???? is also a member of ????.

A set X for which a topology ???? has been specified is called topological space.

Definition 2. [6] A topological cordial labeling of a graph G with |V(G)|=n is an injective function f from the vertex set V(G) to the set 2X where X is a nonempty set such that |X|<n and it forms a topology on X, denoted by {f(V(G))}, that induced a function f from E(G){0,1} defined by

f ( u v ) = { 1 i f   f ( u ) f ( v )   i s   n o t   a n   e m p t y   s e t   a n d   n o t   a   s i n g l e t o n   s e t 0 o t h e r w i s e

for all uvE(G) such that |ef(0)ef(1)|1 where ef(0) is the number of vertices labeled with 0 and where ef(1) is the number of vertices labeled with 1. The graph that satisfies the condition of a topological cordial labeling is called topological cordial graph.

Definition 3. [8] A Bi-star graph Bn,n is a graph obtained by joining graph obtained by joining the center vertices of two copies of K1,n by an edge. The vertex set of Bn,n is V(Bn,n)={u,v,ui,vi|1in}, where u,v are the center vertices and ui,vi are pendant vertices. The edge set of Bn,n is E(B(n,n))={uv,uui,vvi|1in} so, |V(Bn,n)|=2n+2 and |E(Bn,n)|=2n+1.

Definition 4. [8] The Splitting Graph S(G) of a graph G is constructed by adding to each vertex v, a new vertex v such that v is adjacent to every vertex that is adjacent to v, that is, N(v)=N(v).

Definition 5. [9] Let G=(V(G),E(G)) be a graph with V=S1S2SiT where each Si is the set of vertices having at least two vertices of the same degree and T=VSi. The degree splitting graph of G denoted by DS(G) is obtained from G by adding vertices w1,w2,,wt and joining to each vertex of Si for 1it.

Definition 6. [10] A Firecracker Graph Fm,n is the graph obtained by the concatenation of mn-stars by linking on leaf from each. Firecracker graph Fm,n is the graph with (n + 1) m order and (n + 1) m − 1 size, consisting of vertex set V(Fm,n)={ui|1im}{vi,j|1im,1jn} and edge set E(Fm,n)={uivi,j|1im,1jn}{vi,1v(i+1),1|1im1}.

Definition 7. [11] The Banana Tree Graph BNn,k is the graph obtained by connecting one leaf of each of n copies of a k-star graph with a single root vertex that is distinct for all the stars. The BNn,k has order nk+1 and size nk.

Definition 8. [12] The Jellyfish Graph Jm,n is obtained from 4-cycle u,v,w,x by joining u and v with an edge and appending m pendant edges {v1,v2,,vm} to v and n pendant edges {x1,x2,,xn} to x.

Results and Discussions

Theorem 1. Let G be a graph with n vertices and let Yn1={1,2,3,,n1}. Then

???? = { , { 1 } , { 1 , 2 } , , { 1 , 2 , 3 , , n 1 } }

is a topology on Yn1.

Proof: Let G be the graph of order n. Suppose that Yn1={1,2,3,,n1} and let the set ????={Y0,Y1,Y2,,Yn1} where

Y 0 = Y 1 = { 1 } Y 2 = { 1 , 2 } Y n 2 = { 1 , 2 , 3 , , n 2 } Y n 1 = { 1 , 2 , 3 , , n 1 } .

Note that YiYj if i<j. By Definition 1,

i) and Yn1 is in ????. Hence, the first condition is satisfied.

ii) Let I={0,1,2,,n1} and suppose {Yα:αI} is a collection of elements of ???? and let J be a subset of I. We want to show that

α J Y α ????

Let mJ such that αm for every αJ. Then

α J Y α = Y m ????

Hence, the arbitrary union of the elements of any subcollection of ???? is in ????.

iii) Suppose JI. Let sJ such that sα for every αJ. Then

α J Y α = Y s ????

Hence, the intersection of any finite subcollection of ???? is in ????.

Thus, three conditions are satisfied, therefore, ???? is a topology on Yn1, that is,

???? = { , { 1 } , { 1 , 2 } , , { 1 , 2 , 3 , , n 1 } }

is a topology on Yn1.

Theorem 2. A Splitting of a Bi-star Graph Bn,n is a topological cordial graph for all nN.

Proof: Suppose S(Bn,n) is the splitting of a bi-star graph Bn,n. Let V(S(Bn,n))=V(Bn,n){u,v,ui,vi|1in} be a vertex set of S(Bn,n). The order of S(Bn,n) is 4n+4. Also, let E(S(Bn,n))=E(Bn,n){uv,vu,uuivviuvivvi|1in}be the edge set of E(S(Bn,n)). The size of S(Bn,n) is 6n+3. Now, let X={1,2,3,,4n+3} and suppose that

???? = { , { 1 } , { 1 , 2 } , , { 1 , 2 , , 4 n + 2 } } .

According to Theorem 1, ???? is a topology on X. Now, the function f:V(DS(Bn,n))???? is defined by

f ( v ) = { 1 , 2 } , f ( u ) =

f ( u ) = { 1 , 2 , 4 n + 3 } , f ( v ) = { 1 }

f ( u i ) = { 1 , 2 , , i + 2 } for 1 i n ,

f ( v i ) = { 1 , 2 , , n + i + 2 } for 1 i n ,

f ( u i ) = { 1 , 2 , , 2 n + i + 2 } for 1 i n ,

f ( v i ) = { 1 , 2 , , 3 n + i + 2 } for 1 i n .

Thus, the induced edge labels are

f ( u v ) = 0 , f ( u v ) = 0 ,

f ( u v ) = 1 ,

f ( u u i ) = 0 for 1 i n ,

f ( u u i ) = 0 for 1 i n ,

f ( v v i ) = 1 for 1 i n ,

f ( u u i ) = 1 for 1 i n ,

f ( v v i ) = 1 for 1 i n ,

f ( v v i ) = 1 for 1 i n ,

It can be observed that ef(0)=3n+2 and ef(1)=3n+1. Thus |ef(0)ef(1)|=|3n+2(3n+1)|=1. Therefore, the Splitting of a Bi-star Graph S(Bn,n) is a topological cordial graph for nN.

Theorem 3. A Degree Splitting of a Bistar Graph DS(Bn,n) is a topological cordial graph for all nN.

Proof: Suppose DS(Bn,n) is the degree splitting of a bistar graph Bn,n. Let the vertex set V(DS(Bn,n))=V(Bn,n){w1,w2,ui,vi|1in}. The order of DS(Bn,n) is 2n+4. In addition, let the edge set E(DS(Bn,n))=E(Bn,n){w1ui,w1vi,uw2,vw2|1in}. The size of DS(Bn,n) is 4n+3. Now, let X={1,2,3,,4n+3} and suppose ????={,{1},{1,2},,{1,2,,4n+2}}. By Theorem 1, ???? is a topology on X. Now, the function f:V(DS(Bn,n))???? is defined by:

f ( w 1 ) = f ( w 2 ) = { 1 }

f ( u ) = { 1 , 2 , 2 n + 2 } ,

f ( v ) = { 1 , 2 , , 2 n + 3 } ,

f ( u i ) = { 1 , 2 , , i + 1 } for 1 i n ,

f ( v i ) = { 1 , 2 , , n + i + 1 } for 1 i n ,

Thus, the induced edge labels are:

f ( w 2 u ) = 0 , f ( w 2 v ) = 0 , f ( u v ) = 1 ,

f ( w 1 u i ) = 0 for 1 i n , f ( w 1 v i ) = 0 for 1 i n ,

f ( v v i ) = 1 for 1 i n , f ( u u i ) = 1 for 1 i n .

It can be observed that ef (0) = 3n + 2 and ef (1) = 3n + 1. Thus |ef(0)ef(1)|=|3n+2(3n+1)|=1. Therefore, the Splitting of a Bi-star Graph S(Bn,n) is a topological cordial graph for nN.

Theorem 4. A Firecracker Graph Fm,n where n=2 and nN is a topological cordial graph.

Proof: Suppose Fm,n is a firecracker graph where n=2 and nN and assume V(F2,n)={u1,u2,u1,j,u2,j|1jn} be the vertex set of F2,n. The order of F2,n is 2(n+1)1. Also, let E(F2,n)={uiui,j|1i2,1jn}{u1,1u2,1} be an edge set of F2,n. The size of F2,n is 2(n+1)1. Moreover, assume that X={1,2,3,,2n+1} and suppose ????={,{1},{1,2},,{1,2,,2n}}. By Theorem 1, ???? is a topology on X. Now, the function f:V(F2,n)???? is defined by:

f ( x ) = { 1 , 2 , , 2 k } , f ( x 1 ) = ,

f ( x 2 ) = { 1 , 2 , k } ,

f ( x 1 , j ) = { 1 , 2 , , j } for 1 j k 1 ,

f ( x 2 , j ) = { 1 , 2 , , k + j } for 1 j k 1.

Thus, the induced edge labels are:

f ( x x 2 , 1 ) = 1 , f ( x x 1 , 1 ) = 0 ,

f ( x 1 x 1 , j ) = 0 for 1 j k 1 ,

f ( x 2 x 2 , j ) = 1 for 1 j k 1.

It can be observed that ef(0)=n+1 and ef(1)=n. Thus |ef(0)ef(1)|=|n+1n|=1. Therefore, the Firecracker Graph Fm,n where m=2 and nN is a topological cordial graph.

Theorem 5. A Banana Tree Graph BNn,k where n=2 and is a topological cordial graph for all nN.

Proof: Suppose BNn,k is a banana tree graph where n=2 and kN and let the vertex set V(BN2,k)={x,x1,x2,x1,j,x2,j|1jk1}. The order of BN2,k is 2k+1. In addition, suppose that edge set E(BN2,k)={x1x1,j,x2x2,j|1jk1}{xx1,1,xx2,1}. The size of BN2,k is 2k. Now, assume X={1,2,,2k} and suppose ????={,X,{1},{1,2},,{1,2,,2k1}}. According to Theorem 1, ???? is a topology on X. Now, the function f:V(BN2,k)???? is defined by:

f ( x ) = { 1 , 2 , , 2 k } , f ( x 1 ) = ,

f ( x 2 ) = { 1 , 2 , k } ,

f ( x 1 , j ) = { 1 , 2 , , j } for 1 j k 1 ,

f ( x 2 , j ) = { 1 , 2 , , k + j } for 1 j k 1.

Thus, the induced edge labels are:

f ( u 1 , 1 u 2 , 1 ) = 0 ,

f ( u 1 u 1 , j ) = 0 for 1 j n ,

f ( u 2 u 2 , j ) = 1 for 1 j n .

It can be observed that ef(0)=k and ef(1)=k. Thus |ef(0)ef(1)|=|kk|=0<1. Therefore, the Banana Tree Graph BNn,k where n=2 and kN is a topological cordial graph.

Theorem 6. A Jellyfish Graph Jm,n is a topological cordial graph for mn=i where i=0,1,2 and for m,nN.

Proof: Suppose Jm,n is a Jellyfish graph. To prove this theorem, we consider the following cases:

Case 1: mn=0.

Let V(Jm,m)={u,v,w,x}{vi,xi|1im}. The order of Jm,m is 2m+4. Furthermore, let E(Jm,m)={uv,vw,uw,wx}{vvi,xxi|1im}. The size of Jm,m is 2m+5. Now, let X={1,2,,2m+3} and assume that ????={,X,{1},{1,2},,{1,2,,2m+2}}. By Theorem 1, ???? is a topology on X. Define the function f:V(Jm,m)???? by:

f ( u ) = { 1 , 2 , , m + 2 } , f ( v ) = ,

f ( x ) = { 1 , 2 , , m + 3 } , f ( w ) = { 1 , 2 , , m + 1 } ,

f ( v i ) = { 1 , 2 , , i } for 1 i m ,

f ( x j ) = { 1 , 2 , , m + i + 3 } for 1 i n .

Thus, the induced edge labels are:

f ( u x ) = 1 , f ( u v ) = 0 ,

f ( v w ) = 0 , f ( u w ) = 1 , f ( w x ) = 1 ,

f ( v v i ) = 0 , for 1 i n ,

f ( x x j ) = 1 , for 1 i n .

It can be observed that ef(0)=m+2 and ef(1)=m+3. Thus |ef(0)ef(1)|=|m+2(m+3)|=1. Hence, if mn=0, the Jellyfish Graph Jm,m is a topological cordial graph.

Case 2: mn=1.

Let V(Jm,n)={u,v,w,x}{vi,xj|1in+1,1jn}. The order of Jm,n is 2n+5. In addition, let E(Jm,n)={uv,vw,uw,wx}{vvi,xxj|1in+1,1jn}. The size of Jm,n is 2m+6. Now, let X={1,2,,2m+4} and assume that ????={,X,{1},{1,2},,{1,2,,2m+3}}. By Theorem 1, ???? is a topology on X. Define the function f:V(Jm,m)???? by:

f ( u ) = { 1 , 2 , , n + 3 } , f ( v ) = ,

f ( x ) = { 1 , 2 , , n + 4 } , f ( w ) = { 1 , 2 , , n + 2 } ,

f ( v i ) = { 1 , 2 , , i } , for 1 i n + 1 ,

f ( x j ) = { 1 , 2 , , m + i + 4 } , for 1 j n .

Thus, the induced edge labels are:

f ( u x ) = 1 , f ( u v ) = 0 ,

f ( v w ) = 0 , f ( u w ) = 1 ,

f ( v v i ) = 0 for 1 i n + 1 f ( w x ) = 1

f ( x x j ) = 1 for 1 j n .

Observe that ef(0)=n+3 and ef(1)=n+3. Thus |ef(0)ef(1)|=|n+3(n+3)|=0. Hence, if mn=1, the Jellyfish Graph Jm,m is a topological cordial graph.

Case 3: mn=2.

Let V(Jm,n)={u,v,w,x}{vi,xj|1in+2,1jn}. The order of Jm,n is 2n+6. In addition, let E(Jm,n)={uv,vw,uw,wx}{vvi,xxj|1in+2,1jn}. The size of Jm,n is 2m+7. Now, let X={1,2,,2m+5} and assume that ????={,X,{1},{1,2},,{1,2,,2m+4}}. By Theorem 1, ???? is a topology on X. Define the function f:V(Jm,m)???? by:

f ( u ) = { 1 , 2 , , n + 4 } , f ( v ) = ,

f ( x ) = { 1 , 2 , , n + 5 } , f ( w ) = { 1 , 2 , , n + 3 } ,

f ( v i ) = { 1 , 2 , , i } , for 1 i n + 2 ,

f ( x j ) = { 1 , 2 , , n + i + 5 } , for 1 j n .

Thus, the induced edge labels are:

f ( u x ) = 1 f ( u v ) = 0 ,

f ( v w ) = 0 f ( u w ) = 1 ,

f ( v v i ) = 0 for 1 i n + 2 f ( w x ) = 1

f ( x x j ) = 1 for 1 j n

It can be observed that ef(0)=n+4 and ef(1)=n+3. Thus |ef(0)ef(1)|=|n+4(n+3)|=1. Hence, if mn=2, the Jellyfish Graph Jm,n is a topological cordial graph.

Considering the cases above, we can say that Jellyfish Graph Jm,n for mn=i where i=0,1,2 is a topological cordial graph.

References

  1. [1] Balakrishnan VK. Schaum’s Outline of Theory and Problems of Graph Theory. McGraw-Hill Companies Inc; 1997.
     Google Scholar
  2. [2] Ahmad MS, Nazeer W, Kang SM, Jung CY. M-polynomials and degree based topological indices for the line graph of firecracker graphs. GJPAM. 2017;13(6):2749–76.
     Google Scholar
  3. [3] Cahit I. Cordial graphs: a weaker version of graceful and harmoniuos graphs. Acs. 1987;23:201-8.
     Google Scholar
  4. [4] Selistin S, Asha S. On topological cordial graphs. JST. 2020;5(1):25–8.
     Google Scholar
  5. [5] Selistin S, Asha S. Topological cordial labelling of some graphs. MJM. 2021;9(1):861–33.
     Google Scholar
  6. [6] Prijith GS, Subbulakshmi M, Chandrakala S. On topological cordial labelling of some graphs. MJS. 2023;22(1):139–50.
     Google Scholar
  7. [7] Dugundji J. Topology. Ally and Bacon Inc; 1996.
     Google Scholar
  8. [8] Ghodasara GV, Patel MJ. Some bistar related square of graphs. IJMTT. 2017;47(3):172–7.
     Google Scholar
  9. [9] Vaidya SK, Shah NH. Cordial labeling of some bistar graph. IJMSC. 2014;4(2):33–9.
     Google Scholar
  10. [10] Chen WC, Lu HI, Yeh YN. Operations of interlaced trees and graceful trees. SAB. 1997;21:337-8.
     Google Scholar
  11. [11] Ahmad MS, Nazeer W, Kang SM, Jung CY. Some computational aspect of the line graph of banana tree. GJPAM. 2017;13(6):2601–27.
     Google Scholar
  12. [12] Girija L, Karthikeyan M. Magic and antimagic labeling of copies of jelly fish graph. JHUST. 2021;50(1):1.
     Google Scholar