Fork-Decomposition of Cartesian Product of Graphs
Keywords:Decomposition, fork, cartesian product, product graph
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.
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).
Copyright (c) 2023 Samuel Issacraj, J. Paulraj Joseph
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.