×

zbMATH — the first resource for mathematics

Note on the decomposition of \(\lambda K_{m,n}\) (\(\lambda K^*_{m,n}\)) into paths. (English) Zbl 0578.05054
Let \(G\) and \(H\) be (di)graphs. By an \(H\)-decomposition of \(G\) we mean a partition of the edge set of \(G\) into disjoint subsets each spanning in \(G\) a subgraph isomorphic to \(H\). In the paper \(H\)-decompositions of a complete bipartite symmetric multidigraph \(\lambda K^*_{m,n}\) and a complete bipartite multigraph \(\lambda K_{m,n}\) are studied in the case when \(H\) is a path of length \(k\). The following three results are proved:
(1) Let \(m\geq n\). \(\lambda K^*_{m,n}\) has a decomposition into paths of length \(k\) if and only if \(k\) divides \(2\lambda mn\), \(m\geq \lceil (k+1)/2\rceil\) and \(n\geq \lceil k/2\rceil\).
(2) Let \(\lambda\) be an even integer and let \(m\geq n\). \(\lambda K_{m,n}\) has a decomposition into paths of length \(k\) if and only if \(k\) divides \(\lambda mn\), \(m\geq \lceil (k+1)/2\rceil\) and \(n\geq \lceil k/2\rceil\).
(3) Let \(m\) and \(n\) be even, \(m\geq n\). \(\lambda K_{m,n}\) has a decomposition into paths of length \(k\) if and only if \(k\) divides \(\lambda mn\), \(m\geq \lceil (k+1)/2\rceil\) and \(n\geq \lceil k/2\rceil\). Some results in the case when at least one of \(m\) and \(n\) is odd are also presented.
Reviewer: M. Truszczyński

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
05C20 Directed graphs (digraphs), tournaments
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bermond, J.C.; Sotteau, D., Graph decompositions and G-designs, (), 53-72 · Zbl 0331.05021
[2] Chung, F.R.K.; Graham, R.L., Recent results in graph decompositions, (), 103-124 · Zbl 0464.05046
[3] Fink, J.F.; Straight, H.J., A note on path-perfect graphs, Discrete math., 33, 95-98, (1981) · Zbl 0447.05037
[4] Sotteau, D., Decompositions of K_m,n (km,n*) into cycles (circuits) of length 2k, J. combin. theory ser. B, 30, 146-155, (1980)
[5] Straight, H.J.; Schillo, P., On the problem of partitioning …, n into subsets having equal sums, (), 229-231 · Zbl 0404.05039
[6] Tarsi, M., Decomposition of a complete multigraph into simple paths, J. combin. theory ser. A, 34, (1983) · Zbl 0511.05024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.