International Research Journal of Innovations in Engineering and Technology - IRJIET International Open Access, Monthly, Peer Reviewed, Reputed Journal ISSN (online): 2581-3048

Impact Factor (2025): 6.9

DOI Prefix: 10.47001/IRJIET

Structural On-Decomposition of the Complement of Star-Based Graph Constructs ⟨K₁,ₘ: K₁,ₙ⟩

Dr. Mallikarjun GhaleppaMathematics and Computing Unit, Preparatory Studies center, University of Technology and Applied Sciences, Ibra, OmanDr. Amit kumar YadavMathematics and Computing Unit, Preparatory Studies center, University of Technology and Applied Sciences, Ibra, OmanAmabelle Oliva EnanoriaMathematics and Computing Unit, Preparatory Studies center, University of Technology and Applied Sciences, Ibra, OmanFarheen FatimaMathematics and Computing Unit, Preparatory Studies center, University of Technology and Applied Sciences, Ibra, OmanDr. Ramesh PalanisamyCollege of Computing and Information Sciences, University of Technology and Applied Sciences – Ibra, Sultanate of Oman

Vol 9 No 5 (2025): Volume 9, Issue 5, May 2025 | Pages: 423-433

International Research Journal of Innovations in Engineering and Technology

OPEN ACCESS | Research Article | Published Date: 30-05-2025

doi Logo doi.org/10.47001/IRJIET/2025.905047

pdf iconFull Text PDF
Abstract

This study explores the On decomposition of the complement of a graph derived from two star graphs, denoted as . In this context, K₁,ₘ and K₁,ₙ are star graphs with one central vertex and m and n peripheral vertices, respectively. The ":" operator symbolises a specific binary graph operation, such as a graph join, that integrates these two star graphs into a single structure. This research focuses on the complement of the resulting graph, wherein edges exist between previously non-adjacent vertex pairs. The primary objective is to examine how this complemented graph can be decomposed into subgraphs that meet the on decomposition criteria. The On decomposition refers to a partitioning method in which the graph is divided into components satisfying specific neighbourhood or structural constraints, often relevant in graph optimisation and algorithm design. Results of this study provide new insights into the structure and decomposition of complex graphs, with potential implications for theoretical computer science, network analysis, and data structures.

Keywords

Graph theory, star graphs, graph complement, on decomposition, graph operations, graph decomposition


Citation of this Article

Dr. Mallikarjun Ghaleppa, Dr. Amit kumar Yadav, Amabelle Oliva Enanoria, Farheen Fatima, & Dr. Ramesh Palanisamy. (2025). Structural On-Decomposition of the Complement of Star-Based Graph Constructs ?K?,?: K?,??. International Research Journal of Innovations in Engineering and Technology - IRJIET, 9(5), 423-433. Article DOI https://doi.org/10.47001/IRJIET/2025.905047

Licence Copyright (c) 2026 International Research Journal of Innovations in Engineering and Technology creative common licence This work is licensed under Creative common Attribution Non Commercial 4.0 Internation Licence
References
  1. Alon, N. (1983). A note on the decomposition of graphs into matchings. Acta Mathematica Hungarica, 42(3–4), 221–223.
  2. Bondy, J. A., & Murty, U. S. R. (2008). Graph theory (Vol. 244). Springer.
  3. Chatrand, G., & Zhang, P. (2006). Introduction to graph theory. Tata McGraw-Hill.
  4. Chung, F. R. K. (1981). On the decomposition of graphs. SIAM Journal on Algebraic and Discrete Methods, 2(1), 1–12.
  5. Diestel, R. (2017). Graph theory (5th ed.). Springer.
  6. Harary, F. (1969). Graph theory. Addison-Wesley.
  7. Harary, F., Robinson, R. W., & Wormald, N. C. (1978). Isomorphic factorization I: Complete graphs. Transactions of the American Mathematical Society, 242, 243–260.
  8. Hartsfield, N., & Ringel, G. (1994). Pearls in graph theory. Academic Press.
  9. Kumar, C. S. (2002). Decomposition problems in graph theory (Doctoral dissertation).
  10. Rayamarakkarveettill, S. (2013). On the decomposition of the complement of a bistar. Graph Theory Notes of New York, LXIV, 49–57.
  11. Shayida, R. (2017). On decompositions of bistars and their complements. Journal of Graph Theory, 85(2), 123–135.
  12. West, D. B. (2001). Introduction to graph theory (2nd ed.). Prentice Hall.
  13. Wilson, R. M. (1975). Decompositions of complete graphs into subgraphs isomorphic to a given graph. Congressus Numerantium, 15, 647–659.
  14. Wilson, R. M. (1975). Decomposition of complete graphs into subgraphs isomorphic to a given graph. In Proceedings of the 5th British Combinatorial Conference (pp. 647–659).
  15. Yeo, A. (1998). A note on path decompositions of graphs. Discrete Mathematics, 185(1–3), 285–287. 

Copyright @ 2026 IRJIET. All Right Reserved.

Licensed underCreative Commons Attribution 4.0 International License.