Fork-Decomposition of Cartesian Product of Graphs

Authors

  • Samuel Issacraj Manonmaniam Sundaranar University
  • J. Paulraj Joseph

DOI:

https://doi.org/10.12723/mjs.sp1.13

Keywords:

Decomposition, fork, cartesian product, product graph

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.

References

Abolape D. Akwu, Deborah O.A. Ajayi, Sunlet Decomposition of Certain Equipartite Graphs, International Journal of Combinatorics, Vol. 2013, Article ID 907249, 4 pages.

Alspach, B., Gavlas, H., Cycle decomposition of Kn and Kn − I, J .Combin. Theory (B) 81 (2001) 77-99.

Barat, J., Gerbner, D., Edge decomposition of graph into copies of tree with four edges, Electron. J. Combin. 21 (1) (2014).

Bondy, J.A., Murty, U.S.R. , Graph Theory, Springer International Edition, 2008.

Caterina De Simone and Antonio Sassano, Stability number of bull and chair- free graphs, Discrete Applied Mathematics, 41 (1993) 121-129.

Chithra Devi P., Paulraj Joseph J., P4 Decomposition of Product graphs, JP Journal of Mathematical Sciences, Vol. 7, Issues 1 & 2, (2013) 13-39.

Dor, D., Tarsi, M., Graph-decomposition is NP-complete: a complete proof of Holyers conjecture, SIAM J Comput 26 (1997), 11661187.

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.

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.

Richard Hammack, Wilfied Imrich, Samndi Klavzar, Handbook of Product Graphs, Second Edition, Taylor and Francis Group, 2011.12

Sunil Kumar, C., On P4-decomposition of Graphs, Taiwanese Journal of Mathematics, Vol. 7, No. 4, pp. 657-664, December 2003.

Yang Zhao, Baoyindureng Wu, Star decomposition of graphs, Discrete Mathematics, Algorithms and Applications, Vol.7, No.2, (2015) 1550016 (9 pages).

Additional Files

Published

2023-07-19

Issue

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

Section

Research Articles

License

Copyright (c) 2023 Samuel Issacraj, J. Paulraj Joseph

Creative Commons License

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