Some path unions invariance under cordial labeling

Introduction

The graphs we consider are simple, finite, undirected and connected. For terminology and definitions we depend on Graph Theory by Harary, A dynamic survey of graph labeling by J. Gallian and Douglas West. I. Cahit introduced the concept of cordial labeling. f:V(G){0,1} be a function. From this label of any edge (uv) is given by |f (u)-f (v) |. Further number of vertices labeled with 0 i.e v f (0) and the number of vertices labeled with 1 i.e.v f (1) differ at most by one. Similarly number of edges labeled with 0 i.e.e f (0) and number of edges labeled with 1 i.e.e f (1) differ by atmost one.Then the function f is called as cordial labeling. Cahit has shown that: every tree is cordial; Kn is cordial if and only if n ≤ 3; K m,n is cordial for all m and n; the friendship graph C 3 (t) (i.e., the one-point union of t copies of C 3 ) is cordial if and only if t 6≡ 2 (mod 4); all fans are cordial; the wheel W n is cordial if and only if n 6≡ 3 (mod 4).A lot of work has been done in this type of labeling. One may refer dynamic survey by J. Gallian. We have defined path unions on different graphs inparticular on bull graph. For the same given graph there are many path union P m (G) structures possible. It depends on which point on G is used to fuse with vertex on P m . If this point is changed and path union is designed then it may be a different (upto isomorphism) structure. We show that for G = bull on C 3 ,bull on C 4 ,C 3 + ,C 4 + -e the different path union P m (G) are cordial. It is called as invariance under cordial labeling. We use the convention that v f (0,1) = (a,b) to indicate the number of vertices labeled with 0 are a and that numbe of vertices labeled with 1 are b. Further e f (0,1) = (x,y) we mean the number of edges labeled with o are x and number of edges labeled with 1 are y.

Preliminaries

The Bull graph on C 3 is defined in We generalize the definition of bull graph. Let G be a (p,q) graph. Choose any two adjacent vertices of G say u and v. Attach an pendent edge each to u and v. It is denoted by bull(G). Thus bull graph of G has P+2 vertices and q+2 edges. The graph G + is obtained by fusing an edge at each vertex of G. We call this graph as G-crown and denote it by G + . The concept was developed for crown graph which is an cycle Cn to each of it's vertex a pendent edge is attached and denoted by C n + . G + -e is obtained from G + by deleting an pendent edge of G + . When G = Cn or Kn deleting any pendent edge from G + makes no difference. Otherwise one has to specify which edge is deleted. Fusion of vertex. Let u ϵ V (G 1 ) and vϵV (G 2 ).By fusing vertex u with v we replace these two vertices by a single vertex say w and all edges incident to u in G 1 and that incident with v in G 2 are incident with w. If u and v are from the same graph G still the same procedure is followed and loops are deleted if any is formed. Some times this is called as u is identified with v.

),c i,2 =(u i,2 u i,3 ),c i,3 =(u i,3 u i,1 )} U { x i,1 =(u i,2 w i,1 ),x i,2 =(u i,3 w i,2 )} There are three non isomorphic structures possible on G. Structure 1, structure 2 and structure 3.  To obtain Structure 1 graph we fuse vertex u i,1 on bull with v i on path Pm.  To obtain structure 2 graph we fuse vertex u i,2 on bull with v i on path Pm.  To obtain structure 3 we fuse vertex w i,1 on bull with v i on path Pm. We further design unit X and unit Y for each structure as shown in figures below.

Fig 1: C3-bull also called as bull graph

To obtain a path union of larger m>2size, take two copies of type X. By an edge (ab) join the two copies. Here the vertex a is from one copy and b is from other copy. The edge label of (ab) = |1-0| =1. Repeat the process and we will get the path union on even m. For odd m say m = 2t+1 we first obtain the path union on m= 2t and attach type y to the vertex a on P 2t (bull) by an edge (ab), the vertex b is from type y. The label of (ab) will be 1.The label number distribution is for m = 2t, we have v f (0,1)= (5t,5t), e f (0,1)=(6t,6t-1). For m = 2t+1 we have v f (0,1)= (5t+2,5t+3),e f (0,1)=(6t+3,6t+2).It follows that the graph is cordial.

