Note on the decomposition of \(\lambda K_{m,n}\) (\(\lambda K^*_{m,n}\)) into paths
type: Item
instance of: scholarly article
title: Note on the decomposition of \(\lambda K_{m,n}\) (\(\lambda K^*_{m,n}\)) into paths
zbMATH Open document ID: 0578.05054
DOI: 10.1016/S0012-365X(85)80023-6
published in: Discrete Mathematics
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 3924835
zbMATH Keywords: edge decomposition
zbMATH Keywords: Euler cycle
zbMATH Keywords: H-decompositions
zbMATH Keywords: complete bipartite multigraph
zbMATH Keywords: path
author: Mirosław Truszczyński
reviewed by: Mirosław Truszczyński
MaRDI profile type: Publication
cites work: Q4097307
cites work: Q3915022
cites work: A note on path-perfect graphs
cites work: On the Problem of Partitioning {1, 2, � , n} into Subsets having Equal Sums
cites work: Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs
full work available at URL: s0012-365x(85)80023-6
OpenAlex ID: W2094280702
Recommended article: Q3070206
Recommended article: Isomorphic path decompositions of \(\lambda K_{n,n,n}(\lambda K^*_{n,n,n})\) for odd \(n\)
Recommended article: Balanced path decomposition of λ K n,n and λ K n,n *
Recommended article: Q3011784
Recommended article: Path Decompositions of Kneser and Generalized Kneser Graphs
Recommended article: A note on the path graph \(P_k(G)\)
Recommended article: Q5740787
Recommended article: On path decompositions of \(2k\)-regular graphs
Recommended article: Decompositions of the Kronecker product of a cycle and a path into long cycles and long paths
Recommended article: Decompositions of \(\lambda K_n\) using Stanton-type graphs
description: scientific article; zbMATH DE number 3924835