Product cordiality of path union of mix graphs

We obtain mixed path union Pm (G1, G2) and discuss it for product cordiality, where G1 and G2 are from C3, C4, bull graph. In this type of path union G1 and G2 are fused at alternate vertices of Pm. Note that the minimum length of a mixed path union is 2 if we have to notice that it is a mixed path union.

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

AI-generated illustration

↗ Enlarge

Mixed Path 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

The graphs we consider are simple, finite, undirected and connected. For terminology and definitions we depend on Graph Theory by Harary [9] , a dynamic survey of graph labeling by J. Gallian [8] and Douglas West. [11] . I. Cahit introduced the concept of cordial labeling [7] . There are variety of cordial labeling available in labeling of graphs. Sundaram, Ponraj, and Somasundaram [10] introduced the notion of product cordial labeling. A product cordial labeling of a graph G with vertex set V is a function f from V to {0, 1} such that if each edge uv is assigned the label f (u) f (v), the number of vertices labeled with 0 and the number of vertices labeled with 1 differ by at most 1, and the number of edges labeled with 0 and the number of edges labeled with 1 differ by at most 1. A graph with a product cordial labeling is called a product cordial graph. We use v f (0, 1) = (a, b) to denote the number of vertices with label 1 are a in number and the number of vertices with label 0 are b in number. Similar notion on edges follows for e f (0, 1) = (x, y). A lot of work is done in this type of labeling so far. One interested in survey may refer Dynamic survey in Graph labeling by J. Gillian. We mention some part of it. Sundaram, Ponraj, and Somasundaram have shown that trees; unicyclic graphs of odd order; triangular snakes; dragons; helms; Pm∪Pn; Cm∪Pn; Pm∪K1,n; Wm∪Fn (Fn is the fan Pn + K1); K1,m∪K1,n; Wm∪ K1,n; Wm ∪Pn; Wm ∪Cn; the total graph of Pn (the total graph of Pn has vertex set V (Pn) ∪E (Pn) with two vertices adjacent whenever they are neighbors in Pn); Cn if and only if n is odd; C n (t) , the one-point union of t copies of C n , provided t is even or both t and n are even; K2+mK1 if and only if m is odd; C m ∪P n if and only if m+n is odd; K m,n ∪Ps if s > mn; Cn+2∪K1,n; Kn∪Kn, (n-1)/2 when n is odd; Kn∪Kn-1,n/2 when n is even; and P2 n if and only if n is odd. Are product cordial graphs. They also prove that K m,n (m, n > 2), P m × P n (m,n > 2) and wheels are not product cordial and if a (p, q)-graph is product cordial graph, then q = 6 (p-1) (p + 1)/4 + 1. In this paper we show that P m (G 1 , G 2 ) where G 1 and G 2 from {C 3 , C 4 , bull graph} are product cordial graphs.

Preliminaries 2.1 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. If uϵG 1 and vϵG 2 , where G 1 is (p 1 , q 1 ) and G 2 is (p 2 , q 2 ) graph. Take a new vertex w and all the edges incident to u and v are joined to w and vertices u and v are deleted. The new graph has p 1 +p 2 -1 vertices and q 1 + q 2 edges. Sometimes this is referred as u is identified with the concept is well elaborated in John Clark, Holton [6] A bull graph bull (G) was initially defined for a C 3 -bull. It has a copy of G with an pendent edge each fused with any two adjacent vertices of G. For G is a (p, q) graph, bull (G) has p+2 vertices and q+2 edges. In this we refer bull graph to C3-bull [11] . Path union of G, i.e. P m (G) is obtained by taking a path p m and take m copies of graph G. Then fuse a copy each of G at every vertex of path at given fixed point on G. It has mp vertices and mq + m-1 edges. Where G is a (p, q) graph. Mixed path union P m (G 1 , G 2 ) is obtained by taking a path P m = (v 1 , e 1 , v 2 , e 2 ,.. v m ) and at v i of it a copy of G 1 is fused if i ≡ 1 (mod 2) and a copy of G 2 is fused if i ≡ 0(mod 2) at a fixed vertex of G 1 and that of G 2 where G 1 = (p 1 , q 1 ) and G 2 is (p 2 , q 2 ) graph. It is important to note that P m (G 1 , G 2 ) ≠P m (G 2 , G 1 ) ( in the sense of isomorphism). The minimum length of P m (G 1 , G 2 ) is m = 2. It has xp 1 + xp 2 vertices and xq 1 xq 2 + 2x-1 edges when m = 2x and (x+1) p 1 + xp 2 vertices and xq 1 + xq 2 + 2x+q 2 edges when m = 2x+1.

Main Results

