1,161
Views
3
CrossRef citations to date
0
Altmetric
Research Articles

On certain prime cordial families of graphs

ORCID Icon, ORCID Icon, ORCID Icon & ORCID Icon
Pages 579-584 | Received 03 Dec 2019, Accepted 11 Apr 2020, Published online: 28 Apr 2020

Abstract

Graph labelling is an important tool in modelling real life problems. In the present paper, different graph families are studied for prime cordial labelling. In this work, we show that the double comb graph Pn2K1, for n2, as well as sunflower planar graph Sfn for n3, admit prime cordial labelling. We also prove that if we join two copies of sunflower planar graph by a path of arbitrary length then the resultant graph is also prime cordial.

1. Introduction

A relation between numbers and structure of graphs is called graph labelling. Graph labelings have broad range of applications in various areas of science and technology such as radar, astronomy, computer science and communication networks. Gallian [Citation1] gave a comprehensive survey of graph labelings. Cahit introduced the concept of cordial labelling [Citation2]. Many other researchers [Citation3–6] have a great contribution for deriving various results on cordial labelling.

Different labelling schemes have been introduced with minor changes in cordial labelling conditions. Motivated through the concept of prime labelling and cordial labelling, Sundaram et al. introduced prime cordial labelling [Citation7]. Prime cordial labelling contains blend of both the labelings. The present work is focused on prime cordial labelling of certain graph families.Vaidya and Vihol investigated the prime cordial labelling of graphs obtained by various graph operations [Citation8]. They also investigated prime cordial behaviour of some cycle related graphs [Citation9].

Vaidya and Shah have proved that the wheel graph and some wheel related graphs like gear, helm and closed helm graphs admit prime cordial labelling [Citation10]. Babitha and Baskar gave certain characterizations of prime cordial graphs [Citation11]. In addition to this many other researchers [Citation12–14] have great contribution for deriving characterization results on prime cordial labelling. For other studies which use similar techniques include [Citation15], [Citation16].

Every graph is not prime cordial. In this paper, we add new families of graphs to Prime cordial graphs.

These graphs correspond to many electrical, protein or communication network, and prime cordiality can help in solving the problems in different areas like coding theory, artificial intelligence, clinical psychology, radio networks and many more. In this paper we prove that double comb graph, sunflower graph and two copies of sunflower graph are prime cordial. These prime cordial graphs can, in turn, help to construct new families of prime cordial graphs by certain graph transformations.

2. Materials and methods

In this work we investigate some families of graphs for prime cordial labelling. We consider finite, simple connected graphs. Let the graph G has p vertices and q edges, denoted as G(p,q). V(G) denotes the set of vertices of graph G and E(G) denotes the set of edges of G. We follow Gross and Yellen [Citation17] for basic graph theoretic concepts, symbols and terminology. We provide brief summary of definitions which are necessary for the present investigations.

Definition 1:

The labelling of graph is the allocation of numbers to the vertices or edges or both under certain conditions. If we assign numbers to the vertices, then the labelling is called a vertex labelling an is called an edge labelling if we assign numbers to the set of edges.

Definition 2:

A labelling is called binary vertex labelling if we assign only 0 and 1 to the vertices of G i.e the range of mapping p is the set {0,1}.

Notation 1. Let v be a vertex of G then p(v)is called the label of the vertex v under p.

Notation 2. If p:V(G){0,1} is binary vertex labelling. Then vp(i)=|{vV(G)|p(v)=i}| where i {0,1}.

Notation 3. Consider the induced edge labelling p:E(G){0,1} defined as p(e)=|p(u)p(v)|, where e=uv is an edge. Then ep(i)=|{eE(G)|p(e)=i}| where i {0,1}.

Definition 3:

Let p:V(G){0,1} be a binary vertex labelling of G then it is called cordial labelling if it satisfies the following conditions. |vp(0)vp(1)|1|ep(0)ep(1)|  1A graph G which satisfies the above conditions is called a cordial graph.

Definition 4:

An injective mapping p:V(G){1,2,,|V(G)|} is called prime labelling of G if, gcd(p(u),p(v))=1, for every pair of adjacent vertices u,v. A graph G is termed as prime graph if it satisfies the condition of prime labelling.

Definition 5:

