Decomposing Kn,n into Hamiltonian cycles and small stars
A decomposition of a graph $G$ is a set consisting of edge-disjoint subgraphs of $G$ whose union is $G$. A Hamiltonian cycle in $G$, is a cycle containing all of the vertices of $G$. A $m$-star is a star containing $m$ edges and denoted by $S_m$, which is isomorphic to the complete bipartite graph $K_{1,m}$. In this paper, the necessary and sufficient conditions for decomposing the balanced complete bipartite graph $K_{n,n}$ into $p$ copies of Hamiltonian cycles and $q$ copies of $3$-stars ($4$-stars) are given.
Authors
- Hung-Chih Lee
Publication Details
- Journal
- International Journal of Contemporary Mathematical Sciences
- Published
- 2025-01-01
- DOI
- https://doi.org/10.12988/ijcms.2025.92004
- Primary Topic
- Cellular Automata and Applications
- Type
- article
- Field-Weighted Citation Impact
- 0.00