Advanced
DIFFERENCE CORDIALITY OF SOME SNAKE GRAPHS
DIFFERENCE CORDIALITY OF SOME SNAKE GRAPHS
Journal of Applied Mathematics & Informatics. 2014. Sep, 32(3_4): 377-387
Copyright © 2014, Korean Society of Computational and Applied Mathematics
  • Received : May 13, 2013
  • Accepted : November 04, 2013
  • Published : September 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
R. PONRAJ
S. SATHISH NARAYANAN

Abstract
Let G be a ( p, q ) graph. Let ƒ be a map from V ( G ) to {1, 2, . . . , p }. For each edge uv , assign the label | ƒ ( u ) − ƒ ( v )|. ƒ is called a difference cordial labeling if ƒ is a one to one map and | eƒ (0) − eƒ (1)| ≤ 1 where eƒ (1) and eƒ (0) denote the number of edges labeled with 1 and not labeled with 1 respectively. A graph with admits a difference cordial labeling is called a difference cordial graph. In this paper, we investigate the difference cordial labeling behavior of triangular snake, Quadrilateral snake, double triangular snake, double quadrilateral snake and alternate snakes. 2010 AMS Mathematics Subject Classification : 05C78.
Keywords
1. Introduction
Let G be a ( p, q ) graph. In this paper we have considered only simple and undirected graph. The number of vertices of G is called the order of G , de-noted by | V ( G )| and the number of edges of G is called the size of G , denoted by | E ( G )|. Labeled graphs are used in several areas such as astronomy, radar, circuit design and database management [1] . The notion of difference cordial labeling has been introduced by R. Ponraj, S. Sathish Narayanan and R. Kala in [3] . In [3 , 4 , 5 , 6 , 7] , difference cordial labeling behaviour of several graphs like path, cycle, complete graph, complete bipartite graph, bistar, wheel, web and some more standard graphs have been investigated. In this paper we investi-gate the difference cordial labeling behaviour of Triangular snake, Quadrilateral snake, Alternate triangular snake, Alternate quadrilateral snake. Let x be any real number. Then ⌊ x ⌋ stands for the largest integer less than or equal to x and ⌈ x ⌉ stands for the smallest integer greater than or equal to x . Terms and definitions not defined here are used in the sense of Harary [2] .
2. Main results
Definition 2.1. Let G be a ( p, q ) graph. Let ƒ : V ( G ) → {1, 2, . . . , p } be a bijection. Foreach edge uv , assign the label | ƒ ( u ) − ƒ ( v )|. ƒ is called a difference cordial labeling if ƒ is 1−1 and | eƒ (0) − eƒ (1)| ≤ 1 where eƒ (1) and eƒ (0) denote the number of edges labeled with 1 and not labeled with 1 respectively. A graph with a difference cordial labeling is called a difference cordial graph.
Now we investigate the difference cordial labeling behavior of some snake graphs. The triangular snake Tn is obtained from the path Pn by replacing each edge of the path by a triangle C 3 .
Theorem 2.2. The Triangular snake Tn is difference cordial.
Proof . Let Pn be the path u 1 u 2 . . . un . Let V ( Tn ) = V ( Pn )∪{ vi : 1 ≤ i n − 1} and E ( Tn ) = E ( Pn ) ∪ {
PPT Slide
Lager Image
: 1 ≤ i n − 1}. In this graph, | V ( Tn )| = 2 n − 1 and | E ( Tn )| = 3 n − 3. For n > 4, define ƒ : V ( Tn ) → {1, 2, . . . , 2 n − 1} by
PPT Slide
Lager Image
The following table 1 shows that the labeling ƒ defined above is a difference cordial labeing of Tn for n > 4.
PPT Slide
Lager Image
We now display a difference cordial labeling for T 2 , T 3 and T 4 is given in figure 1 .
PPT Slide
Lager Image
The Quadrilateral snake Qn is obtained from the path Pn by replacing each edge of the path by a cycle C 4 .
Theorem 2.3. All Quadrilateral snakes are difference cordial.
Proof . Let Pn be the path u 1 u 2 . . . un . Let V ( Qn ) = { vi , wi : 1 ≤ i n − 1} ∪ V ( Pn ) and E ( Qn ) = E ( Pn ) ∪ {
PPT Slide
Lager Image
: 1 ≤ i n − 1}. Note that | V ( Qn )| = 3 n − 2 and | E Qn )| = 4 n − 4. Define a map ƒ : V ( Qn ) → {1, 2, 3, . . . , 3 n − 2} by ƒ ( v 1 ) = 3 n − 3, ƒ ( v 2 ) = 3 n − 2, ƒ ( w 1 ) = 3 n − 4,
PPT Slide
Lager Image
Here, eƒ (0) = eƒ (1) = 2 n − 2. It follows that ƒ satisfies the edge condition of difference cordial graph.
Next is the alternate triangular snake. An alternate triangular snake A ( Tn ) is obtained from a path u 1 u 2 . . . un by joining ui and u i+1 (alternatively) to new vertex vi . That is every alternate edge of a path is replaced by C 3 .
Theorem 2.4. Alternate triangular snakes are difference cordial.
Proof . Case 1. Let the first triangle be starts from u 2 and the last triangle ends with u n−1
In this case,
PPT Slide
Lager Image
and | E ( A ( Tn ))| = 2 n − 3. Define
PPT Slide
Lager Image
by ƒ ( u 1 ) = 1,
PPT Slide
Lager Image
and
PPT Slide
Lager Image
In this case eƒ (0) = n − 1 and eƒ (1) = n − 2 and hence ƒ is difference cordial labeling.
Case 2. Let the first triangle be starts from u 1 and the last triangle ends with un . Here
PPT Slide
Lager Image
and | E ( A ( Tn ))| = 2 n − 1. Define a map
PPT Slide
Lager Image
by
PPT Slide
Lager Image
Since eƒ (0) = n − 1 and eƒ (1) = n, f is a required difference cordial labeling.
Case 3. Let the first triangle be starts from u 2 and the last triangle ends with un . Note that in this case,
PPT Slide
Lager Image
and | E ( A ( Tn ))| = 2 n −2. Define an injective map
PPT Slide
Lager Image
by
PPT Slide
Lager Image
Here eƒ (0) = n − 1 and eƒ (1) = n - 1. Therefore, ƒ is a difference cordial labeling.
Case 4. Let the first triangle be starts from u 1 and the last triangle ends with u n−1 . This case is equivalent to case 3.
Now we look into alternate quadrilateral snake. An alternate quadrilateral snake A ( Qn ) is obtained from a path u 1 u 2 . . . un by joining ui , u i+1 (alterna-tively) to new vertices vi , wi respectively and then joining vi and wi . That is every alternate edge of a path is replaced by a cycle C 4 .
Theorem 2.5. All alternate quadrilateral snakes are difference cordial.
Proof . Case 1. Let the first cycle C 4 be starts from u 2 and the last cycle be ends with u n−1 . Note that in this case, | V ( A ( Qn ))| = 2 n −2 and
PPT Slide
Lager Image
Define ƒ : V ( A ( Qn )) → {1, 2, . . . , 2 n − 2} as follows:
PPT Slide
Lager Image
The table 2 given below shows that ƒ is a difference cordial labeling.
PPT Slide
Lager Image
Case 2. Let the first cycle C 4 be starts from u 1 and the last cycle be ends with un . Here, | V ( A ( Qn ))| = 2 n and
PPT Slide
Lager Image
Define ƒ : V ( A ( Qn )) → {1, 2, . . . , 2 n } by
PPT Slide
Lager Image
In this case the following table 3 shows that ƒ is a difference cordial labeling.
PPT Slide
Lager Image
Case 3. Let the first cycle C 4 be starts from u 2 and the last cycle be ends with un . Note that | V ( A ( Qn ))| = 2 n − 1 and
PPT Slide
Lager Image
Define ƒ : V ( A ( Qn )) → {1, 2, . . . , 2 n − 1} by
PPT Slide
Lager Image
The following table 4 shows that ƒ is a difference cordial labeling.
PPT Slide
Lager Image
Case 4. Let the first cycle C 4 be starts from u 1 and the last cycle be ends with u n−1 . This case is equivalent to case 3.
Next investigation is about the irregular triangular snakes. The irregular triangular snake ITn is obtained from the path Pn : u 1 u 2 . . . un with vertex set V ( ITn ) = V ( Pn ) → { vi : 1 ≤ i n − 2} and the edge set E ( ITn ) = E ( Pn ) ∪ {
PPT Slide
Lager Image
: 1 ≤ i n − 2}.
Theorem 2.6. The irregular triangular snake is difference cordial.
Proof . Clearly | V ( ITn )| = 2 n −2 and | E ( ITn )| = 3 n −5. Define ƒ : V ( ITn ) → {1, 2, . . . , 2 n − 2} as follows:
Case 1. n is odd.
PPT Slide
Lager Image
Case 2. n is even. Label the vertices ui (1 ≤ i n − 1) and vi (1 ≤ i n ) as in case 1 and assign the label 2 n − 2 to the vertex un . The following table 5 gives the nature of the edge condition of the above labeling ƒ . It follows that ƒ is a difference cordial labeling.
The difference cordial labeling of irregular triangular snake IT 12 is given in figure 2 .
PPT Slide
Lager Image
PPT Slide
Lager Image
The irregular quadrilateral snake IQn is obtained from the path Pn : u 1 u 2 . . . , un with vertex set V ( IQn ) = V ( Pn )∪{ vi , wi : 1 ≤ i n − 2} and edge set E ( IQn ) = E ( Pn ) ∪ {
PPT Slide
Lager Image
: 1 ≤ i n − 2}.
Theorem 2.7. The irregular quadrilateral snake is difference cordial.
Proof . Clearly, | V ( IQn )| = 3 n − 4 and | E ( IQn )| = 4 n − 7 respectively. Define ƒ : V ( IQn ) → {1, 2, 3, . . . , 3 n − 4} by
PPT Slide
Lager Image
Since
PPT Slide
Lager Image
it follows that ƒ is a difference cordial labeling.
A double triangular snake DTn consists of two triangular snakes that have a common path. That is, a double triangular snake is obtained from a path u 1 , u 2 . . . un by joining ui and u i+1 to a new vertex vi (1 ≤ i n − 1) and to a new vertex wi (1 ≤ i n − 1).
Theorem 2.8. Double triangular snake DTn is difference cordial iff n ≤ 6.
Proof . For n ≤ 6, the difference cordial labeling is given in figure 3 . Conversely, suppose n > 6 and ƒ is a difference cordial labeling of the double triangular snake. Here, | V ( DTn )| = 3 n − 2 and | E ( DTn )| = 5 n − 5. We observe that the maximum value of eƒ (1) does not exceed 1 + 2 ( n − 1) + 1 = 2 n . Hence eƒ (0) ≥ q −2 n ≥ 3 n −5. Therefore, eƒ (0)− eƒ (1) ≥ n −5, a contradiction.
A double quadrilateral snake DQn consists of two triangular snakes that have a common path.
PPT Slide
Lager Image
Theorem 2.9. The double quadrilateral snake is difference cordial.
Proof . Let V ( DQn ) = { ui : 1 ≤ i n } ∪ { vi , wi , xi , yi : 1 ≤ i n − 1} and E ( DQn ) =
PPT Slide
Lager Image
: 1 ≤ i n − 1}. Clearly, | V ( DQn )| = 5 n − 4 and | E ( DQn )| = 7 n − 7. Define a map ƒ : V ( DQn ) → {1, 2, . . . , 5 n − 4} as follows:
PPT Slide
Lager Image
The following table 6 shows that ƒ is a difference cordial labeling of DQn .
PPT Slide
Lager Image
A double alternate triangular snake DA ( Tn ) consists of two alternate trian-gular snakes that have a common path. That is, a double alternate triangular snake is obtained from a path u 1 u 2 . . . un by joining ui and u i+1 (alternatively) to two new vertices vi and wi .
Theorem 2.10. Double alternate triangular snake DA ( Tn ) is difference cordial.
Proof . Case 1. The triangles starts from u 1 and end with un . In this case, | V ( DA ( Tn ))| = 2 n and | E ( DA ( Tn ))| = 3 n − 1. Define an injective map ƒ : V ( DA ( Tn )) → {1, 2, . . . , 2 n } by
PPT Slide
Lager Image
Since ef (1)
PPT Slide
Lager Image
ƒ is a difference cordial labeling of DA ( Tn ).
Case 2. The triangles starts from u 2 and end with u n−1 . Note that In this case, | V ( DA ( Tn ))| = 2 n − 2 and | E ( DA ( Tn ))| = 3 n − 5. Label the vertices vi and
PPT Slide
Lager Image
as in case 1 and define ƒ ( ui ) = 2 i − 3, 2 ≤ i n − 1, ƒ ( u 1 ) = 2 n − 3 and ƒ ( un ) = 2 n − 2. Since
PPT Slide
Lager Image
ƒ is a difference cordial labeling of DA ( Tn ).
Case 3. The triangles starts from u 2 and end with un . It is clear that in this case, | V ( DA ( Tn ))| = 2 n − 1 and | E ( DA ( Tn ))| = 3 n − 3. Label the vertices vi and
PPT Slide
Lager Image
as in case 1 and label ui (2 ≤ i n − 1) as in case 2 and define ƒ ( u 1 ) = 2 n − 1. Since
PPT Slide
Lager Image
ƒ is a difference cordial labeling of DA ( Tn ).
Case 4. The triangles starts from u 1 and end with u n−1 . This case is equivalent to case 3.
Finally, we look into the graph double alternate quadrilateral snake. A double alternate quadrilateral snake DA ( Qn ) consists of two alternate quadrilateral snakes that have a common path. That is, it is obtained from a path u 1 u 2 . . . un by joining ui and u n+1 (alternatively) to new vertices vi , xi and wi , yi respectively and adding the edges viwi and xi yi .
Theorem 2.11. All double alternate quadrilateral snakes are difference cordial.
Proof . Case 1 The squares starts from u 1 and end with un . In this case, | V ( DA ( Qn ))| = 3 n and | E ( DA ( Qn ))| = 4 n −1. Define a map ƒ : V ( DA ( Qn )) → {1, 2, . . . , 3 n } by
PPT Slide
Lager Image
Since eƒ (1) = 2 n and eƒ (0) = 2 n − 1, ƒ is a difference cordial labeling of DA ( Qn ).
Case 2. The squares starts from u 2 and end with u n−1 . In this case, | V ( DA ( Qn ))| = 3 n −4 and || E ( DA ( Qn ))| = 4 n −7. Label the vertices vi , wi , xi , yi
PPT Slide
Lager Image
as in case 1 and define ƒ ( ui ) = 3 i − 4, 2 ≤ i n , and ƒ ( u 1 ) = 3 n − 5. Since eƒ (1) = 2 n −3 and eƒ (0) = 2 n −4, ƒ is a difference cordial labeling of DA ( Qn ).
Case 3. The square starts from u 2 and end with un . In this case, | V ( DA ( Qn ))| = 3 n −2 and | E ( DA ( Qn ))| = 4 n −4. Label the vertices vi , wi , xi , yi
PPT Slide
Lager Image
as in case 1 and label ui (2 ≤ i n ) as in case 2 and define ƒ ( u 1 ) = 3 n − 2. Since eƒ (1) = ef (0) = 2 n − 2, ƒ is a difference cordial labeling of DA ( Qn ).
Case 4. The square starts from u 1 and end with u n-1 . This case is equivalent to case 3.
Acknowledgements
The authors thank the refree for his suggestions and valu-able comments.
BIO
Dr. R. Ponraj received his Ph.D in Manonmaniam Sundaranar University, Tirunelveli. He is currently an Assistant Professor at Sri Paramakalyani College, Alwarkurichi, India. His Research interest is in Discrete Mathematics.
Department of Mathematics, Sri Paramakalyani College, Alwarkurichi, Tamil Nadu, India-627412.
e-mail: ponrajmaths@gmail.com
Mr. S. Sathish Narayanan did his M.Phil in St. John’s College, Palayamkottai. He is persuing doctoral research work. His Research interest is in Graph labeling.
Department of Mathematics, Sri Paramakalyani College, Alwarkurichi, Tamil Nadu 627 412, India.
e-mail: sathishrvss@gmail.com
References
Gallian J. A. (2012) A Dynamic survey of graph labeling The Electronic Journal of Combinatorics # Ds6. 19
Harary F. (1969) Graph theory Addision wesley New Delhi
Ponraj R. , Narayanan S. Sathish , Kala R. (2013) Difference cordial labeling of graphs Global Journal of Mathematical Sicences: Theory and Practical 5 185 - 196
Ponraj R. , Narayanan S.Sathish , Kala R. (2013) Difference cordial labeling of graphs obtained from Double snakes International Journal of Mathematics Research 5 317 - 322    DOI : 10.1504/IJMOR.2013.053626
Ponraj R. , Narayanan S.Sathish (2013) Difference cordiality of some graphs obtained from Double Alternate Snake Graphs Global Journal of Mathematical Sciences: Theory and Practical 5 167 - 175
Ponraj R. , Narayanan S. Sathish , Kala R. (2013) Difference cordial labeling of corona graphs J. Math. Comput. Sci. 3 1237 - 1251
Ponraj R. , Narayanan S. Sathish (2013) Further results on difference cordial labeling of corona graphs The Journal of the Indian Academy of Mathematics 35