DIFFERENCE CORDIALITY OF SOME SNAKE GRAPHS

Journal of Applied Mathematics & Informatics.
2014.
Sep,
32(3_4):
377-387

- Received : May 13, 2013
- Accepted : November 04, 2013
- Published : September 28, 2014

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

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.
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]
.
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
T_{n}
is obtained from the path
P_{n}
by replacing each edge of the path by a triangle
C
_{3}
.
Theorem 2.2.
The Triangular snake T_{n} is difference cordial.
Proof
. Let
P_{n}
be the path
u
_{1}
u
_{2}
. . .
u_{n}
. Let
V
(
T_{n}
) =
V
(
P_{n}
)∪{
v_{i}
: 1 ≤
i
≤
n
− 1} and
E
(
T_{n}
) =
E
(
P_{n}
) ∪ {
: 1 ≤
i
≤
n
− 1}. In this graph, |
V
(
T_{n}
)| = 2
n
− 1 and |
E
(
T_{n}
)| = 3
n
− 3. For
n
> 4, define
ƒ
:
V
(
T_{n}
) → {1, 2, . . . , 2
n
− 1} by
The following
table 1
shows that the labeling
ƒ
defined above is a difference cordial labeing of
T_{n}
for
n
> 4.
We now display a difference cordial labeling for
T
_{2}
,
T
_{3}
and
T
_{4}
is given in
figure 1
.
The Quadrilateral snake
Q_{n}
is obtained from the path
P_{n}
by replacing each edge of the path by a cycle
C
_{4}
.
Theorem 2.3.
All Quadrilateral snakes are difference cordial.
Proof
. Let
P_{n}
be the path
u
_{1}
u
_{2}
. . .
u_{n}
. Let
V
(
Q_{n}
) = {
v_{i}
,
w_{i}
: 1 ≤
i
≤
n
− 1} ∪
V
(
P_{n}
) and
E
(
Q_{n}
) =
E
(
P_{n}
) ∪ {
: 1 ≤
i
≤
n
− 1}. Note that |
V
(
Q_{n}
)| = 3
n
− 2 and |
E
Q_{n}
)| = 4
n
− 4. Define a map
ƒ
:
V
(
Q_{n}
) → {1, 2, 3, . . . , 3
n
− 2} by
ƒ
(
v
_{1}
) = 3
n
− 3,
ƒ
(
v
_{2}
) = 3
n
− 2,
ƒ
(
w
_{1}
) = 3
n
− 4,
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
(
T_{n}
) is obtained from a path
u
_{1}
u
_{2}
. . .
u_{n}
by joining ui and
u
_{i+1}
(alternatively) to new vertex
v_{i}
. 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,
and |
E
(
A
(
T_{n}
))| = 2
n
− 3. Define
by
ƒ
(
u
_{1}
) = 1,
and
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
u_{n}
. Here
and |
E
(
A
(
T_{n}
))| = 2
n
− 1. Define a map
by
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
u_{n}
. Note that in this case,
and |
E
(
A
(
T_{n}
))| = 2
n
−2. Define an injective map
by
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
(
Q_{n}
) is obtained from a path
u
_{1}
u
_{2}
. . .
u_{n}
by joining
u_{i}
,
u
_{i+1}
(alterna-tively) to new vertices
v_{i}
,
w_{i}
respectively and then joining
v_{i}
and
w_{i}
. 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
(
Q_{n}
))| = 2
n
−2 and
Define
ƒ
:
V
(
A
(
Q_{n}
)) → {1, 2, . . . , 2
n
− 2} as follows:
The
table 2
given below shows that
ƒ
is a difference cordial labeling.
Case 2.
Let the first cycle
C
_{4}
be starts from
u
_{1}
and the last cycle be ends with
u_{n}
. Here, |
V
(
A
(
Q_{n}
))| = 2
n
and
Define
ƒ
:
V
(
A
(
Q_{n}
)) → {1, 2, . . . , 2
n
} by
In this case the following
table 3
shows that
ƒ
is a difference cordial labeling.
Case 3.
Let the first cycle
C
_{4}
be starts from
u
_{2}
and the last cycle be ends with
u_{n}
. Note that |
V
(
A
(
Q_{n}
))| = 2
n
− 1 and
Define
ƒ
:
V
(
A
(
Q_{n}
)) → {1, 2, . . . , 2
n
− 1} by
The following
table 4
shows that
ƒ
is a difference cordial labeling.
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
IT_{n}
is obtained from the path
P_{n}
:
u
_{1}
u
_{2}
. . .
u_{n}
with vertex set
V
(
IT_{n}
) =
V
(
P_{n}
) → {
v_{i}
: 1 ≤
i
≤
n
− 2} and the edge set
E
(
IT_{n}
) =
E
(
P_{n}
) ∪ {
: 1 ≤
i
≤
n
− 2}.
Theorem 2.6.
The irregular triangular snake is difference cordial.
Proof
. Clearly |
V
(
IT_{n}
)| = 2
n
−2 and |
E
(
IT_{n}
)| = 3
n
−5. Define
ƒ
:
V
(
IT_{n}
) → {1, 2, . . . , 2
n
− 2} as follows:
Case 1.
n
is odd.
Case 2.
n
is even. Label the vertices
u_{i}
(1 ≤
i
≤
n
− 1) and
v_{i}
(1 ≤
i
≤
n
) as in case 1 and assign the label 2
n
− 2 to the vertex
u_{n}
. 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
.
The irregular quadrilateral snake
IQ_{n}
is obtained from the path
P_{n}
:
u
_{1}
u
_{2}
. . . ,
u_{n}
with vertex set
V
(
IQ_{n}
) =
V
(
P_{n}
)∪{
v_{i}
,
w_{i}
: 1 ≤
i
≤
n
− 2} and edge set
E
(
IQ_{n}
) =
E
(
P_{n}
) ∪ {
: 1 ≤
i
≤
n
− 2}.
Theorem 2.7.
The irregular quadrilateral snake is difference cordial.
Proof
. Clearly, |
V
(
IQ_{n}
)| = 3
n
− 4 and |
E
(
IQ_{n}
)| = 4
n
− 7 respectively. Define
ƒ
:
V
(
IQ_{n}
) → {1, 2, 3, . . . , 3
n
− 4} by
Since
it follows that
ƒ
is a difference cordial labeling.
A double triangular snake
DT_{n}
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}
. . .
u_{n}
by joining
u_{i}
and
u
_{i+1}
to a new vertex
v_{i}
(1 ≤
i
≤
n
− 1) and to a new vertex
w_{i}
(1 ≤
i
≤
n
− 1).
Theorem 2.8.
Double triangular snake DT_{n} 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
(
DT_{n}
)| = 3
n
− 2 and |
E
(
DT_{n}
)| = 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
DQ_{n}
consists of two triangular snakes that have a common path.
Theorem 2.9.
The double quadrilateral snake is difference cordial.
Proof
. Let
V
(
DQ_{n}
) = {
u_{i}
: 1 ≤
i
≤
n
} ∪ {
v_{i}
,
w_{i}
,
x_{i}
,
y_{i}
: 1 ≤
i
≤
n
− 1} and
E
(
DQ_{n}
) =
: 1 ≤
i
≤
n
− 1}. Clearly, |
V
(
DQ_{n}
)| = 5
n
− 4 and |
E
(
DQ_{n}
)| = 7
n
− 7. Define a map
ƒ
:
V
(
DQ_{n}
) → {1, 2, . . . , 5
n
− 4} as follows:
The following
table 6
shows that
ƒ
is a difference cordial labeling of
DQ_{n}
.
A double alternate triangular snake
DA
(
T_{n}
) 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}
. . .
u_{n}
by joining
u_{i}
and
u
_{i+1}
(alternatively) to two new vertices
v_{i}
and
w_{i}
.
Theorem 2.10.
Double alternate triangular snake DA
(
T_{n}
)
is difference cordial.
Proof
.
Case 1.
The triangles starts from
u
_{1}
and end with
u_{n}
. In this case, |
V
(
DA
(
T_{n}
))| = 2
n
and |
E
(
DA
(
T_{n}
))| = 3
n
− 1. Define an injective map
ƒ
:
V
(
DA
(
T_{n}
)) → {1, 2, . . . , 2
n
} by
Since
e_{f}
(1)
ƒ
is a difference cordial labeling of
DA
(
T_{n}
).
Case 2.
The triangles starts from
u
_{2}
and end with
u
_{n−1}
. Note that In this case, |
V
(
DA
(
T_{n}
))| = 2
n
− 2 and |
E
(
DA
(
T_{n}
))| = 3
n
− 5. Label the vertices
v_{i}
and
as in case 1 and define
ƒ
(
u_{i}
) = 2
i
− 3, 2 ≤
i
≤
n
− 1,
ƒ
(
u
_{1}
) = 2
n
− 3 and
ƒ
(
u_{n}
) = 2
n
− 2. Since
ƒ
is a difference cordial labeling of
DA
(
T_{n}
).
Case 3.
The triangles starts from
u
_{2}
and end with
u_{n}
. It is clear that in this case, |
V
(
DA
(
T_{n}
))| = 2
n
− 1 and |
E
(
DA
(
T_{n}
))| = 3
n
− 3. Label the vertices
v_{i}
and
as in case 1 and label
u_{i}
(2 ≤
i
≤
n
− 1) as in case 2 and define
ƒ
(
u
_{1}
) = 2
n
− 1. Since
ƒ
is a difference cordial labeling of
DA
(
T_{n}
).
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
(
Q_{n}
) consists of two alternate quadrilateral snakes that have a common path. That is, it is obtained from a path
u
_{1}
u
_{2}
. . .
u_{n}
by joining
u_{i}
and
u
_{n+1}
(alternatively) to new vertices
v_{i}
,
x_{i}
and
w_{i}
,
y_{i}
respectively and adding the edges viwi and
x_{i}
y_{i}
.
Theorem 2.11.
All double alternate quadrilateral snakes are difference cordial.
Proof
.
Case 1
The squares starts from
u
_{1}
and end with
u_{n}
. In this case, |
V
(
DA
(
Q_{n}
))| = 3
n
and |
E
(
DA
(
Q_{n}
))| = 4
n
−1. Define a map
ƒ
:
V
(
DA
(
Q_{n}
)) → {1, 2, . . . , 3
n
} by
Since
e_{ƒ}
(1) = 2
n
and
e_{ƒ}
(0) = 2
n
− 1,
ƒ
is a difference cordial labeling of
DA
(
Q_{n}
).
Case 2.
The squares starts from
u
_{2}
and end with
u
_{n−1}
. In this case, |
V
(
DA
(
Q_{n}
))| = 3
n
−4 and ||
E
(
DA
(
Q_{n}
))| = 4
n
−7. Label the vertices
v_{i}
,
w_{i}
,
x_{i}
,
y_{i}
as in case 1 and define
ƒ
(
u_{i}
) = 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
(
Q_{n}
).
Case 3.
The square starts from
u
_{2}
and end with
u_{n}
. In this case, |
V
(
DA
(
Q_{n}
))| = 3
n
−2 and |
E
(
DA
(
Q_{n}
))| = 4
n
−4. Label the vertices
v_{i}
,
w_{i}
,
x_{i}
,
y_{i}
as in case 1 and label
u_{i}
(2 ≤
i
≤
n
) as in case 2 and define
ƒ
(
u
_{1}
) = 3
n
− 2. Since
e_{ƒ}
(1) =
e_{f}
(0) = 2
n
− 2,
ƒ
is a difference cordial labeling of
DA
(
Q_{n}
).
Case 4.
The square starts from
u
_{1}
and end with
u
_{n-1}
. This case is equivalent to case 3.
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

Triangular snake
;
Quadrilateral snake
;
Alternate
;
Alternate triangular snake
;
Alternate quadrilateral snake

1. Introduction

Let
2. Main results

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

Acknowledgements

The authors thank the refree for his suggestions and valu-able comments.

BIO

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

Citing 'DIFFERENCE CORDIALITY OF SOME SNAKE GRAPHS
'

@article{ E1MCA9_2014_v32n3_4_377}
,title={DIFFERENCE CORDIALITY OF SOME SNAKE GRAPHS}
,volume={3_4}
, url={http://dx.doi.org/10.14317/jami.2014.377}, DOI={10.14317/jami.2014.377}
, number= {3_4}
, journal={Journal of Applied Mathematics & Informatics}
, publisher={Korean Society of Computational and Applied Mathematics}
, author={PONRAJ, R.
and
SATHISH NARAYANAN, S.}
, year={2014}
, month={Sep}