Research article · 2018 · Full text
International Journal of Statistics and Applied MathematicsInvariance under cordiality of C4 and Pm related graphs under path: unions
Volume 3(2) · Pages 294–298
Research areasGraph Labeling and Dimension Problemsgraph theory and CDMA systemsAdvanced Graph Theory Research
Abstract
Author-writtenWe discuss one point union of k copies og G i.e. G(k) where G = crown of C4, C4 and Pm for m = 3, 4, 5.We also obtain cordial labeling of C4 and Pm.
Summary
Source-checkedPlain-language reading of the full paper, prepared with AI and checked against the text. Each point links to the authors' own words.
Why it matters
- Cordial labeling is a graph theory concept where vertices are labeled 0 or 1 such that the counts of vertices and edges labeled 0 and 1 differ by at most one. View evidence ↗
- Path unions are created by fusing a graph G to the vertices of a path Pm; different fusion points can result in non-isomorphic structures. View evidence ↗
- Invariance under cordial labeling occurs when all possible path-union structures of a specific graph G are cordial. View evidence ↗
The question
- The study aims to examine the cordiality of one-point unions and path unions for graphs involving C4 and Pm (for m = 3, 4, 5), as well as the cordiality of C4 and Pm themselves. View evidence ↗
What they did
- The method for constructing Pm(G) involves taking a path Pm and fusing a copy of graph G at every vertex of the path at a fixed point. View evidence ↗
- The author uses specific labeling patterns (Type A and Type B) fused at different vertices of the path Pm based on modulo 4 conditions to test cordiality. View evidence ↗
What they found
- All structures of Pm(G) where G = C4+ are cordial, with vertex distributions of (4m, 4m) and edge distributions that differ by at most one depending on whether m is even or odd. View evidence ↗
- For G = C4 and P3, all three non-isomorphic path-union structures are cordial, maintaining a vertex distribution of (4m, 4m). View evidence ↗
- For G = C4 and P4, all four non-isomorphic path-union structures are cordial, with a vertex distribution of (8m, 8m). View evidence ↗
- For G = C4 and P5, all five non-isomorphic path-union structures are cordial, with a vertex distribution of (10m, 10m). View evidence ↗
- The graph consisting of C4 and Pm is cordial for both even (m=2p) and odd (m=2p+1) cases, with balanced vertex and edge distributions. View evidence ↗
What it means
- The author states that the general case of Pk (C4 and Pm) for any given m still needs to be addressed. View evidence ↗
Visual summary
1 visualsIllustrations explain the paper; they do not show study data.
Conceptual Path Union Construction
AI-generated conceptual illustration (mathematical graph structures consisting of vertices and edges). It explains the idea and does not show study data.
View source evidence ↗Figures & tables
From the original paper
Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10
Figure 11Introduction
The graphs we consider are simple, finite, undirected and connected. For terminology and definitions we depend on Graph Theory by Harary [6], A dynamic survey of graph labeling by J.Gallian [8] and Douglas West [9]. I. Cahit introduced the concept of cordial labeling [5]. 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 vf(0) and the number of vertices labeled with 1 i.e.vf(1) differ at most by one. Similarly number of edges labeled with 0 i.e. ef(0) and number of edges labeled with 1 i.e. ef(1) differ at most by one. Then the function f is called as cordial labeling.
I. Cahit has shown that: every tree is cordial; Kn is cordial if and only if n ≤ 3; Km,n is cordial for all m and n; the friendship graph C3 (t) (i.e., the one-point union of t copies of C3) is cordial if and only if t is not congruent to 2 (mod 4); all fans are cordial; the wheel Wn is cordial if and only if n is not congruent to 3 (mod 4). A lot of work has been done in this type of labeling. One may refer dynamic survey by J.
Gallian [8]. Our focus of attention is on path unions on different graphs. For a given graph there are different path unions (up to isomorphism) structures possible. It depends on which point on G is used to fuse with vertex of Pm to obtain path-union.
We have shown that for G = bull on C3, bull on C4, C3+, C4+-e then different path union Pm(G) are cordial [4]. It is called as invariance under cordial labeling. We use the convention that vf(0,1) = (a,b) to indicate the number of vertices labeled with 0 are a in number and that number of vertices labeled with 1 are b in number. Further ef(0,1) = (x,y) we mean the number of edges labeled with 0 are x and number of edges labeled with 1 are y in number.
The graph whose cordial labeling is known is cordial graph. 2. Preliminaries: Path union of G, i.e. Pm(G) is obtained by taking a path pm 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. 3.
Theorems Proved 3.1 Theorem: All structures of Pm(G) are cordial, where G = C+ Proof: Define f: V(G) {0,1}.It gives different labeling units of C+. Maths 2018; 3(2): 294-298 Mukund V Bapat Bapat, Hindale, Tal: Devgad, Sindhudurg, Maharashtra, India Correspondence Mukund V Bapat Bapat, Hindale, Tal: Devgad, Sindhudurg, Maharashtra, India Fig 1: vf(0,1) = (4,4) ef(0,1)=4,4) Fig 2: vf(0,1) = (4,4) ef(0,1)=4,4) To obtain a labeled copy of Pm(G) we start with an unlabeled copy of Pm=(v1, v2,. vm). To obtain structure 1 we fuse type A label at vertex ‘a’ on it at vi on Pm if i≡1,2 (mod 4) and type B with vertex ‘b’ label at vertex vi if i≡ 2,3 (mod 4).The resultant graph is cordial labeled copy of Pm(C4+).The label number distribution is vf(0,1) = (4m,4m), ef(0,1)=(4m+x,4m+x) for all m =2x+1, x= 0, 1, 2,. When m is even number given by m =2x, x= 1, 2,. vf(0,1) = (4m,4m), ef(0,1)=(4m+x,4m+x-1) To obtain structure 2 we fuse type A label at vertex ‘d’ on it at vi on Pm if i≡1,2 (mod 4) and type B with vertex ‘c’ label at vertex vi if i≡ 2,3 (mod 4).The resultant graph is cordial labeled copy of Pm(C4+).The label number distribution is vf(0,1) = (4m,4m), ef(0,1)=(4m+x,4m+x) for all m = 2x+1, x= 0, 1, 2, … When m is even number then m= 2x, x = 1, 2,. vf(0,1) = (4m, 4m), ef(0,1)=(4m+x,4m+x-1).
The two structures are non-isomorphic and cordial. 3.2 Theorem: All structures of Pm(G) are cordial, where G = C4 AND p3.Proof: Define f: V(G) {0,1}. It gives different labeling units of G. Though label numbers on both type A and type B are same the number distribution is different. Fig 3: vf(0,1) = (6,6) ef(0,1)=(6,6) Fig 4: vf(0,1) = (6,6) ef(0,1)=(6,6) Fig 5: P4(C4 and P2), vf(0,1) = (26,26) ef (0,1)=(26,25): structure 3 To obtain a labeled copy of Pm(G) we start with an unlabeled copy of Pm=(v1, v2,. vm).
To obtain structure 1 we fuse type A label at vertex ‘a’ on it at vi on Pm if i≡1,2 (mod 4) and type B with vertex ‘a’ label at vertex vi of Pm if i≡ 2,3 (mod 4).The resultant graph is cordial labeled copy of Pm(C4 and P3).The label number distribution is vf(0,1) = (4m,4m), for all m and on edges ef(0,1)=(4m+x,4m+x) when m = 2x+1, where m is odd number and x =0, 1, 2,. and if m is even number then x=1, 2, … then on edges we have ef(0,1)=(4m+x,4m+x-1). To obtain structure 2we fuse type A label at vertex ‘b’ on it at vi on Pm if i≡1,2 (mod 4) and type B with vertex ‘b’ label at vertex vi of Pm if i≡ 2,3 (mod 4).The resultant graph is cordial labeled copy of Pm(C4 and P3).The label number distribution is vf(0,1) = (4m,4m), for all m and on edges ef(0,1)=(4m+x,4m+x) when m = 2x+1, where m is odd number and x =0, 1, 2,. and if m is even number then x=1, 2, …then on edges we have ef(0,1)=(4m+x,4m+x-1). To obtain structure 3 we fuse type A label at vertex ‘c’ on it at vi on Pm if i≡1,2 (mod 4) and type B with vertex ‘c’ label at vertex vi of Pm if i≡ 2,3 (mod 4). The resultant graph is cordial labeled copy of Pm(C4 and P3).The label number distribution is vf(0,1) = (4m,4m), for all m and on edges ef(0,1)=(4m+x,4m+x) when m = 2x+1, where m is odd number and x =0, 1, 2,. and if m is even number then x=1, 2, …then on edges we have ef(0,1)=(4m+x,4m+x-1).
Thus the graph is cordial under different structures. 3.3 Theorem: All structures of Pm(G) are cordial, where G = C4 and p4. Proof: Define f: V(G) {0,1}.It gives different labeling units of G. Though label numbers on both type A and type B are same the number distribution is different. There are four different non-isomorphic structures of path-union possible on G Fig 6: vf(0,1) = (8,8) ef(0,1)=(8,8) Fig 7: vf(0,1) = (8,8) ef(0,1)=(8,8) Depending on which vertex ‘a’, ‘b’, ‘c’, or ‘d’ we use to fuse on vertex of path Pm.
To obtain structure 1 we fuse type A label at vertex ‘a’ on it at vi on Pm if i≡1,2 (mod 4) and type B with vertex ‘a’ label at vertex vi of Pm if i≡ 2,3 (mod 4).The resultant graph is cordial labeled copy of Pm(C4 and P4).The label number distribution is vf(0,1) = (8m,8m), for all m and on edges ef(0,1)=(8m+x,8m+x) when m = 2x+1, where m is odd number and x =0, 1, 2,. and if m is even number then x=1, 2, … then on edges we have ef(0,1)=(8m+x,8m+x-1). To obtain structure 2we fuse type A label at vertex ‘b’ on it at vi on Pm if i≡1,2 (mod 4) and type B with vertex ‘b’ label at vertex vi of Pm if i≡ 2,3 (mod 4).The resultant graph is cordial labeled copy of Pm(C4 and P4).The label number distribution is vf(0,1) = (8m,8m), for all m and on edges ef(0,1)=(8m+x,8m+x) when m = 2x+1, where m is odd number and x =0, 1, 2,. and if m is even number then x=1, 2, …then on edges we have ef(0,1)=(8m+x,8m+x-1). To obtain structure 3 we fuse type A label at vertex ‘c’ on it at vi on Pm if i≡1,2 (mod 4) and type B with vertex ‘c’ label at vertex vi of Pm if i≡ 2,3 (mod 4).The resultant graph is cordial labeled copy of Pm(C4 and P4).The label number distribution is vf(0,1) = (8m,8m), for all m and on edges ef(0,1)=(8m+x,8m+x) when m = 2x+1, where m is odd number and x =0, 1, 2,. and if m is even number then x=1, 2, …then on edges we have ef(0,1)=(8m+x,8m+x-1). To obtain structure 4 we fuse type A label at vertex ‘d’ on it at vi on Pm if i≡1,2 (mod 4) and type B with vertex ‘d’ label at vertex vi of Pm if i≡ 2,3 (mod 4).The resultant graph is cordial labeled copy of Pm(C4 and P4).The label number distribution is vf(0,1) = (8m,8m), for all m and on edges ef(0,1)=(8m+x,8m+x) when m = 2x+1, where m is odd number and x =0, 1, 2,. and if m is even number then x=1, 2, …then on edges we have ef(0,1)=(8m+x,8m+x-1).
Thus the graph is cordial under different structures. 3.4 Theorem: All structures of Pm(G) are cordial, where G = C4 and p5. Proof: Define f: V(G) {0,1}.It gives different labeling units of G. Though label numbers on both type A and type B are same the number distribution is different. There are five different non-isomorphic structures of path-union possible on G Fig 8: vf(0,1) = (10,10) ef(0,1)=(10,10) Fig 9: vf(0,1) = (10,10) ef(0,1)=(10,10) Depending on which vertex ‘a’, ‘b’, ‘c’, ‘d’ or ‘e’ we use to fuse on vertex of path Pm.
To obtain structure 1 we fuse type A label at vertex ‘a’ on it at vi on Pm if i≡1,2 (mod 4) and type B with vertex ‘a’ label at vertex vi of Pm if i≡ 2,3 (mod 4).The resultant graph is cordial labeled copy of Pm(C4 and P4).The label number distribution is vf(0,1) = (10m,10m), for all m and on edges ef(0,1)=(10m+x,10m+x) when m = 2x+1, where m is odd number and x =0, 1, 2,. and if m is even number then m = 2x, x=1, 2, …then on edges we have ef(0,1)=(10m+x,10m+x-1). To obtain structure 2 we fuse type A label at vertex ‘b’ on it at vi on Pm if i≡1,2 (mod 4) and type B with vertex ‘b’ label at vertex vi of Pm if i≡ 2,3 (mod 4).The resultant graph is cordial labeled copy of Pm(C4 and P4).The label number distribution is vf(0,1) = (10m,10m), for all m and on edges ef(0,1)=(10m+x,10m+x) when m = 2x+1, where m is odd number and x =0, 1, 2,. and if m is even number then m = 2x, x=1, 2, …then on edges we have ef(0,1)=(10m+x,10m+x-1). To obtain structure 3 we fuse type A label at vertex ‘c’ on it at vi on Pm if i≡1,2 (mod 4) and type B with vertex ‘c’ label at vertex vi of Pm if i≡ 2,3 (mod 4).The resultant graph is cordial labeled copy of Pm(C4 and P4).The label number distribution is vf(0,1) = (10m,10m), for all m and on edges ef(0,1)=(10m+x,10m+x) when m = 2x+1, where m is odd number and x =0, 1, 2,. and if m is even number then m = 2x, x=1, 2, …then on edges we have ef(0,1)=(10m+x,10m+x-1). To obtain structure 4 we fuse type A label at vertex ‘d’ on it at vi on Pm if i≡1,2 (mod 4) and type B with vertex ‘d’ label at vertex vi of Pm if i≡ 2,3 (mod 4).The resultant graph is cordial labeled copy of Pm(C4 and P4).The label number distribution is vf(0,1) = (10m,10m), for all m and on edges ef(0,1)=(10m+x,10m+x) when m = 2x+1, where m is odd number and x =0, 1, 2,. and if m is even number then m = 2x, x=1, 2, …then on edges we have ef(0,1)=(10m+x,10m+x-1).
To obtain structure 5 we fuse type A label at vertex ‘e’ on it at vi on Pm if i≡1,2 (mod 4) and type B with vertex ‘e’ label at vertex vi of Pm if i≡ 2,3 (mod 4).The resultant graph is cordial labeled copy of Pm(C4 and P4).The label number distribution is vf(0,1) = (10m,10m), for all m and on edges ef(0,1)=(10m+x,10m+x) when m = 2x+1, where m is odd number and x =0, 1, 2,. and if m is even number then m = 2x, x=1, 2, …then on edges we have ef(0,1)=(10m+x,10m+x-1). Thus the graph is cordial under different structures. We conclude our paper with showing that C4 and Pm is cordial. We do this in two cases in the theorem below by taking m = 2x, x=1, 2,. and m = 2x+1, x= 0, 1, 2, … 3.5 Theorem: C4 and Pm is cordial.
Proof: case m = 2p.The ordinary label is shown in figure below. Define f: V(G){0,1} as follows: f(xi)=0 for i is an odd number. f(xi) = 1 for i is an even number. f(yi) = 0 for i is an odd number. f(y2) = 0; f(yi)=1 for i is an even number ≥ 4. f(ui) = 1 for i =1, 2 and f(ui)=0 for all other i. f(vi) = 0 for i =2x and f(vi)=1 for all other i. The label number distribution is is vf(0,1) = (2m+2,2m+2), for all m and on edges ef(0,1) = (2m+2,2m+2) Case m = 2p+1 Follow the labeling of C4 and Pm for m= 2p as above. The four pendent verticesat (2p+1)th place are labeled as follows: f(x2p+1) = 1; f(y2p+1) = 1; f(u2p+1) = 0; f(v2p+1) = 0.
The label number distribution is vf(0,1) = (2m+3,2m+3), for all m and on edges ef(0,1)=(2m+3,2m+3). Thus the graph is cordial. Fig 10: Ordinary labeling of C4 and P2x C4 and Pm is cordial. Proof: case m = 2p.
Fig 11: labeled copy of C4 and P2x cordial, Proof: case m = 2p.
Conclusions
We have shown invariance under cordial labeling of different structures obtained on path union of Pk(G) where G= C4 and Pm (m = 2,3,4,5). These different non isomorphic structures are due to we use different vertex on C4 and Pm to construct path-union. It remains to do the general case of Pk (C4 and Pm), for given m. We also obtain particular cordial labeling of C4 and Pm.
We predict that for this graph the path union is invariant under cordial labeling.
References
9 in the original paper- And ar M, Boxwala S, Limaye N. New families of cordial graphs, J. Combin. Math. Combin. Comput. 2005; 53:117-154.
- And ar M, Boxwala S, Limaye N. On the cordiality of the t-ply Pt(u,v), Ars Combin., 2005; 77:245-259. [135]
- Bapat Mukund. Ph.D. thesis submitted to university of Mumbai. India, 2004.
- Bapat Mukund V. Some Path Unions Invariance under cordial labeling, accepted IJSAM, 2018.
- Cahit I. Cordial graphs: a weaker version of graceful and harmonious graphs, Ars Combin. 1987; 23:201-207.
- Harary. Graph Theory, Narosa publishing, New Delhi.
- Yilmaz Cahit. E-cordial graphs, Ars combina, 46:251-256.
- Gallian J. Dynamic survey of graph labeling, E.J.C, 2017.
- West D. Introduction to Graph Theory, Pearson Education Asia.