Extended vertex product cordial (evpc) labeling of graphs

In this paper we discuss a new type of labeling called as extended vertex product cordial Labeling. (evpcl). We allow the vertices of a graph to take values from 0 to p-1,p being the number of vertices of a graph, and restrict the edges to take values 0 or 1 only. We show that path Pn, Star K1,n., Crown of Cn, Path union of C3 i.e. Pn(C3), Antena (C3,m) are evpc graphs.

Illustrations explain the paper; they do not show study data.

AI-generated illustration

↗ Enlarge

EVPC Labeling LogicClose ×

AI-generated conceptual illustration (mathematical graph consisting of vertices and edges). It explains the idea and does not show study data.

Open full-size image ↗

Introduction

A labeling which assigns number 0 or 1 to vertices (or edges) by some function is binary or cordial labeling. Let G be a (p,q) graph .The word cordial was used first time by Cahit in 1996.[3] In the present case we define a bijective function f : V(G) →{0,1,2..,p-1}. This introduces f+:E(G)→{0,1}such that (uv)ϵE(G) then f+(uv) = f(u)f(v)(mod 2). Further the condition is satisfied that |ef(0)-ef(1)|≤1.

This condition is called as pairity condition. Thus the edge labels are restricted to take values 0 or 1 only. The label is cordial labeling. In discription that follows further we use the letter f for describing edge labels when confusion with f as a vertex label function as above is not possible.

A graph that satisfies the conditions for evpc is called as evpc graph and the corresponding function f as above is evpc function. Further f is evpc function means that the graph G is evpc graph. We use ef(0,1)= (a,b) to indicate number of edges with label 0 are a in number and that with label 1 are b in number under the evpc labeling function f. 1. Definitions 1.1 Path Pn It is sequences of vertices and edges given by v1, e1, v2, e2,...en-1,vn It has n vertices and n-1 edges. 1.2 Antena graph Consider a G=(p, q) graph.

At each of it’s vertex attach a path of length m.then we get a antena graph antena (G, m).If we attach K antennas of different length at each vertex of G then it is k-antena(G). 1.3 Tail graph Tail(G, m) has a path of length m attached at a suitable vertex on it with end point of path of degree at least. 1.4 Crown of G is obtained by attaching a pendent edge at each vertex of G. It was defined for cycle Cn and hence the name. 1.5 Path union of G. Pn(G) is obtained by attaching a copy of G at every vertex of Pn. The same fixed point on G is used to obtain Pn(G).

Here we discuss Pn(C3). 2.1 Theorem A path Pn is evpcl iff n is an even number. Proof: Let the graph G = Pn with ordinary labeling be given as (v1, e1, v2, e2,..,en-1,vn).Note that |V(Pn)|= n and |E(Pn)|= n-1.Let n be even number given by 2x. Define a function f:V(P2x)→{0,1,2..,2x-1} as follows: Maths 2018; 3(1): 272-274 Mukund Bapat Hindale, Devgad, Sindhudurg, Maharashtra, India Correspondence Mukund Bapat Hindale, Devgad, Sindhudurg, Maharashtra, India f(vi)= 2(i-1) for i = 1,2,..,x f(vx+j)=2(j-1)+1 for j = 1,2..,x. Thus ef(0)= x and ef(1) = x-1.And the graph is evpcl.

For even n the graph is evpc graph. When n is an odd number and we include number 0 for vertex labeling, there are ௡ାଵ ଶ even numbers that must be assigned to as many vertices. We have to label consecutive vertices as even number to produce smallest number of edges with even number as a label. This produces ef(0)ൌ ௡ାଵ ଶ out of maximum n-1 edges available.

Thus there can be at most ௡ିଷ ଶedges with label 1. Thus |ef(0)-ef(1)| =2 and the graph is not evpcl. # 2.2 Theorem K1,n is evpcl iff n is a odd number. Proof: Let n be an odd number. In ordinary labeling of K1,n label the central vertex as u and the pendent vertices be u1,u2,..,un.

Define a function f:V(K1,n)→{0,1,2...,n} as follows, f(u) = 1, f(u1) = 0, f(ui)= i for i= 2,3,..n. We have and ef(0)= ௡ାଵ ଶ and ef(1) = ௡ିଵ ଶ Now if n is an even number we have ௡ ଶ +1 even numbers ( as 0 is to be included) and ௡ ଶെ1 odd numbers. Further the vertex u can’t be labeled as an even number as that will produce all edge labels as an even number. Therefore we must label vertex u as an odd number.

Consequently the number of edges with odd label numbers is smaller by 2 than ef(0). 2.3 Theorem Crown of Cn is evpc graph. Proof: The ordinary labeling of Cn be given as (v1, e1, v2, e2,..,en-1,vn,en,v1) The pendent vertex at vi be ui and the corresponding edge be ei’=(viui).G=Crown (Cn). Then |V(G)| = 2n= |E(G)|. Define a function f:V(G)→{0,1,2...,2n-1} as follows:f(ui)= 2(i-1) for i = 1,..n. f(vi)=2(i-1)+1, i = 1,2,..n.

