Shayou Permutation Labelling for Some Families of Graphs

Abstract

This paper introduces a new graph labeling called Shayou Permutation Labeling. A formula is proposed to define the edge labels from the vertex labels. A function ? is said to be a Shayou Permutation Labeling of a graph G if there exists a mapping from the vertex set of G to the set {1 , 2 ,…, p } such that each edge uv is assigned the label ?(uv)=(?(u) + ?(v))!/(( ?(u) + ?(v) -1)!) ,and the resulting edge labels are distinct numbers. The proposed labeling is based on the additive relationship between the labels of the end vertices of each edge. This labeling provides a systematic approach for assigning edge labels using factorial expressions derived from vertex labels. The concept contributes to the study of graph labeling by introducing a new labeling technique that can be extended to other classes of graphs. The existence of this labeling is studied for some classes of graphs, namely, the path graph and star graph. The results demonstrate that these graph families admit Shayou Permutation Labeling under the proposal labeling rule. Graph labelling can be classified into different types which is cited as [9,13,14,15,16,17]. Graph labeling concept can be extended to automata theory which is cited as [10, 11, 12]. Graph labeling is also extended to domination [1, 6, 7, 8].

Introduction

The paper introduces a new graph-labeling concept called Shayou Permutation Labeling, extending existing work in graph theory and graph labeling.

Graph theory studies mathematical structures consisting of vertices and edges and has applications in computer science, communication networks, chemistry, biology, engineering, operations research, and social sciences. In graph labeling, integers are assigned to vertices, edges, or both according to specific mathematical rules. Existing approaches include graceful, additive, multiplicative, strongly multiplicative, square, and cube labeling.

Shayou Permutation Labeling

For a finite, simple, undirected graph G=(V,E) with p vertices, the proposed labeling assigns the numbers

{1,2,…,p}

to the vertices through a bijection/permutation π.

For an edge uv, the paper defines its induced label as

π(uv)=(π(u)+π(v)−1)!(π(u)+π(v))!?.

Since

(n−1)!n!?=n,

this formula simplifies mathematically to

π(uv)=π(u)+π(v)?.

Thus, the proposed edge-labeling rule is essentially the sum of the labels of the two end vertices. A graph that admits such a labeling while satisfying the required distinctness conditions is called a Shayou Permutation Graph.

Main Results

The paper proves that certain important graph families satisfy the proposed labeling.

1. Path Graph Pn?

For the path

Pn?=v1?v2??vn?,

the vertices are assigned their natural labels:

π(vi?)=i.

For an edge ei?=vi?vi+1?,

π(ei?)=i+(i+1)=2i+1.

Therefore, the edge labels are

3,5,7,…,2n−1,

which are all distinct. Hence,

Pn? is a Shayou Permutation Graph for n≥2.?

2. Star Graph K1,n?

For the star graph, the centre is assigned label 1, while the pendant vertices receive labels

2,3,…,n+1.

Therefore, the edge joining the centre to the i-th pendant vertex receives

π(ei?)=1+(i+1)=i+2.

The resulting edge labels are distinct, so

K1,n? is a Shayou Permutation Graph for n≥2.?

Conclusion

This paper introduces a new graph labeling scheme called Shayou Permutation Labeling. The proposed labeling assigns distinct edge labels using a factorial-based formula and a bijective vertex labeling. The existence of this labeling has been established for the path graph Pn and the star graph K1,n . This work contributes a new direction to graph labeling theory and provides a foundation for extending the concept to other classes of graphs in future research.

References

[1] Amalorpava Jerline, J., Litta, E., Dhanalakshmi, K., Benedict Michael Raj, L., “F – Index of Generalized Mycielskian Graphs”, International Journal of Recent Scientific Research, 10(6),33076 – 33081. [2] Bodendick, R. and Walther, G., On number theoretical methods in graph labelingsRes.Exp.Maths (2,/1995) 3-25. [3] Bloom, D.F. Hsu, On graceful directed graphs, SIAMJ, Alg. Discrete Math.,6(1985),519-536. [4] Gallian, M.A., “A Dynamic survey of graph labelings” Electronic journal, 2000 (Volume-23). [5] Harary, F., Graph Theory, New Delhi: Narosa Publishing House, 2001. [6] Litta, E., Narmadha, S, “Proper Colourings in r – Regular Inverse sum Indeg Index Graph”, Research and Applications Towards Mathematics and Computer Science, Volume 9, February 2024, Pg. No. 66-76, B P International, Print ISBN: 978-81-970187-8-7 eBook ISBN: 978-81-970187-9-4. [7] Litta, E., Narmadha, S.,“Augmented Zagreb Index of corona Product of Some Special Graphs”, International Journal for Research in Applied Science & Engineering Technology, Volume 12, March 2024 Pg. No. 580 – 585. [8] Litta, E., Jayavarshini, N.,, “Proper Colourings in r – Regular Randic Index Graph”, , International Journal for Research in Applied Science & Engineering Technology, Volume 12, February 2024 Pg. No. 1603– 1607. [9] [9] Prakash, V., Gopi, R., Shalini, P., Anti Skolem Mean Labeling of Quadrilateral Snake Related Graphs, Tuijin Jishu/Journal of Propulsion Technology, Vol. 44, No. 5(2023), 495 – 500. [10] Saridha. S, Haridha Banu. S“An innovative Ideas on Plus Weighted Linear Grammar”,Volume 15, Issue 2, Aryabhatta journal of mathematics & Informatics (AJMI), June-Dcc 2023, Page No: 173-178, ISSN: 2394-9309. [11] Saridha. S, Vidhya. R, “Application of Fuzzy Hypergraph in Medical Diagnosis”, Aryabhatta Journal of Mathematics & Informatics,Volume 12, Issue I, Page no: 872-875, ISSN 2321-9653, Jan 2024, Impact factor: 7.538. [12] Saridha, S., Shalini, P., “An overview of plus weighted DiGraph and its Applications”, Aryabhatta Journal of Mathematics and Informatics, Volume 18, Issue 1, Jan -June 2026. Pg. No. 27-32. [13] Shalini, P. Paul Dhayabaran, D, Minimization of Multiplicative Graphs, International Journal of Current Research, Vol. 7, Issue, 08, pp. 19511 – 19518, August, 2015. [14] Shalini, P., Gowri, R., Paul Dhayabaran, D., “An Absolute Differences of Cubic and Square Difference Labeling For Some Families Of Graphs”, The International journal of analytical and experimental modal analysis, Volume XI, Issue 10, October 2019, Page no: 538-544. [15] Shalini, P., Priyadarshini, K., SP Mean Difference Labeling for Some Families of Graphs”,Research and Applications Towards Mathematics and Computer Science, Volume 9, February 2024, Pg. No. 1-12, B P International, Print ISBN: 978-81-970187-8-7, eBook ISBN: 978-81-970187-9-4. [16] Shalini, P., “Skolem Odd Vertex Graceful Signed Graphs for Path”, Aryabhatta Journal of Mathematics and Informatics, Volume 15, Issue 1, Jan -June 2023. Pg. No. 121-126. [17] Shalini, P., Saridha, S.,”A Study on Vertex Sum Cube Labeling for Path and Star Graphs”, Aryabhatta Journal of Mathematics and Informatics, Volume 18, Issue 1, Jan -June 2026. Pg. No. 63-68.

Copyright

Copyright © 2026 P. Shalini, K. Youvamathi . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.