Decomposition of the complete bipartite graph with a 1-factor removed into paths and stars

  • Jenq-Jong Lin Ling Tung University
  • Hung-Chih Lee Ling Tung University
Keywords: Decomposition, complete bipartite graph, path, star, crown

Abstract

Let P_k denote a path on k vertices, and let S_k denote a star with k edges. For graphs F, G, and H, a decomposition of F is a set of edge-disjoint subgraphs of F whose union is F. A (G,H)-decomposition of F is a decomposition of F into copies of G and H using at least one of each. In this paper, necessary and sufficient conditions for the existence of the (P_{k+1},S_k)-decomposition of the complete bipartite graph with a 1-factor removed are given.

References

1. A. Abueida and M. Daven, Multidesigns for graph-pairs of order 4 and 5, Graphs Combin. 19 (2003), 433-447.

2. A. Abueida and M. Daven, Multidecompositons of the complete graph, Ars Combin. 72 (2004), 17-22.

3. A. Abueida and M. Daven, Multidecompositions of several graph products, Graphs Combin. 29 (2013), 315-326.

4. A. Abueida and C. Lian, On the decompositions of complete graphs into cycles and stars on the same number of edges, Discuss. Math. Graph Theory 34 (2014), 113-125.

5. A. Abueida and T. O'Neil, Multidecomposition of -km into small cycles and claws, Bull. Inst. Combin. Appl. 49 (2007), 32-40.

6. F. Beggas, M. Haddad, and H. Kheddouci, Decomposition of complete multigraphs into stars and cycles, Discuss. Math. Graph Theory 35 (2015), 629-639.

7. A. Bouchet and J. L. Fouquet, Trois types de décomposition d'un graphe en chaînes, Ann Discrete Math. 17 (1983), 131-141.

8. D. E. Bryant, S. El-Zanati, C. V. Eyden, and D. G. Hoffman, Star decompositions of cubes, Graphs Combin. 17 (2001), 55-59.

9. K. Heinrich, Path-decompositions, Matematiche (Catania) 47 (1992), 241-258.

10. K. Heinrich, J. Liu, and M. Yu, P4-decomposition of regular graphs, J. Graph Theory

11. M. S. Jacobson, M. Truszczy«ski, and Z. Tuza, Decompositions of regular bipartite graphs, Discrete Math. 89 (1991), 17-27.

12. S. Jeevadoss and A. Muthusamy, Decomposition of complete bipartite graphs into paths and cycles, Discrete Math. 331 (2014), 98-108.

13. S. Jeevadoss and A. Muthusamy, Decomposition of complete bipartite multigraphs into paths and cycles having k edges, Discuss. Math. Graph Theory 35 (2015), 715-731.

14. A. Kotzig, From the theory of finite regular graphs of degree three and four, - Časopis Pěst Mat 82 (1957), 76-92.

15. C. S. Kumar, On p4-decomposition of graphs, Taiwanese J. Math. 7 (2003), 657-664.

16. H.-C. Lee, Multidecompositions of complete bipartite graphs into cycles and stars, Ars Combin. 108 (2013), 355-364.

17. H.-C. Lee, Decomposition of the complete bipartite multigraph into cycles and stars, Discrete Math. 338 (2015), 1362-1369.

18. H.-C. Lee, M.-J. Lee, and C. Lin, Isomorphic path decompositions of $\lambdak_{n,n,n} (\lambda k_{n,n,n}^{*})$ for odd n, Taiwanese J. Math 13 (2009), 393-402.

19. H.-C. Lee and J.-J. Lin, Decomposition of the complete bipartite graph with a 1-factor removed into cycles and stars, Discrete Math. 313 (2013), 2354-2358.

20. C. Lin, J.-J. Lin, and T.-W. Shyu, Isomorphic star decomposition of multicrowns and the power of cycles, Ars Combin. 53 (1999), 249-256.

21. J.-J. Lin, Decompositions of multicrowns into cycles and stars, Taiwanese J. Math. 19 (2015), 1261-1270.

22. C. A. Parker, Complete bipartite graph path decompositions, Ph.D. thesis, Auburn University, Auburn, Alabama, 1998.

23. H. M. Priyadharsini and A. Muthusamy, (Gm;Hm)-multifactorization of -km, J. Combin. Math. Combin. Comput. 69 (2009), 145-150.

24. H. M. Priyadharsini and A. Muthusamy, Bull. inst. combin. appl., $(G_m;H_m)$-multidecomposition of $K_{m;m}(\lambda)$ 66 (2012), 42-48.

25. T.-W. Shyu, Path decompositions of -kn;n, Ars Combin. 85 (2007), 211-219.

26. T.-W. Shyu, Decomposition of complete graphs into paths and stars, Discrete Math. 310 (2010), 2164-2169.

27. T.-W. Shyu, Decompositions of complete graphs into paths and cycles, Ars Combin. 97 (2010), 257-270.

28. T.-W. Shyu, Decomposition of complete graphs into paths of length three and triangles, Ars Combin. 107 (2012), 209-224.

29. T.-W. Shyu, Decomposition of complete bipartite graphs into paths and stars with same number of edges, Discrete Math. 313 (2013), 865-871.

30. T.-W. Shyu, Decomposition of complete graphs into cycles and stars, Graphs Combin. 29 (2013), 301-313.

31. T.-W. Shyu and C. Lin, Isomorphic path decomposition of crowns, Ars Combin. 67 (2003), 97-103.

32. M. Tarsi, Decomposition of complete multigraphs into stars, Discrete Math. 26 (1979), 273-278.

33. M. Tarsi, Decomposition of complete multigraph into simple paths: nonbalanced handcuffed designs, J. Combin. Theory Ser. A 34 (1983), 60-70.

34. S. Tazawa, Decomposition of a complete multipartite graph into isomorphic claws, SIAM J. Algebraic Discrete Methods 6 (1985), 413-417.

35. M. Truszczy«ski, Note on the decomposition of $\lambda k_{m;n}(\lambda k_{m;n}^{*})$ into paths, Discrete Math. 55 (1985), 89-96.

36. K. Ushio, S. Tazawa, and S. Yamamoto, On claw-decomposition of complete multipartite graphs, Hiroshima Math. J. 8 (1978), 207-210.

37. S. Yamamoto, H. Ikeda, S. Shigeede, K. Ushio, , and N. Hamada, On claw decomposition of complete graphs and complete bigraphs, Hiroshima Math. J. 5 (1975), 33-42.
Published
2018-12-31
Section
Articles