A directed graph, also known as a digraph, is a graph in which each edge has direction. A linear directed cycle, Cm is a cycle whose all edges have the same direction. A linear directed graph is called directed cordial if it preserves binary or 0 - 1 labeling under certain condition. This paper dealt with directed cordial labeling of directed cycle Cm and square of directed Cm. We investigate directed path joining two copies of directed cycle Cm and directed square cycle Cm2 is directed cordial. Further we show that the directed path union of of rcopies of directed cycle and directed square cycle graph Cm2 is cordial under certain condition. Directed cycle, directed square cycle, cordial graph, directed cordial graph Graph theory is an important domain of discrete mathematics with voluminous applications in various streams. Graph labeling is an allotment of labels to edges or vertices or both. Numerous graph labeling schemes are studied and researched by many researchers. Gallian [3] reviewed and surveyed various labeling schemes invented by many researchers. In graph theory cordial labeling plays a vital role. It has ample of applications in many streams such as computer science, networking and communication network. Cahit [1] introduced cordial labeling in 1958. The directed cordial labeling of directed path was investigated and studied by Al-Shamiri [5] in 2019. He proved many results on linear directed path in the context of some graph operations are directed cordial. We study directed cordial labeling of directed cycle and their square subject to certain conditions. An overview provided on basic terminology and notations is needed for the presentation of our results. In the present work, we consider the W is directed graph.
2.2.
2022 Copyright for this paper by its authors.
(0) and (
A path Pr = b0, b1….br-1 is an alternating sequence of different vertices with r – 1 length. The linear directed path Pr have the same orientation. (clockwise or anticlockwise).
A cycle Cm is a closed path. A cycle is said to be linear directed cycle Cm if all its edges have the same direction. (clockwise or anticlockwise).
A linear directed cycle graph Cm on m vertices is called directed square cycle graph if each pair of vertex has distance less than or equal to two. We denote directed square cycle graph as Cm2 . The graph W = {2-Cm : Pr } is constructed with merging two same copies of directed cycle graph with indefinite path length . We denote W = {r-Cm : Pr } as path union of r same copies of directed cycle graph.
Case I For m ≡ 0, 1 (mod4) Case II For m ≡ 2, 3 (mod4)
0 ; p = 0, 2 (mod4) = { 1 ; p = 1, 3(mod4)
Edges Pattern
(0) = (
The corresponding observed cases of m with labeling pattern of edges and vertices resulted in
above table. Therefore, the conditions | (0) − (
Example 1. The directed cordiality of C6 is elaborated as shown in Figure 1.
Theorem 3.2. The linear directed square cycle Cm2, m ≥ 6 is directed cordial.
Proof: Let t1, t2, . . . tm successive vertices of directed square cycle Cm.
For m ≡ 0, 2, 4 (mod6)
The corresponding observed cases of m with labeling pattern of edges and vertices resulted in
above table. Therefore, the conditions | (0) − (
Example 2. The directed cordiality C62 is elaborated as shown in Figure 2. Proof: Let us denote 1st and 2nd copies of m-pan as t1, t2, . . .tm and s1, s2 . . . sm respectively. Let the vertices 1st, 2nd and r th of path Pr be represented by x1, x2, . . . , xr which carries condition as first vertex x1 = t1 and r th vertex, xr = s1.
Case I For r ≡ 0(mod4), m ≡ 0, 1 (mod4)
0 ; p = 0, 3(mod4) (tp) = { 1 ; p = 1, 2(mod4)
0 ; p = 1, 2(mod4) (sp) = {1 ; p = 0, 3 (mod4)
0 ; p = 0, 3(mod4) (xp) = {1 ; p = 1, 2(mod4) Case II For r ≡ 1(mod4), m ≡ 0 (mod4)
0 ; p = 0, 3(mod4) (tp) = (sp) = { 1 ; = 1, 2( 4)
0 ; p = 0, 3(mod4) (xp) = {1 ; = 1, 2( 4) Case III For r ≡ 2 (mod4), m ≡ 0, 1 (mod4)
0 ; p = 0, 3(mod4) (tp) = { 1 ; p = 1, 2(mod4)
0 ; p = 1, 2(mod4) (sp) = {1 ; p = 0, 3 (mod4)
0 ; p = 0, 2(mod4) (xp) = {1 ; p = 1, 3(mod4)
0 ; p = 0, 3(mod4) (tp) = { 1 ; p = 1, 2(mod4) (sp) = {10 ;; pp == 01,,32((mmoodd44))
0 ; p = 2, 3(mod4) (xp) = {1 ; p = 0, 1(mod4) Case IV For r ≡ 3 (mod4), m ≡ 0, 1 (mod4)
Case V For r ≡ 0(mod4), m ≡ 2, 3 (mod4)
0 ; p = 0, 2(mod4) (tp) = { 1 ; p = 1, 3(mod4)
0 ; p = 1, 3(mod4) (sp) = {1 ; p = 0, 2 (mod4) 0 ; p = 0, 3(mod4) (xp) = { 1 ; p = 1, 2(mod4) Case VI For r ≡ 1(mod4), m ≡ 2 (mod4) Case VIII For r ≡ 3 (mod4), m ≡ 2, 3 (mod4)
The corresponding observed cases of m with labeling pattern of edges and vertices resulted in
above table. Therefore, the conditions | (0) − (
Example 3 The graph W = {2-C5 : P6 } elaborated in Figure 3 is directed cordial. Theorem 3.4. The graph W = {r-Cm : Pr }is directed cordial.
Proof. Consider the vertices of 1st, 2nd , . . . , r th copy graph as tp1, tp2, . . . , tpr. Let x1, x2, . . . , xr be the vertices of path Pr with condition x1 = tp1, x2 = tp2, . . . , xr = tpr.
Case I: For r ≡ 0(mod4), m ≡ 0, 1 (mod4) (tpq) = {01;; p == 10,,23((mod4)
4) (tpq−2) = (tpq−3) = {10 ;; pp == 01,, 32((mmoodd44)) Case II: For r ≡ 1(mod4), m ≡ 0, 1 (mod4) (tpq) = {10 ;; p == 10,, 23((mod4)
4) (tpq−1) = (tpq−2) = {10 ;; pp == 10,, 23((mmoodd44)) Case III: For r ≡ 2(mod4), m ≡ 0, 1 (mod4) (tpq) = {10 ;; p == 10,, 23((mod4)
4) (tpq−2) = (tpq−4) = {01 ;; p == 10,,23((mod4)
4) Case IV: For r ≡ 3(mod4), m ≡ 0, 1 (mod4) (tpq) = { 0 ; = 0, 3( 4)
1 ; = 1, 2( 4) (tpq−1) = (tpq−4) = {01;; p == 10,,23((mod4)
4) Case V: For r ≡ 0(mod4), m ≡ 2, 3 (mod4) 0 ; p = 1, 3(mod4) (tpq) = {1 ; = 0, 2( 4)
0 ; p = 0, 2(mod4) (tpq−2) = (tpq−3) = {1 ; p = 1, 3(mod4) Case VI: For r ≡ 1(mod4), m ≡ 2, 3 (mod4)
0 ; p = 0, 2(mod4) (tpq) = {1 ; = 1, 3( 4)
0 ; p = 1, 3(mod4) (tpq−1) = (tpq−2) = { 1 ; p = 0, 2(mod4) Case VII: For r ≡ 2(mod4), m ≡ 2, 3 (mod4)
0 ; = 0, 2( (tpq) = { 1 ; = 1, 3( 4) 4) 0 ; p = 1, 3(mod4) (tpq−2) = (tpq−4) = {1 ; = 0, 2( 4) Case VIII: For r ≡ 3(mod4), m ≡ 2, 3 (mod4)
0 ; = 0, 2( (tpq) = { 1 ; = 1, 3( 4) 4) 0 ; p = 1, 3(mod4) (tpq−1) = (tpq−4) = {1 ; = 0, 2( 4)
The corresponding observed cases of m with labeling pattern of edges and vertices resulted in
above table. Therefore, the conditions | (0) − (
Example 4: The graph W = {5-Cm : P5 }is directed cordial as shown in Figure 4.
Theorem 3.5. The graph W = {2-Cm2 : Pr } merged by two copies of directed cycle graph with path of indefinite length is cordial.(For m ≥ 6)
Proof. Consider vertices of 1st and 2nd copies of Cm2 as t1, t2, . . .tm and s1, s2 . . . sm respectively. Let vertices 1st, 2nd and r th of path Pr be represented by x1, x2, . . . , xr which carries condition as first vertex x1 = t1 and r th vertex, xr = s1.
Consider : V (W) → {0, 1} as stated,
1 ; p = 1, 3, 5(mod6) (tp) = { 0 ; p = 0, 2, 4(mod6) (sp) (xr)
1 ; p = 0, 2, 4(mod6) = { 0 ; p = 1, 3, 5(mod6) 1 ; r = 1, 2(mod4) = { 0 ; r = 0, 3(mod4)
1 ; p = 1, 3, 5(mod6) (tp) = (sp) = { 0 ; p = 0, 2, 4(mod6) (xr)
1 ; r = 1, 2(mod4) = { 0 ; r = 0, 3(mod4) Case III For r ≡ 2, 3 (mod4)
r ≡ 0(mod4),m ≡ 0, 2, 4 (mod6) r ≡ 1(mod4), m ≡ 0, 2, 4(mod6) r ≡ 2(mod4), m ≡ 0, 2, 4(mod6) r ≡ 3(mod4), m ≡ 0, 2, 4(mod6)
(0) = (
(0) = (
Example 5 The graph W = {2-C62 : P5 } is directed cordial as shown in Figure 5.
Theorem 3.6. The graph W = {r-Cm2 : Pr }, m ≥ 6 preserves directed cordial labeling. Proof. Let us represent the vertices of 1st, 2nd , . . . , r th copy as tp1, tp2, . . . , tpr. Let x1, x2, . . . , xr be the vertices of path Pr with condition x1 = tp1, x2 = tp2, . . . , xr = tpr.
Consider : V (W) → {0, 1} When m ≡ 0, 2, 4(mod6).
1 ; = 0, 2, 4(mod6) (tpq) = { 0 ; = 1, 3, 5(mod6)
1 ; = 1, 3, 5(mod6) (tpq−2) = (tpq−3) = { 0 ; = 0, 2, 4(mod6)
1 ; = 1, 3, 5(mod6) (tpq) = { 0 ; ℎ = 0, 2, 4(mod6)
1 ; p = 0, 2, 4(mod6) (tpq−1) = (tpq−2) = { 0 ; p = 1, 3, 5(mod6)
1 ; p = 1, 3, 5(mod6) (tpq) = { 0 ; p = 0, 2, 4(mod6)
1 ; p = 0, 2, 4(mod6) (tpq−2) = (tpq−4) = { 0 ; p = 1, 3, 5(mod6)
1 ; p = 1, 3, 5(mod6) (tpq) = { 0 ; p = 0, 2, 4(mod6)
1 ; p = 0, 2, 4(mod6) (tpq−1) = (tpq−4) = { 0 ; p = 1, 3, 5(mod6)
Example 6 The graph W = {6-C62 : P6 } is directed cordial as shown in Figure 6.
In this paper we investigated linear directed cycle and their square is directed cordial. The directed path merged with two copies of directed cycle Cm and directed square cycle Cm2 is directed cordial. We proved that directed path unions of r-copies of these graphs are directed cordial under certain condition. To investigate and elaborate various families of graph which preserves same results is an open problem for researchers. In the branch of graph theory, labeling is widely applicable in coding, circuit designing, communication networking and data base management.
Authors are highly grateful to anonymous referee for their valuable inputs and comments.