J.
Indones.
Math.
Soc.
Vol.
No.
, pp.
01Ae08.
HARMONIOUS CHROMATIC NUMBER OF CENTRAL
GRAPH OF QUADRILATERAL SNAKES
AKHLAK MANSURI1,a .
ROHIT MEHTA2 .
CHANDEL1,b Department of Mathematics.
Government Girls College.
Mandsaur (M.
) India, email: a akhlaakmansuri@gmail.
rs chandel2009@yahoo.
Department of Engineering Mathematics.
Radharaman Engineering College.
Bhopal (M.
) India, email: rohitmehta1010@gmail.
Abstract.
This article shows the study about the harmonious coloring and investigation of the harmonious chromatic number of the central graph of the kquadrilateral snake and k-alternate quadrilateral snake i.
NH (C.
Qn )) = .
n Oe .
and NH (C.
(AQn ))) = ( 3k 4 )n Oe 1.
Key words and Phrases: Harmonious coloring.
harmonious chromatic number.
central graph.
quadrilateral and alternate quadrilateral snakes.
INTRODUCTION
The harmonious coloring .
, 7, 8, 17, .
of a simple graph G is a kind of vertex coloring in which each edge of graph G has different color pair and least number of colors are to be used for this coloring is called the harmonious chromatic number, denoted by NH (G).
For a simple graph G when we subdivide the each edge and connect all the non-adjacent vertices, such obtained graph is called the central graph .
, 17, .
of G and it is denoted by C(G).
A quadrilateral snake Qn is obtained from a path u1 , u2 , .
, un by joining ui and ui 1 to new vertices vi and wi respectively and adding edges vi wi for .
O i O n Oe .
in which every edge of a path is replaced by a cycle C4 .
We take the following definitions from .
, 4, 9, 10, 11, 12, 13, 14, 15, .
: quadrilateral snake, double quadrilateral snake, triple quadrilateral snake, alternate quadrilateral snake, double alternate quadrilateral snake and triple alternate quadrilateral snake and investigate the harmonious chromatic number of the central graph of these graphs.
We also give the harmonious chromatic number of the central graph of k- quadrilateral snake and k- alternate quadrilateral snake, where the k-quadrilateral snake graph k(Qn ) consists of k quadrilateral snakes 2020 Mathematics Subject Classification: 05C15, 05C76 Received: 11-07-2020, accepted: 12-01-2021.
Mansuri.
Mehta.
Chandel with a common path and k-alternate quadrilateral snake graph k(AQn ) consists of k alternate quadrilateral snakes .
with a common path.
Throughout the paper we consider n as the number of vertices of the path Pn .
Harmonious Chromatic Number of C(Qn ).
C(DQn ).
C(T Qn ) Theorem 2.
For central graph of quadrilateral snake Qn , the harmonious chromatic number.
NH (C(Qn )) = 5n Oe 4, n Ou 2.
Proof.
Let us consider Qn as the quadrilateral snake graph and Pn as the path graph contains n vertices u1 , u2 , .
, un .
For obtaining central graph, we subdivide each edge ui ui 1 , ui vi , ui wi and vi wi .
O i O n Oe .
of Qn by the vertices vi0 , vi00 , vi000 and vi0000 .
O i O n Oe .
of Qn in central graph of Qn .
V (C(Qn )) = .
1 O i O .
O .
i , wi , vi0 , vi00 , vi000 , vi0000 : 1 O i O n Oe .
Now coloring the vertices of C(Qn ) as follows.
define c : V (C(Qn )) OeIe .
, 2, 3, .
, 5n Oe .
where n Ou 2 by c.
i00 ) = i, c.
i000 ) = i, c.
i0 ) = n Oe i 1, c.
i0000 ) = n Oe 1 i, c.
i ) = 2n Oe 2 i, c.
i ) = 3n Oe 3 i for .
O i O n Oe .
and c.
i ) = 4n Oe 4 i for .
O i O .
Now Figure 1.
C(Q3 ) with coloring.
NH (C(Q3 )) = 11.
from above each c.
i ), c.
i ), c.
i ) and its neighbors are assigned by different colors c.
i ) 6= c.
i ) 6= c.
i ), although c.
i0 ) = c.
i0000 ) and c.
i00 ) = c.
i000 ) but these vertices are at least at a distance 2, therefore it is proper.
It is also obvious from above that no two edges share the same color pair and same colored vertices are at least at a distance 3, therefore it is harmonious and all the vertices are colored by 5n Oe 4 colors.
Now if we repeat .
any color on any vertex from these 5n Oe 4 colors, color pairs will be repeated which leads to contradict the harmonious Harmonious Chromatic Number of Central Graph of Quadrilateral Snakes coloring, therefore it is minimum.
Hence NH (C(Qn )) = 5n Oe 4.
Figure 1 shows the central graph of Q3 with harmonious coloring.
Theorem 2.
For central graph of double quadrilateral snake DQn , the harmonious chromatic number.
NH (C(DQn )) = 8n Oe 7, n Ou 2 Proof.
Let us consider DQn as the double quadrilateral snake and Pn as the path graph with n vertices u1 , u2 , .
, un .
Now we obtain the central graph as described in Theorem 2.
1, therefore V (C(DQn )) = .
i : 1 O i O .
i , wi , xi , yi , e0i , e00i , ei , li0 , li00 , m0i , m00i : 1 O i O n Oe .
Now coloring the vertices of C(DQn ) as follows.
c : V (C(DQn )) OeIe .
, 2, 3, .
, 8n Oe .
for n Ou 2 by c.
i ) = i, c.
0i ) = i, c.
00i ) = i, c.
i0 ) = n Oe 1 i, c.
i00 ) = n Oe 1 i, c.
0i ) = 2n Oe 2 i, c.
00i ) = 2n Oe 2 i, c.
i ) = 3n Oe 3 i, c.
i ) = 4n Oe 4 i, c.
i ) = 5n Oe 5 i, c.
i ) = 6n Oe 6 i for .
O i O n Oe .
and c.
i ) = 7n Oe 7 i for .
O i O .
To prove c is harmonious and minimum, follow Theorem 2.
Figure 2 shows the harmonious coloring for C(DQ3 ).
Figure 2.
C(DQ3 ) with harmonious coloring.
NH (C(DQ3 )) = 17.
Theorem 2.
For central graph of triple quadrilateral snake T Qn , the harmonious chromatic number.
NH (C(T Qn )) = 11n Oe 10, n Ou 2.
Proof.
Let us consider T Qn as the triple quadrilateral snake and Pn as the path graph with n vertices u1 , u2 , .
, un .
Now we obtain the central graph as described in Theorem 2.
1, therefore V (C(T Qn )) = .
i : 1 O i O .
i , wi , xi , yi , pi , qi , ei , e0i , e00i , 00 0 00 i , li , li , mi , mi , zi , zi : 1 O i O n Oe .
Now coloring the vertices of C(T Qn ) as define c : V (C(T Qn )) OeIe .
, 2, 3, .
, 11n Oe .
where n Ou 2 by c.
i ) = i.
Mansuri.
Mehta.
Chandel c.
0i ) = i, c.
00i ) = i, c.
000 i ) = i, c.
i ) = n Oe 1 i, c.
i ) = n Oe 1 i, c.
i ) = 2n Oe 2 i, c.
i ) = 2n Oe 2 i, c.
i ) = 3n Oe 3 i, c.
i ) = 3n Oe 3 i, c.
i ) = 4n Oe 4 i, c.
i ) = 5n Oe 5 i, c.
i ) = 6n Oe 6 i, c.
i ) = 7n Oe 7 i, c.
i ) = 8n Oe 8 i, c.
i ) = 9n Oe 9 i, c.
i ) = 10n Oe 10 i for .
O i O n Oe .
and c.
i ) = 10n Oe 10 i for .
O i O .
For remaining proof, follow Theorem 2.
Figure 3 shows the harmonious coloring for C(T Q3 ).
Figure 3.
C(T Q3 ) with harmonious coloring.
NH (C(T Q3 )) = 23.
Harmonious Chromatic Number of k-Quadrilateral Snake Theorem 3.
For central graph of k-quadrilateral snake kQn , the harmonious chromatic number.
NH (C.
Qn )) = .
n Oe .
, n Ou 2.
Proof.
For k = 1, we have NH (C(Qn )) = 5n Oe 4, this proves Theorem 2.
1, for k = 2, we have NH (C(D(Qn ))) = 8n Oe 7, this proves Theorem 2.
2, for k = 3, we have NH (C(T (Qn ))) = 11n Oe 10, this proves Theorem 2.
3, which is true.
Let NH (C.
Qn )) be true for some positive integer r, i.
NH (C.
Qn )) = .
n Oe .
We shall now prove that NH (C(.
Qn )) is true.
Consider NH (C(.
Qn )) = .
nOe.
= .
nOe.
3nOe 3 = NH (C.
Qn )) 11nOe10Oe.
nOe.
= NH (C.
Qn )) NH (C(T Qn ))OeNH (C(DQn )) which is true.
Therefore it is true for r 1 that follows by mathematical induction, it is true for all values of k.
Hence the theorem.
Harmonious Chromatic Number of Central Graph of Quadrilateral Snakes Harmonious Chromatic Number of C(AQn ).
C(DAQn ).
C(T AQn ) Theorem 4.
For alternate quadrilateral snake AQn , harmonious chromatic number.
NH C(AQn ) = 7n 2 Oe 1, n is even and Ou 4.
Proof.
Let us consider AQn as the alternate quadrilateral snake and Pn as the path graph with n vertices u1 , u2 , .
, un .
Now we obtain the central graph as described in Theorem 2.
1, therefore V (C(AQn )) = .
i : 1 O i O .
O .
i , wi , vi00 , li0 , li00 : .
O i O 2 )} O .
i : .
O i O n Oe .
Now coloring the vertices of C(AQn ) as follows.
c : V (C(AQn ) OeIe .
, 2, 3, .
, 7n 2 Oe .
where n Ou 4 by c.
i ) = i for .
O i O n Oe .
, c.
i00 ) = i, c.
i0 ) = n Oe 1 i, c.
i00 ) = n Oe 1 i, c.
i ) = 3n 2 Oe 1 i, c.
i ) = 2n Oe 1 i for .
O i O 2 ) and c.
i ) = 2 Oe 1 i for .
O i O .
To prove c is harmonious and minimum, follow Theorem 2.
Figure 4 shows the central graph of AQn with harmonious coloring.
Figure 4.
C(AQ4 ) with harmonious coloring.
NH (C(AQ4 )) = 13.
Theorem 4.
For central graph of double alternate quadrilateral snake D(AQn ), the harmonious chromatic number.
NH (C(D(AQn ))) = 5n Oe 1, n is even and Ou 4.
Proof.
Let us consider D(AQn ) as the double alternate quadrilateral snake and Pn as the path graph with n vertices u1 , u2 , .
, un .
Now we obtain the central graph as described in Theorem 2.
1, therefore V (C(D(AQn ))) = .
i : 1 O i O .
O .
i , wi , xi , yi , e0i , e00i , li0 , li00 , m0i , m00i : .
O i O n2 )} O .
i : .
O i O n Oe .
Now coloring the vertices of C(D(AQn )) as follows.
define c : V (C(D(AQn )) OeIe .
, 2, 3, .
, 5n Oe .
where n Ou 4 by c.
i ) = i for .
O i O n Oe .
, c.
0i ) = i, c.
00i ) = i, c.
i0 ) = n Oe 1 i, c.
i00 ) = n Oe 1 i, c.
0i ) = 3n 2 Oe 1 i, c.
i ) = 2 Oe 1 i, c.
i ) = 2n Oe 1 i, c.
i ) = 2 Oe 1 i, c.
i ) = 3n Oe 1 i, c.
i ) = 2 Oe 1 i for Mansuri.
Mehta.
Chandel .
O i O n2 ) and c.
i ) = 4n Oe 1 i for .
O i O .
To prove c is harmonious and minimum, follow Theorem 2.
Figure 5 shows the central graph of D(AQn ) with harmonious coloring.
Figure 5.
C(D(AQ4 )) with coloring.
NH (C(D(AQ4 ))) = 19.
Theorem 4.
For triple alternate Quadrilateral snake T (AQn ), the harmonious chromatic number.
NH C(T (AQn )) = 13n 2 Oe 1, n is even and Ou 4.
Proof.
Let us consider T (AQn ) as the triple alternate quadrilateral snake and Pn as the path graph with n vertices u1 , u2 , .
, un .
Now we obtain the central graph as described in Theorem 2.
1, therefore V (C(T (AQn ))) = .
i : 1 O i O .
O .
i , wi , xi , yi , pi , qi , e0i , e00i , e000 i , li , li , li , mi , mi , mi : .
O i O 2 )} O .
i : .
O i O n Oe Now coloring the vertices of C(T (AQn )) as follows.
define c : V (C(T (AQn )) OeIe .
, 2, 3, .
, 13n 2 Oe .
for n Ou 4 by c.
i ) = i for .
O i O n Oe .
, c.
i ) = i, c.
i ) = i, c.
i ) = i, c.
i ) = n Oe 1 i, c.
i ) = n Oe 1 i, c.
i ) = 2 Oe 1 i, c.
i ) = 2 Oe 1 i, c.
i ) = 2n Oe 1 i, c.
i ) = 2n Oe 1 i, c.
i ) = 5n 2 Oe 1 i, c.
i ) = 3n Oe 1 i, c.
i ) = 7n 2 Oe 1 i, c.
i ) = 5n Oe 1 i for .
O i O n2 ) and c.
i ) = 11n To prove c is harmonious and minimum, follow Theorem 2.
Figure 6 shows the central graph of T (AQn ) with harmonious coloring.
Harmonious Chromatic Number of Central Graph of Quadrilateral Snakes Figure C(T (AQ4 )) NH (C(T (AQ4 ))) = 25.
Harmonious Chromatic Number of k-Alternate Quadrilateral Snake Theorem 5.
For central graph of k-alternate quadrilateral snake k(AQn ), the harmonious chromatic number.
NH (C.
(AQn ))) = ( 3k 4 2 )n Oe 1, n is even and Ou 4.
Proof.
For k = 1, we have NH (C(AQn )) = 7n 2 Oe 1, this proves Theorem 4.
1, for k = 2, we have NH (C(D(AQn ))) = 5n Oe 1, this proves Theorem 4.
2, for k = 3, we have NH (C(T (AQn ))) = 13n 2 Oe 1, this proves Theorem 4.
3 which is true.
Let NH (C.
(AQn ))) be true for some positive integer r, i.
NH (C.
(AQn ))) = ( 3r 4 2 )n Oe .
We shall now prove that NH (C(.
(AQn ))) is true.
Consider NH (C(.
AQn )) = ( 3.
4 )n Oe .
= ( 3r 4 2 )n Oe .
2 = NH (C.
AQn )) ( 2 Oe.
Oe.
nOe.
= NH (C.
(AQn ))) NH (C(T (AQn )))OeNH (C(D(AQn ))) which is true.
Therefore it is true for r 1 that follows by mathematical induction, it is true for all values of k.
Hence the theorem.
Conclusion This article shows the study about the harmonious coloring and we find the harmonious chromatic number of central graph of k- quadrilateral and k-alternate quadrilateral snakes NH (C.
Qn )) = .
n Oe .
, and NH (C.
(AQn ))) = Mansuri.
Mehta.
Chandel ( 3k 4 2 )n Oe 1 respectively.
For future scope we can examine the different type of colorings for these quadrilateral snakes.
Acknowledgment Thanks for the referees for their excellent comments and valuable suggestions for improving this article.
REFERENCES