Theorem 3.1 G = P m (G 1 ,G 2 ) is product cordial where G 1 is C 3 and G 2 is C 4 for all m as even number and odd m = 2x+1 for even x only. Proof: We take a path P m = (v 1 , e 1 , v 2 , e 2 ... v m ). At v i we fuse C 3 if i≡ 1 (mod 2) and C 4 if i ≡ 0 (mod 2) .The copy of C 3 fused at v i is given by (u i,1 , e i,1 , u i,2 , e i,2 ,u i,3 , e i,3 ,u i,1 ) and that copy of C 4 fused at v i is given by (v i,1 , e i,1 , v i,2 , e i,2 ,v i,3 , e i,3 ,v i,4, ei ,4 ,v i,1 ).Note that u i,j is same as vi, i = 1, 3,.. and v i,j is same as v i ; i The label number distribution is given by v f (0, 1) = (7x, 7x) and e f (0, 1) = (7y+x, 7y+x-1) where y = Case m = 2x+1 (only even x) To obtain a labeled copy of P m (G 1 , G 2 ) from one end we label P 2x (G 1 , G 2 ) part of P 2x+1 (G 1 , G 2 ) as above. The copy of C 3 fused at last vertex of P 2x+1 is labeled as follows: F (u i, 1 ) = 1; F (u i, 2 ) = 1; F (u i, 3 ) = 0.

The label number distribution is given by v f (0,1) = (7x+1, 7x+2) and e f (0, 1)=(7y+x+2, 7y+x+1) where y = 𝑥 2 for x is even number. # Theorem 3.2 G = P m (G 1 , G 2 ) is product cordial where G 1 is C 4 and G 2 is C 3 . For all m even number and m is odd number 2x+1 then x is odd number only. Proof: We take a path P m = (v 1 , e 1 , v 2 , e 2 ... v m ). At v i we fuse C 3 if i≡ 0 (mod 2) and C 4 if i ≡ 1 (mod 2). The copy of C 3 fused at v i is given by (u i,1 , e i,1 , u i,2 , e i,2 , u i,3 , e i,3 , u i,1 ) and that copy of C 4 fused at v i is given by (v i,1 , e i,1 , v i,2 , e i,2 , v i,3 , e i,3 , v i,4, ei ,4 , v i,1 ). Note that u i,j is same as vi, i = 2, 4, 6,.. And v i, j is same as v i ; i = 1, 3. Thus when m = 2x we have |V (G)| =7x. And| E (G) | = 9m-1 Define a function f: V (G)-{0, 1} as follows. Case m = 2x. F (u i,j ) = 0 for i = 2, 4,..x; F (v i,j )= 0 fori = 1,3,5,..,x; F (u i,j ) = 1 for i = x+2,x+ 4,..,2x; F (v i,j )= 1 for i = x+1,x+3,x+5,..,2x;

The label number distribution is given by v f (0, 1) = (7x, 7x) and e f (0, 1)=(7y+x, 7y+x-1) where y = 𝑥 2 for x is even number. When

x is odd number then v f (0,1) = (7y+4, 7y + 3) ; y = 𝑥-1 2 , e f (0, 1)=(7y+x), 7y+x-1).

Case m = 2x+1 (only odd x)

To obtain a labeled copy of P m (G 1 , G 2 ) from one end we label P 2x (G 1 , G 2 ) part of P 2x+1 (G 1 , G 2 ) as above. The copy of C 4 fused at last vertex of P 2x+1 is labeled as follows: (x is odd number) F (u i, 1 ) = 1; F (u i, 2 ) = 1; F (u i, 3 ) = 1, F (u i, 4 ) = 0. When x is odd number then v f (0,1) = (7y+5, 7y + 6) ; y = 𝑥-1 2 , e f (0,1)=(7y+x+2),7y+x+2). # Theorem 3.3 G = P m (G 1 , G 2 ) is product cordial where G 1 is C 3 and G 2 is bull graph for m= 2x, x is even number and m = 2x+1 when x is even number. Proof: We take a path P m = (v 1 , e 1 , v 2 , e 2 ... v m ). At v i we fuse C 3 if i≡ 1 (mod 2) and bull if i ≡ 0 (mod 2). The copy of C 3 fused at v i with vertex u i,1 of C 3 is given by (u i,1 , e i,1 , u i,2 , e i,2 ,u i,3 , e i,3 ,u i,1 ) and that copy of bull fused at v i at v i,1 of bull is given by {(v i,1 , e i,1 , v i,2 , e i,2 ,v i,3 , e i,3 ,v i,1 ) and pendent vertices v i,4 , v i,5 with corresponding pendent edges (v i,2 v i,4 ) and (v i,3 v i,5 ). Note that u i,j is same as v i , i = 1, 3, 5,... and v i,j is same as v Case m = 2x. F (u i,j ) = 0 fori = 1,3,5,..,x; F (v i,j ) = 0 for i = 2, 4,..,x; F (v i, 4 ) = 0, f (v i, 5 ) = 0 for i≤ x F (u i,j ) = 1 for i = x+1, x+ 3,..,2x; F (v i,j )= 1 for i = x+2, x+4, x+6,..,2x;