A bijection p:V(G){1,2,...,|V|} is called a prime cordial labelling of G if the induced edge function p:E(G){0,1} defined by p(e=uv)=1  if gcd (p(u),p(v))=10  otherwisesuch that |ep(0) -- ep(1)|1.

A graph with labelling satisfying above conditions is termed as prime cordial graph.

Definition 6:

A double comb graph is a graph obtained from a path Pn by attaching two pendant vertices at each vertex of Pn denoted by Pn2K1.

Definition 7:

A sunflower planar graph Sfn is obtained from a wheel graph with vertices v0,v1,v2,,vn (v0 is central vertex and v1,v2,,vn are rim vertices) and additional vertices u1,u2,,un such that uj is joined to vj and vj+1, where vj+1 is taken modulo n.

3. Main results

Theorem 1:

Double comb graph admits prime cordial labeling for. admits prime cordial labeling for.

Proof: Let H denotes double comb graph Pn2K1 with V(H)=vi,uij, 1in, j=1,2 andE(H)=(vivi+1):i=1,2,,n1(viuij):i=1,2,,n;j=1,2.Then |V(H)|=3n |E(H)|=3n1|V(H)|=3n |E(H)|=3n1.

We define p:V(H){1,2,3,,3n} according to the following cases.

Case 1: n2 n1: n2 n is even. p(vi)=6i ; 1in2 and pvn+22=1, p(vi+1)=p(vi)+6; n2+1in1 p(ui1)=p(vi)4; 1in2 p(ui1)=p(vi)+2; n2+1in p(ui2)=p(vi)2; 1in2 p(ui2)=p(vi)+4; n2+1in.

According to the labelling scheme we have ep(0)+1=ep(1)=(3n/2).

Case 2: n3n2: n3n is odd. p(vi)=6i; 1in2 pvn2=3n, pvn+32=3, pvn+52=7, p(vi+1)=p(vi)+6; n+52in1 p(ui1)=p(vi)4; 1in2 p(ui1)=p(vi)2; i=n2 p(ui1)=1; i=n+32, p(ui1)=9; i=n+52 p(ui1)=p(vi)+2; n+52in p(ui2)=p(vi)2; 1in2 p(ui2)=p(vi)1; i=n2 p(ui2)=5; i=n+32, p(ui2)=11; i=n+52 p(ui2)=p(vi)+4; n+52in.

Here, we have ep(0)=ep(1)=(3n1/2).

So, in the two cases discussed above it can be observed that |ep(0)ep(1)|1.

As a result, we can say that Pn2K1n2Pn2K1n2, labeling is elaborated in Figure .

Figure 1. Prime cordial labelling of P92K1.

Figure 1. Prime cordial labelling of P9⊙2K1.

Theorem 2:

The sunflower planar graph Sfn n6. Sfn n6.

Proof: Let {v0,v1,v2,,vn,w1,w2,,wn} be the vertices of Sfn{e1,e2,e3,,e4n} Sfn{e1,e2,e3,,e4n} be the edges of Sfn |V(Sfn)|=2n+1|E(Sfn)|=4n Sfn |V(Sfn)|=2n+1|E(Sfn)|=4n Sfn |V(Sfn)|=2n+1|E(Sfn)|=4n

We define p:V(Sfn){1,2,3,,2n+1} as follows Figure ,

Figure 2. Prime cordial labelling of Sf_8.

Figure 2. Prime cordial labelling of Sf_8.

Case 1: n is even, n0(mod3) p(v0)=2, p(vi)=4i; 1in2 pvn2+1=3, pvn2+2=1, pvn2+3=11, p(vi+1)=p(vi)+4; n2+3in1 p(w1)=6, pwn2=9, p(wi+1)=p(wi)+4; for 1in21 pwn2+1=5, pwn2+2=7, pwn2+3=13, p(wi+1)=p(wi)+4; n2+3in1

In this case, we have ep(0)=ep(1)=2n.

Case 2: n is even, n1(mod3) p(v0)=2, p(vi)=4i; 1in21 pvn2=2n2, pvn2+1=3, p(vi+1)=p(vi)+4; n2+1in1 p(w1)=6, pwn21=2n, pwn2=9, p(wi+1)=p(wi)+4; 1in23 pwn2+1=1, pwn2+2=5, pwn2+3=13, p(wi+1)=p(wi)+4; n2+3in1

