Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
path decomposition; balanced decomposition; complete bipartite graph
path decomposition; balanced decomposition; complete bipartite graph
Summary:
Let $P_k$ denote a path with $k$ edges and $łK_{n,n}$ denote the $ł$-fold complete bipartite graph with both parts of size $n$. In this paper, we obtain the necessary and sufficient conditions for $łK_{n,n}$ to have a balanced $P_k$-decomposition. We also obtain the directed version of this result.
References:
[1] Bermond, J.-C.: Cycles dans les graphes et $G$-configurations. Thesis, University of Paris XI (Orsay), Paris (1975).
[2] Bosák, J.: Decompositions of Graphs. Kluwer, Dordrecht, Netherlands (1990). MR 1071373
[3] Huang, C.: On Handcuffed designs. Dept. of C. and O. Research Report CORR75-10, University of Waterloo.
[4] Hung, S. H. Y., Mendelsohn, N. S.: Handcuffed designs. Discrete Math. 18 (1977), 23-33. DOI 10.1016/0012-365X(77)90003-6 | MR 0447002 | Zbl 0354.05016
[5] Shyu, T.-W.: Path decompositions of $łK_{n,n}$. Ars Comb. 85 (2007), 211-219. MR 2359292
[6] Yu, M.-L.: On path factorizations of complete multipartite graphs. Discrete Math. 122 (1993), 325-333. DOI 10.1016/0012-365X(93)90305-D | MR 1246687 | Zbl 0792.05114
Search
Partner of