The label number distribution is given by v f (0,1) = (8y,8y) and e f (0,1)=(8y+x+1,8y+x-1) where y = 𝑥 2 for x is even number. When x is odd number then there is no vertex prime labeling. Case m =2x+1 To obtain a labeled copy of P m (G 1 , G 2 ) from one end we label P 2x (G 1 , G 2 ) part of P 2x+1 (G 1 , G 2 ) as above. The copy of C 3 fused at last vertex of P 2x+1 is labeled as follows: F (u i, 1 ) = 1; F (u i, 2 ) = 1; F (u i, 3 ) = 0;

The label number distribution is given by v f (0,1) = (8y+2,8y+1) and e f (0,1)=(8y+x+2,8y+x+1) where y = 𝑥 2 for x is even number. For odd number x there is no product cordial labeling. # Theorem 3.4 G = P m (G 1 , G 2 ) is product cordial where G 1 is bull graph and G 2 is C 3 cycle for m = 2x, x is even and for all m. Proof: We take a path P m = (v 1 , e 1 , v 2 , e 2 ... v m ). At v i we fuse C 3 if i≡ 0 (mod 2) and bull if i ≡ 1 (mod 2). The copy of C 3 fused at v i with vertex u i,1 of C 3 is given by (u i,1 , e i,1 , u i,2 , e i,2 , u i,3 , e i,3 , u i,1 ) and that copy of bull fused at v i at v i,1 of bull is given by {(v i,1 , e i,1 , v i,2 , e i,2 , v i,3 , e i,3 , v i,1 ) and pendent vertices v i,4 , v i,5 with corresponding pendent edges (v i,2 v i,4 ) and (v i,3 v i,5 ). Note that u i,j is same as v i , i = 2, 4, 6,.. and v i,j is same as v i ; i = 1, 3, Case m = 2x. F (u i,j ) = 0 for i = 2,4,6,..,x; F (v i,j ) = 0 for i = 1, 3,..x; F (v i, 4 ) = 0, f (v i, 5 ) = 0; for i≤ x F (u i,j ) = 1 for i = x+2,x+ 4,.., 2x; F (v i,j )= 1 for i = x+1,x+3,x+5,.., 2x; F (v i, 4 ) = 1, f (v i, 5 ) = 1 for x ≤ i≤ 2x

The label number distribution is given by v f (0,1) = (8y,8y) and e f (0,1)=(8y+x+1,8y+x-1) where y = 𝑥 2 for x is even number. When x is odd number then there is no vertex prime labeling.

Case m = 2x+1

To obtain a labeled copy of P m (G 1 , G 2 ) from one end we label P 2x (G 1 , G 2 ) part of P 2x+1 (G 1 , G 2 ) as above. The copy of bull fused at last vertex of P 2x+1 is labeled as follows: F (u i, 1 ) = 1; F (u i, 2 ) = 1; F (u i, 3 ) = 1; F (u i, 4 ) = 0; F (u i, 5 ) = 0;

Figures and tables from the paper

↗ Enlarge

Figure 1Close ×

mixed path union on C3 and C4 with m = 6

Open full-size image ↗

Original paper figureSource PDF · page 2 ↗

1. Bapat MV. Some new families of product cordial graphs, Proceedings, Annual International conference, CMCGS, Singapore, 2017, 110-115.
2. Bapat MV. Some vertex prime graphs and a new type of graph labelling IJMTT. 2017; 47(1):23-29.
3. Bapat MV. Some complete graph related families of product cordial graphs. Arya bhatta journal of mathematics and informatics, 2018, 9(2).
4. Bapat MV. Extended Edge Vertex Cordial Labelling Of Graph, International Journal Of Math Archives IJMA Sept, 2017.
5. Bapat MV. Ph.D. Thesis, University of Mumbai, 2004.
6. Cahit I. Cordial graphs: a weaker version of graceful and harmonious graphs, Ars Combin. Harary, Theory, Narosa publishing, New Delhi. 1987; 23L201-207.
7. Gallian J. Electronic Journal of Graph Labeling (Dynamic survey), 2016.
8. Sundaram M, Ponraj R, Somasundaram S. Product cordial labeling of graph, Bulletin of Pure and Applied Science. 2004; 23:155-163.