Vol. 22 No. Special Issue (2023): Mapana Journal of Sciences- RECENT DEVELOPMENTS IN PURE AND APPLIED MATHEMATICS
Research Articles

Fork-Decomposition of Cartesian Product of Graphs

PDF
  • Samuel Issacraj,
  • J. Paulraj Joseph
Samuel Issacraj
Manonmaniam Sundaranar University
DOI: https://doi.org/10.12723/mjs.sp1.13

Published 2023-07-19

Keywords

  • Decomposition,
  • fork,
  • cartesian product,
  • product graph

Copyright (c) 2023

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Abstract

Let G = (V, E) be a graph. Fork is a tree obtained by subdividing any edge of a star of size three exactly once. In this paper, we investigate the necessary and sufficient condition for the fork-decomposition of Cartesian product of graphs.

PDF

References

  1. Abolape D. Akwu, Deborah O.A. Ajayi, Sunlet Decomposition of Certain Equipartite Graphs, International Journal of Combinatorics, Vol. 2013, Article ID 907249, 4 pages.
  2. Alspach, B., Gavlas, H., Cycle decomposition of Kn and Kn − I, J .Combin. Theory (B) 81 (2001) 77-99.
  3. Barat, J., Gerbner, D., Edge decomposition of graph into copies of tree with four edges, Electron. J. Combin. 21 (1) (2014).
  4. Bondy, J.A., Murty, U.S.R. , Graph Theory, Springer International Edition, 2008.
  5. Caterina De Simone and Antonio Sassano, Stability number of bull and chair- free graphs, Discrete Applied Mathematics, 41 (1993) 121-129.
  6. Chithra Devi P., Paulraj Joseph J., P4 Decomposition of Product graphs, JP Journal of Mathematical Sciences, Vol. 7, Issues 1 & 2, (2013) 13-39.
  7. Dor, D., Tarsi, M., Graph-decomposition is NP-complete: a complete proof of Holyers conjecture, SIAM J Comput 26 (1997), 11661187.
  8. Ming-qing Zhai, Chang-hong Lu, Path Decomposition of Graph with given path length, Acta Mathematicae Aplicatae Sinica, English Series, Vol. 22, No. 4 (2006) 633-638.
  9. Paulraj Joseph, J., Samuel Issacraj, A., Fork-decomposition of graphs, Pre- Conference Proceedings of the International Conference on Discrete Mathematics, ISBN:978-93-91077-53-2, (2022) 426-431.
  10. Richard Hammack, Wilfied Imrich, Samndi Klavzar, Handbook of Product Graphs, Second Edition, Taylor and Francis Group, 2011.12
  11. Sunil Kumar, C., On P4-decomposition of Graphs, Taiwanese Journal of Mathematics, Vol. 7, No. 4, pp. 657-664, December 2003.
  12. Yang Zhao, Baoyindureng Wu, Star decomposition of graphs, Discrete Mathematics, Algorithms and Applications, Vol.7, No.2, (2015) 1550016 (9 pages).