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₁,ₙ⟩

Abstract

This study explores the On decomposition of the complement of a graph derived from two star graphs, denoted as <K₁,ₘ : K₁,ₙ>. 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.

Country : Sultanate of Oman

1 Dr. Mallikarjun Ghaleppa2 Dr. Amit kumar Yadav3 Amabelle Oliva Enanoria4 Farheen Fatima5 Dr. Ramesh Palanisamy

  1. Mathematics and Computing Unit, Preparatory Studies center, University of Technology and Applied Sciences, Ibra, Oman
  2. Mathematics and Computing Unit, Preparatory Studies center, University of Technology and Applied Sciences, Ibra, Oman
  3. Mathematics and Computing Unit, Preparatory Studies center, University of Technology and Applied Sciences, Ibra, Oman
  4. Mathematics and Computing Unit, Preparatory Studies center, University of Technology and Applied Sciences, Ibra, Oman
  5. College of Computing and Information Sciences, University of Technology and Applied Sciences – Ibra, Sultanate of Oman

IRJIET, Volume 9, Issue 5, May 2025 pp. 423-433

doi.org/10.47001/IRJIET/2025.905047

Full Paper
Download

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-2017 IRJIET. All Right Reserved.

Developed by Byzero Technologies