The procedure given above is followed for all three structures and we get cordial graph with same label numbers as above.

Theorem: Path union of C3 + i.e. G = Pm(C3 + )is cordial.

There are two types of structures possible on path union. In one type (structure 1) we use any of the three degree vertex on C 3 crown to fuse with vertex on path P m . In second type (structure 2) we use any of the pendent vertex of C 3 crown to fuse with vertex on path Pm to obtain G. :Type X

To design structure 1 we start with A type of copy of graph C 3 + .To obtain P 2 (C3+) we attach a copy of type B by an edge to copy of type A of graph. Here new edge is (uv) where u lies on type A graph and v lies on type B graph. and the new edge label is 1.At this stage label number distribution is v f (0,1)= (6,6), e f (0,1)=(6,7) and the graph is cordial. To obtain P 3 (C 3 + ) we choose type B labeling to attach at vertex v of P 2 (C 3 + ).The new edge is (vv) with label 0.The label numbers are v f (0,1)= (9,9), e f (0,1)=(10,10). Then the sequence type A, Type B, type B followed by A,A,B,B….is repeated. The resultant graph is E-cordial.

To obtain cordial label of structure 2 we use Type A and type B labeled copies as shown below. Rest of the procedure and result is same. Thus the graph of structure 2 is also cordial.

Final label distribution is: on vertices: vf(0,1) =(3n,3n) and on n is odd number ≥ 3 given by n = 2x+1, distribution on edges e f (0,1) = (10 +7(x-1),10+7(x-1)),x=1,2,…and for even n = 2x

we have e f (0,1) = (10 +3(x-1),10+4(x-1)),x=2,3,…

Theorem: Path union on bull of C4 is cordial.

Proof: There are three non-isomorphic structures possible on Pm(C 4 bull). m ≡ 1(mod 4) type A label is used and for all other m copy type B is used to construct Pm(C 4 bull) To construct structure 3 Here also the sequence observed is type A then B,B,B, then A,B…is followed. vertex e on type B and vertex f on type A is used to add new edge and construct the path union. Thus for m ≡ 1(mod 4) type A label is used and for all other m copy type B is used to construct Pm(C 4 bull)

The label distribution for all three structures is same and given by v f (0,1)= (3m,3m), e f (0,1) = (3+7x,3+ 7x) when m = 2x+1,when m ≡ 0(mod 4) we have v f (0,1)= (3m,3m), e f (0,1) = (14x,14x), m = 4x. For m ≡2(mod 4) we have v f (0,1)= (3m,3m), e f (0,1) = (6+14x,7+14x),m= 2+14x.Thus the graph is cordial.

Theorem Let C4

+ -e be the graph obtained by deleting an pendent edge of C4 + Then G =Pm(C4 + -e) is cordial graph.

