E-cordial labeling of bull related graphs and invariance

A bull graph has a copy of C3 with pendent edge attached at two (adjacent) vertices. Similar structure is obtained on cycles C4, C5. We obtain e- cordial labeling of these graphs and one point union of these graphs. Further we show that one point union structures are invariant under e-cordial labeling.

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

AI-generated illustration

↗ Enlarge

General Bull Graph StructureClose ×

AI-generated conceptual illustration (A mathematical bull graph structure consisting of a cycle of vertices and two pendent edges). It explains the idea and does not show study data.

Open full-size image ↗

AI-generated illustration

↗ Enlarge

One Point Union ConceptClose ×

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

Open full-size image ↗

Introduction

In 1997 Yilmaz and Cahit [4] introduced a weaker version of edge graceful labeling called Ecordial. The word cordial was used first time in this paper. Let G be a graph with vertex set V and edge set E. Let f be a function that maps E into {0, 1}. Define f on V by f(v) = ∑{𝑓(𝑢𝑣)/ (𝑢𝑣)Є E}(mod 2). The function f is called as E cordial labeling if |ef(0)-ef(1)|≤1 and |vf(0)vf(1)|≤1. Where ef(i) is the number of edges labeled with i = 0,1 and vf (i) is the number of vertices labeled with i = 0,1. We also use vf(0,1) = (a,b) to denote the number of vertices labeled with 0 are a and that with 1 are b in number. Similarly ef(0,1)=(x, y) to denote number of edges labeled with 0 are x and that labeled with 1 are y in number respectively. A lot of work has been done in this type of labeling and the above mentioned paper gave rise to number of papers on cordial labeling. A graph that admits E-cordial labeling is called as Ecordial graph. Yilmaz and Cahit has shown that Trees Tn with n vertices and Complete graphs Kn on n vertices are Ecordial iff n is not congruent to 2 (modulo 4). Friendship graph C3 (n) for all n and fans Fn for n not congruent to1 (mod 4).One may refer A Dynamic survey of graph labeling for more details on completed work. A bull graph consists of C3 and two pendent vertices one each at adjacent vertices. It has 5 edges and 5 vertices. This concept we generalize for all Cn. A general bull graph bull(Cn) consists of a cycle and a pendent edge each at two adjacent vertices. It has n+2 vertices and n+2 edges. We obtain e-cordial labeling of G = bull(Cn) for n = 3, 4, 5…n. Also we define one point union of G on k copies and obtain different structures by changing common point of union on G. We show that all these structures are e-cordial. This is referred as invariance under e-cordial labeling.

Preliminaries

By one point union of k copies of graph G we fuse k copies of G at fixed vertex of G. It is denoted by G (k) . It has kq edges and Pk-k+1 vertices. We choose G as bull(Cn) with n = 3,4,5. Fusion of vertex. Let G be a (p,q) graph. let u≠v be two vertices of G. We replace them with single vertex w and all edges incident with u and that with v are made incident with w. If a loop is formed is deleted. The new graph has p-1vertices and at least q-1 edges [5] .

Theorems Proved 3.1

A bull graph is e-cordial. All structures on one point union of bull graph denoted by (bull(C3)) (k) are e-cordial. Proof. Define a function f: E(G){0,1}where G = (bull) (k) . From the diagram below it follows that the bull graph is e-cordial. Structure 1: First obtain one point union at point 'c' on bull graph for k = 2x, x=1, 2, 3…This is done by repeatedly fusing type B labeled copy at point c on it. The structure has label number distribution given by vf(0,1) = (4x+1,4x), ef(0,1)=(5x,5x).To obtain labeled copy of bull graph on k = 2x+1 copies, x= 0, 1, 2,…We first obtain (bull) (2x) and fuse it at vertex 'c' on it with vertex 'c' on type B label. The resultant structure has label number distribution given by vf(0,1) = (4x+3,4x+2), ef(0,1)=(5x+3,5x+2). Structure 3: First obtain one point union at point 'a' on bull graph for k = 2x, x=1, 2, 3…This is done by repeatedly fusing type C labeled copy at point 'a' on it. The structure has label number distribution given by vf(0,1) = (4x+1,4x), ef(0,1)=(5x,5x).To obtain labeled copy of bull graph on k = 2x+1 copies, x= 0, 1, 2,…We first obtain (bull) (2x) and fuse it at vertex 'a' on it with vertex 'a' on type B label. The resultant structure has label number distribution given by vf(0,1) = (4x+3,4x+2), ef(0,1)=(5x+3,5x+2).These three structures are pairwise non-isomorphic. All of them are shown to be E-cordial.

Theorem:

A bull graph on C4 denoted by bull(C4) is not e-cordial. But all structures on one point union of bull(C4) graph denoted by (bull(C4)) (k) , for k not congruent to 1,3 (mod 4), are e-cordial.

Proof: Define a function f: E(G){0,1}where G = (bull(C4)) (k) .

It follows from copy of bull(C5) in fig 4.9 that we can take one point union at vertices 'a', 'b', 'c' and 'd' to get four different ( pair wise non-isomorphic) structures. In all structures Type A label will serve as G (k) at k =1.For rest of values of k we first obtain G (2x) first and append it with copy type A by fusing with appropriate vertex on it.

↗ Enlarge

Figure 4Close ×

