Fork-decomposition of strong product of graphs

Samuel Issacraj, Paulraj Joseph


Decomposition of arbitrary graphs into subgraphs of small size is assuming importance in the literature. There are several studies on the isomorphic decomposition of graphs into paths, cycles, trees, stars, sunlet etc. 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 for the fork-decomposition of Strong product of graphs.


Decomposition, Fork, Product graph, Strong Product

Full Text:



A. Akwu and D. Ajayi. Sunlet decomposition of certain equipartite graphs. International Journal of Combinatorics, page 4, 2013.

B. Alspach and H. Gavlas. Cycle decomposition of K_n and K_n-i,. J .Combin. Theory (B), 81:77–99, 2001.

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

J. Barat and C. Thomassen. Claw-decompositions and tutte-orientations. J. Graph Theory, 52:135–146, 2006.

J. Bondy and U. Murty. Graph Theory, Springer International Edition. Springer, 2008.

P. C. Devi and J. P. Joseph. P_4 decomposition of product graphs. JP Journal of Mathematical Sciences, 7 (1 & 2):13–39, 2013.

D. Dor and M. Tarsi. Graph-decomposition is np-complete: a complete proof of holyer’s conjecture. SIAM J Comput, 26:1166–1187, 1997.

R. Hammack, W. Imrich, and S. Klavzar. Handbook of Product Graphs, Second Edition. Taylor and Francis Group, 2011.

A. S. Issacraj and J. P. Joseph. Fork-decomposition of cartesian product of graphs. Mapana Journal of Sciences, 22:189–204, 2023.

A. S. Issacraj and J. P. Joseph. Fork-decomposition of direct product of graphs. Advances and Applications in Discrete Mathematics, 34:39–55, 2022.

J. P. Joseph and A. S. Issacraj. Fork-decomposition of graphs. Pre-Conference Proceedings of the International Conference on Discrete Mathematics, 426–431, 2022.

C. S. Kumar. On P_4-decomposition of graphs. Taiwanese Journal of Mathematics, 7 (4):657–664, 2003.

M. qing Zhai and C. hong Lu. Path decomposition of graph with given path length. Acta Mathematicae Aplicatae Sinica, English Series, 22 (4):633–638, 2006.

C. D. Simone and A. Sassano. Stability number of bull and chair-free graphs. Discrete Applied Mathematics, 41:121–129, 1993.

Y. Zhao and B. Wu. Star decomposition of graphs. Discrete Mathematics, Algorithms and Applications, 7 (2):1550016 (9 pages), 2015.



Copyright (c) 2023 Samuel Issacraj, Paulraj Joseph

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

Ratio Mathematica - Journal of Mathematics, Statistics, and Applications. ISSN 1592-7415; e-ISSN 2282-8214.