We can see that ep(0)=ep(1)=2n in this case.

Case 3: n is even, n2(mod3) p(v0)=2, p(vi)=4i; 1in21 pvn2=3, pvn2+1=1, pvn2+2=11, p(vi+1)=p(vi)+4; n2+2in3 p(vn1)=2n2, p(vn)=2n, p(w1)=6,p(wn)=2n1 p(wi+1)=p(wi)+4; 1in23 pwn21=9, pwn2=5, pwn2+1=7,pwn2+2=13, p(wi+1)=p(wi)+4; n2+2in2

According to this labelling scheme, ep(0)=ep(1)=2n.

Case 4: n is odd, n0(mod3) p(v0)=2, p(vi)=4i; 1in2 pvn2=2n, pvn2+1=3, pvn2+2=5,pvn2+3=13, p(vi+1)=p(vi)+4; n2+3in1 p(w1)=6, p(wi+1)=p(wi)+4; 1in22 pwn2=1, pwn2=9, pwn2+1=7, p(wi+1)=p(wi)+4; n2+1in1

Here, ep(0)=ep(1)=2n.

Case 5: n is odd, n1(mod3) p(v0)=2, p(vi)=4i; 1in2 pvn2=3, pvn2+1=1, pvn2+2=5, pvn2+3=13, p(vi+1)=p(vi)+4; n2+3in2 p(vn)=2n, p(w1)=6, p(wi+1)=p(wi)+4; 1in22 pwn21=9, pwn2=2n1, pwn2+1=7, p(wi+1)=p(wi)+4; n2+1in1

This labelling scheme gives ep(0)=ep(1)=2n.

Case 6: n is odd, n2(mod3) p(v0)=2, p(v1)=2n, p(v2)=6, p(vi+1)=p(vi)+4; 2in21 pvn2=3, pvn2+1=9, pvn2+2=7, p(vi+1)=p(vi)+4; n2+2in1 p(wi)=4i; 1i<n2 pwn2=2n1, pwn2+1=1, pwn2+2=5, pwn2+3=13, p(wi+1)=p(wi)+4; n2+3in2 p(wn)=2n+1

By this labelling scheme, we get ep(0)=ep(1)=2n. So, in all the cases discussed above, it can be observed that|ep(0)ep(1)|1. Consequently, we can say that Sfn is prime cordial for n6.

Theorem 3:

The graph obtained by joining two copies of sunflower planar graph Sfn by a path of finite length is prime cordial.

Proof: Let.

Here we define the labelling function p:V(G){1,2,3,,4n+k+2} as follows.

Case 1: k=2 p(v0=u1)=2, p(v1)=4, p(vi+1)=p(vi)+4;1in1 p(w1)=6, p(wi+1)=p(wi)+4; 1in1 p(v0=u2)=1, p(v1)=3, p(vi+1)=p(vi)+4; 1in1 p(w1)=5, p(wi+1)=p(wi)+4; 1in1

Case 2: k=3 p(u1=v0)=4, p(u3=v0)=2,p(u2)=4n+3, p(v1)=6, p(v2)=12, p(v3)=8, p(v4)=16, p(vi+1)=p(vi)+4; 4in1 p(w1)=9, p(w2)=10, p(w3)=14, p(wi+1)=p(wi)+4; 3in1 p(v1)=1, p(v2)=3, p(v3)=1,p(v4)=13, p(v5)=19, p(vi+1)=p(vi)+4; 5in1 p(w1)=5, p(w2)=7, p(w3)=11, p(w4)=17, p(wi+1)=p(wi)+4; 4in1

Case 3: k is even, k4 p(v0=u1)=4, p(v1)=6, p(vi+1)=p(vi)+4; 1in1 p(w1)=8, p(wi+1)=p(wi)+4; 1in1 p(v0=uk)=2, p(v1)=1, p(v2)=3, p(v3)=9, p(v4)=13, p(vi+1)=p(vi)+4; 4in1 p(w1)=5, p(w2)=7 p(wi+1)=p(wi)+4; 2in1 p(ui)=4n+2i+2; 2ik21 puk2=4n+k1 p(ui+1)=p(ui)2; k2ik2