4: vf(0,1) = (5,4), ef(0,1)=(5,5).The numbers are edge

Open full-size image ↗

Original paper figureSource PDF · page 2 ↗

↗ Enlarge

Figure 4Close ×

3: vf(0,1) = (5,4), ef(0,1)=(5,5).The numbers are edge

Open full-size image ↗

Original paper figureSource PDF · page 2 ↗

↗ Enlarge

Figure 4Close ×

2: vf(0,1) = (5,4), ef(0,1)=(5,5).The numbers are edge

Open full-size image ↗

Original paper figureSource PDF · page 2 ↗

↗ Enlarge

Figure 4Close ×

1: vf(0,1) = (3,2), ef(0,1)=(3,2).The numbers are edge

Open full-size image ↗

Original paper figureSource PDF · page 2 ↗

To obtain structure 1 we fuse Type B label at vertex 'c' on it for x times and we get labeled copy of G (2x) , x = 1, 2, 3, ...To get labeled copy of G (2x+1) we first obtain G (2x) and append it with copy of type A label by fusing both at vertex 'c' on it.

To obtain structure 2 we fuse Type C label at vertex 'd' on it for x times and we get labeled copy of G (2x) , x = 1, 2, 3, ...To get labeled copy of G (2x+1) we first obtain G (2x) and append it with copy of type A label by fusing both at vertex 'd' on it.

To obtain structure 3 we fuse Type D label at vertex 'b' on it for x times and we get labeled copy of G (2x) , x = 1, 2, 3, ...To get labeled copy of G (2x+1) we first obtain G (2x) and append it with copy of type A label by fusing both at vertex 'b' on it.

To obtain structure 4 we fuse Type E label at vertex 'a' on it for x times and we get labeled copy of G (2x) , x = 1, 2, 3, ...To get labeled copy of G (2x+1) we first obtain G (2x) and append it with copy of type A label by fusing both at vertex 'a' on it. For all structures resultant label number distribution is for vertices vf(0,1) = (6x+1,6x), and for edges ef(0,1)=(7x,7x) when k = 2x, x=1, 2, 3, ..And when k = 2x+1 we have on vertices vf(0,1) = (6x+3,6x+4) and on edges ef(0,1)=(7x+4,7x+3). Thus in all structures we get e-cordial labeling of G (K) . We conclude our paper showing that G= bull(Cn) is e-cordial.( for all n is not divisible by 4).

Theorem:

A bull graph on C5 denoted by G=bull(C5) is e-cordial. We take three cases on n. At the case n = 4x the e-cordial labeling is not available.

Define a function f:E(G){0,1} as follows.

Case n = 4x+3.G=bull(C4x+3) has 4x+5 edges and 4x+5 vertices.We start with a cycle C4x=(v1, e1, v2, e2, v3, e3..v4x, e4x), with pendent edges c1 and c2 attached respectively at v1 and v2.Define f:V(G){0,1} as: f(ei)=1, for i = 1,3,5,7…2p-1 (p=1,2,..x).f(ei)=0 for i=2,4,..2x; f(e2x+J)=1 for j=1, 2, ..x,x+1, x+2.And for all rest i. f(ei) = 0.Further f(c1)=0,f(c2)=1.The label number distribution is vf(0,1)=(2x+2,2x+3), ef(0,1) = (2x+3,2x+2).

Case n = 4x+2.G=bull(C4x+2) has 4x+4 edges and 4x+4 vertices.We start with a cycle C4x=(v1, e1, v2, e2, v3, e3..v4x, e4x), with pendent edges c1 and c2 attached respectively at v1 and v2Define f:V(G){0,1} as: f(ei)=1, for i = 1, 3, ..2x-1, f(ei)=0 for i= 2,4,6,..2x.f(ei)=1 for i = 2x+1 to 2x+7.f(ei)=0 for I 2x+8 to 2x+n.f(c1)=0,f(c2)=1. The label number distribution is vf(0,1)=(2x+2,2x+2), ef(0,1) = (2x+2,2x+2)

Case n = 4x+1.G=bull(C4x+1) has 4x+3 edges and 4x+3 vertices. We start with a cycle C4x=(v1, e1, v2, e2, v3, e3..v4x, e4x),with pendent edges c1 and c2 attached respectively at v1 and v2.Define f:V(G){0,1} as: f(ei)=1, for i = 1, 3, ..2x-1, f(ei)=0 for i= 2,4,6,..2x.f(ei)=1 for i = 2x+1 to 2x+7.f(ei)=0 for I 2x+8 to 2x+n.f(c1)=0,f(c2)=1. The label number distribution is vf(0,1)=(2x+1,2x+2), ef(0,1) = (2x+1,2x+2). Conclusions: We have defined bull graph bull(G) and shown that G=Bull(Cn), n= 3,4,5. is E-cordial. Also we have shown for n = 3, 4, 5 that G (k) with all non-isomorphic structures are E-cordial. It is necessary to investigate e-cordiality for all G (K) for all k where G = bull(Cn).We predict that all structures onG (k) are e-cordial. When G has vertices say q and q-2 is divisible by 4 then G (k) is e-cordial for k is even number.

1. Bapat MV. Ph.D. thesis, University Of Mumbai, 2004.
2. Joe Gallian. Dynamic survey of graph labeling, 2016.