Fig 17 shows that there are five possible different structures of path unions on G. (at five different points x,y,z,w,q.) To construct different structures we start with a path Pm= (v1,v2,v3,…vm). Structure 1 Fuse the vertex g from different types to verteices on Pm as follows. For m ≡1(m0d 4) use type A For m≡2,3 (m0d 4) use B type of label and for m ≡0 (mod 4) use E type label. Resulting is cordial labeling. The label numbers observed are 1) for m = 2x,x = 1,2,.. we have v f (0,1)= (7x,7x), e f (0,1)=(8(x+1),8(x+1)-1) for m≡2(mod 4) and x is from m = 2x; and for m ≡ o(mod4), write m=2x, e f (0,1) =(8x-1,8x) 2) for m = 4x+3 (i.e. m ≡3 (mod 4)) we have v f (0,1)=(14x+10,14x+11) and e f (0,1) = (12+16x,11+16x) For m = 1+4x (i.e.m≡1(mod 4) we have v f (0,1)=(14x+4,14x+3) and e f (0,1) = (4+16x,3+16x) The resultant graph is cordial. Structure 2 Fuse the vertex b from different types to verteices on Pm as follows. For m ≡1(m0d 4) use type A For m≡2,3 (m0d 4) use B type of label and for m ≡0 (mod 4) use E type label. Resulting is cordial labeling. The label numbers observed are 1) for m = 2x,x = 1,2,.. we have v f (0,1)= (7x,7x), e f (0,1)=(8(x+1),8(x+1)-1)for m≡2(mod 4) and x is from m = 2x; and for m ≡ o(mod4), write m=2x, e f (0,1) =(8x-1,8x) 2) for m = 4x+3 (i.e. m ≡3 (mod 4)) we have v f (0,1)=(14x+10,14x+11) and e f (0,1) = (12+16x,11+16x) For m = 1+4x (i.e.m≡1(mod 4) we have v f (0,1)=(14x+4,14x+3) and e f (0,1) = (4+16x,3+16x) The resultant graph is cordial. Structure 3 Fuse the vertex f from different types to verteices on Pm as follows. For m ≡1(m0d 4) use type A For m≡2,3 (m0d 4) use B type of label and for m ≡0 (mod 4) use E type label. Resulting is cordial labeling. The label numbers observed are 1) for m = 2x,x = 1,2,.. we have v f (0,1)= (7x,7x), e f (0,1)=(8(x+1),8(x+1)-1)for m≡2(mod 4) and x is from m = 2x; and for m ≡ o(mod4), write m=2x, e f (0,1) =(8x-1,8x) 2) for m = 4x+3 (i.e. m ≡3 (mod 4)) we have v f (0,1)=(14x+10,14x+11) and e f (0,1) = (12+16x,11+16x) For m = 1+4x (i.e.m≡1(mod 4) we have v f (0,1)=(14x+4,14x+3) and e f (0,1) = (4+16x,3+16x) The resultant graph is cordial. Structure 4 Fuse the vertex d from different types to verteices on Pm as follows. For m ≡1(m0d 4) use type A For m≡2,3 (m0d 4) use B type of label and for m ≡0 (mod 4) use E type label. Resulting is cordial labeling. The label numbers observed are 1) for m = 2x,x = 1,2,.. we have v f (0,1)= (7x,7x), e f (0,1)=(8(x+1),8(x+1)-1)for m≡2(mod 4) and x is from m = 2x; and for m ≡ o(mod4), write m=2x, e f (0,1) =(8x-1,8x) 2) for m = 4x+3 (i.e. m ≡3 (mod 4)) we have v f (0,1)=(14x+10,14x+11) and e f (0,1) = (12+16x,11+16x) For m = 1+4x (i.e.m≡1(mod 4) we have v f (0,1)=(14x+4,14x+3) and e f (0,1) = (4+16x,3+16x) The resultant graph is cordial.

Structure 5 Fuse the vertex c from different types to verteices on Pm as follows. For m ≡1(m0d 4) use type A For m≡2,3 (m0d 4) use B type of label and for m ≡0 (mod 4) use F type label. Resulting is cordial labeling. The label numbers observed are 1) for m = 2x,x = 1,2,.. we have v f (0,1)= (7x,7x), e f (0,1)=(8(x+1),8(x+1)-1)for m≡2(mod 4) and x is from m = 2x; and for m ≡ o(mod4), write m=2x, e f (0,1) =(8x-1,8x) 2) for m = 4x+3 (i.e. m ≡3 (mod 4)) we have v f (0,1)=(14x+10,14x+11) and e f (0,1) = (12+16x,11+16x) For m = 1+4x (i.e.m≡1(mod 4) we have v f (0,1)=(14x+4,14x+3) and e f (0,1) = (4+16x,3+16x) The resultant graph is cordial.

Conclusion

So far a specific graph only was called as bull graph. We have generalized the definition of bull graph to any graph G. Then we have designed path union on bull type of graphs. We have further shown all possible structures (upto isomorphism) on path union follow cordial labeling. (invariance under cordiality)

References

1. Andar M, Boxwala S, Limaye N. New families of cordial graphs. J. Combin. Math. Combin. Comput. 2005; 53(134):117-154.
2. Andar M, Boxwala S, Limaye N. On the cordiality of the t-ply Pt(u,v), Ars Combin. 2005; 77(135):245-259.
3. Bapat Mukund Ph.D. thesis submitted to university of Mumbai. India, 2004.
4. Cahit I. Cordial graphs: a weaker version of graceful and harmonious graphs, Ars Combin. 1987; 23:201-207.