Case 4: k is odd, k5 p(v0=u1)=4, p(v1)=6, p(vi+1)=p(vi)+4; 1in1 p(w1)=8, p(wi+1)=p(wi)+4; 1in1 p(v0=uk)=2, p(v1)=1, p(v2)=3, p(v3)=9,p(v4)=15, p(v5)=17, p(vi+1)=p(vi)+4; 5in1 p(w1)=5, p(w2)=7, p(w3)=11,p(w4)=13, p(w5)=19, p(wi+1)=p(wi)+4; 5in1 p(ui)=4n+2i+2; 2ik21 puk2=4n+k, p(ui+1)=p(ui)2; k2ik2.

According to the labelling scheme defined above we have ep(0)=ep(1)=2n+(k/2).

It can be easily observed that the labelling scheme defined in each case is according to the criteria of prime cordial labelling. So, the graph is prime cordial Figure .

Figure 3. Prime cordial labelling of graph having two copies of Sf8 P7Sf8 P7.

Figure 3. Prime cordial labelling of graph having two copies of Sf8 P7Sf8 P7.

4. Conclusion

It is very challenging and captivating to examine whether a graph is prime cordial or not. In this paper we have contributed some new families of graphs to the family of prime cordial graphs like sunflower graph, double comb graph, sunflower graph and duplication of sunflower graph. The defined labelling schemes are demonstrated by illustrations for better perception of derived results.

It would be interesting to investigate the prime cordiality of other families of graphs by using graphical transformations of the present studied graphs.

Acknowledgement

Authors are highly grateful to reviewers for their valuable comments which helped in improvement of the article.

Disclosure statement

No potential conflict of interest was reported by the author(s).

References

  • Gallian JA. A dynamic survey of graph labeling. Electron J Comb. 2009;16(6):1–219.
  • Cahit I. Cordial graphs, a weaker version of graceful and harmonious graphs. Ars Comb. 1987;23:201–207.
  • Babujee JB, Shobana L. Cordial languages and cordial numbers. J Appl Comput Sci Math. 2012;6(13):9–12.
  • Ho YS, Lee SM, Shee SC. Cordial labelings of unicyclic graphs and generalized Petersen graphs. Congr Numer. 1988;68:109–122.
  • Raj PLR, Koilraj S. Cordial labeling for the splitting graph of some standard graphs. Int J Math. Soft Comput. 2011;1(1):89–104.
  • Sundaram M, Ponraj R, Somasundram S. Prime cordial labeling of graphs. J Indian Acad Math. 2005;27(2):373–390.
  • Vaidya SK, Vihol PL. Prime cordial labeling for some graphs. Mod Appl Sci. 2010;4(8):119.
  • Vaidya SK, Shah NH. Prime cordial labeling of some wheel related graphs. Malaya J Mat. 2013;4(1):148–156.
  • Babitha S, Babujee JB. Prime cordial labeling on graphs. Int J Math Sci. 2013;7(1):43–48.
  • Andar M, Boxwala S, Limaye NB. Cordial labelings of some wheel related graphs. J. Combin. Math. Combin. Comput. 2002;41:203–208.
  • Ghodasara GV, Jena JP. Prime cordial labeling of the graphs related to cycle with one chord, twin chords and triangle. Int J Pure Appl Math. 2013;89(1):79–87.
  • Haque KMM, Xiaohui L, Yuansheng Y, et al. Prime cordial labeling of flower snark and related graphs. Ars Combinatoria. 2012;2012(105):45–52.
  • Haque KMM, Xiaohui L, Yuansheng Y, et al. On the prime cordial labeling of generalized Petersen graph. Utilitas Mathematica. 2010;2010(82):71–79.
  • Seoud MA, Salim MA. Two upper bounds of prime cordial graphs. J. Combin. Math. Combin. Comput. 2010;2010:75–95.
  • Marin M, Ellahi R, Chirilă A. On solutions of Saint-Venant’s problem for elastic dipolar bodies with voids. Carpathian J Math. 2017;33(2):219–232.
  • Marin M, Vlase S, Ellahi R, et al. On the partition of energies for the backward in time problem of thermoelastic materials with a dipolar structure. Symmetry (Basel). 2019;11(7):863.
  • Gross JL, Yellen J. Graph theory and its applications. Boca Raton (FL): CRC press; 2005.