This gives ef(0,1)=(n,n). 2.4 Theorem: for n is an even number Path union of C3 i.e.Pn (C3) is evpc graph. Proof: Let the ordinary labeling of path be (v1, e1, v2, e2,.., en-1,vn). Between vi and vi+1 two new vertices ui and wi are taken.the new edges are (viui),(uiwi),(wivi+1). Define a function f:V(G)→{0,1,2...,3n-1}.

Let n = 2x. f(vi) = 2(i-1) for i = 1,2,..,x. and f(vx+i) = 2(i-1)+1for i = 1,2,..,x. f(ui) = f(vx)+2i for i =1,2,..x. and f(wi) = f(ux)+2i for i = 1,2,..x. f(ux+i) = f(vn)+2i for i =1,2,..x. and f(wx+i) = f(un)+2i for i = 1,2,..x. We have ef(0,1) = ( ௤ାଵ ଶ, ௤ିଵ ଶ) where q = 4n-1.The graph is evpc.In the fig 4.1 below the labeling is explained for n =6 and G = C3# Fig 4.1: P6(C3) : A labeled copy. Theorem 2.5 Antena (C3,m) is evpc. Proof.

↗ Enlarge

Figure 4Close ×

1: P6(C3) : A labeled copy.

Open full-size image ↗

Original paper figureSource PDF · page 2 ↗

Let the three vertices on C3 be v1,v2 and v3.The path Pm+1 at vertex vi be (vi,1=vi, vi,2,vi,3, ...,vi,m, vi,m+1) for i =1,2,3.Note that |V(G)| = 3m+3.Define f as follows: f(vi)=2(i-1)+1 for i =1,2,3. f(v1,j)=2(j-2),j = 2,3,..,m+1. Case m is even number say 2x. Then f(v2,j)=f(v1,m+1)+2(t+1) for j = x+t,t=0,1,2..x,x+1 f(v2,x+j) = 5+ 2(j-1) for j= 2,3,..,x-1 f(v3,j)=f(v2,x-1)+2(j-1), j=2, 3, 4,..m+1. The number distribution is ef(0,1) = (t+1,t), t = ଷ௠ାଶ ଶ Fig 4.2: Antena (C3, 3) A labeled evpc graph Case m is odd number say 2x+1 f(v2,j)= f(v1,m+1)+2(j-x) for j=x+1,x+2,...,2x+1 f(v2,j)=5+ 2(j-1),j=2,3,..x. f(v3,j)=f(v2,x)+2(j-1), j=2,3,4,..m+1.

The number distribution is ef(0,1) = (t,t),t = ଷ௠ାଷ ଶ Theorem 4.6 Tail(C3,m) is evpc graph.(m=1,2,..) Proof: Tail(C3,m)has a path of length m attached at a vertex and the end vertex of the path is of degree 3 or more. We consider the end degree vertex of path of degree 3 .The ordinary labeling of the graph be u,v, w as cycle vertices and tail attached at point u be (u=u1,u2,u3,..,um+1). The two pendent vertices be x and y respectively. Define a function as f:V(G)→{0,1,2..,m+4} given as f(u)=1,f(v)=3,f(w)=5,f(x)=0,f(y)=2,f(um+1)=4 for m is even number say 2x then, f(uj)= 5+2(j-1) for j = 2,3,..,x f(ux+j)=2x+4-2(j-1), j = 1,2,..,x.

Number distribution is ef(0,1) = (3+x,2+x). For m is a odd number say 2x+1( x=0,1,2,..) we have, f(uj) = 5+2(j-1) for j = 2,3,..,x+1 and f(ux+j)=2x+4-(j-2)2, j =2,3,..x,x+1.We have number distribution ef(0,1) = (2+x,2+x)#

Conclusions

In this paper we discuss a new type of graph labeling. We show that certain graph families are evpc families. A well-known graph Cn is not found to be evpc.

1. Bapat Mukund. Some vertex Prime Graphs and A New Type of Graph Labeling, IJMTT, 2017; 47(459):23-29.
2. Bapat Mukund MV, Limaye NB. Some families of E3-cordial graphs, Proceedings of the National conference on Graphs, Combinatorics, Algorithm & application at Anandnagar, Krishnankoli, 2004.
3. Cahit I. Cordial graphs, A weaker version of graceful and harmonious graphs, Ars combinatoria, 1987; 23:201-207.
4. Cahit I, Yilmaz R. E3-cordial graphs, Ars Combinatoria, 2000; 54:119-127.
5. Gallian JA. A dynamic survey of graph labellings. Electronic Journal of Combinatorics. 2015; 7:DS6.
6. Harary F. Graph Theory, Narosa Publishing House, New Delhi.