Note on the decomposition of K_m,n ( K^*_m,n) into paths
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.
- Path decompositions of \(\lambda K_{n,n}\)
- Isomorphic path decompositions of \(\lambda K_{n,n,n}(\lambda K^*_{n,n,n})\) for odd \(n\)
- Balanced path decomposition of \(\lambda K_{n,n}\) and \(\lambda K^*_{n,n}\)
- scientific article; zbMATH DE number 5914937
- Path decompositions of Kneser and generalized Kneser graphs
- A note on the path graph P_k(G)
- A fundamental theorem of multigraph decomposition of a \(\lambda K_{m, n}\)
- On path decompositions of 2k-regular graphs
- Decompositions of the Kronecker product of a cycle and a path into long cycles and long paths
- Decompositions of K_n using Stanton-type graphs
- A note on path-perfect graphs
- Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs
- scientific article; zbMATH DE number 3726401 (Why is no real title available?)
- scientific article; zbMATH DE number 3517174 (Why is no real title available?)
- On the Problem of Partitioning {1, 2, � , n} into Subsets having Equal Sums
- Isomorphic path decompositions of \(\lambda K_{n,n,n}(\lambda K^*_{n,n,n})\) for odd \(n\)
- Self-orthogonal Hamilton path decompositions
- Decompositions of graphs into forests with bounded maximum degree
- Hamilton path decompositions of complete multipartite graphs
- Minimal path decomposition of complete bipartite graphs
- Existence of a \(P_{2 k + 1}\)-decomposition in the Kneser graph \(K G_{t, 2}\)
- \(G\)-designs and related designs
- Multidecompositions of the balanced complete bipartite graph into paths and stars
- Decompositions of complete bipartite graphs and complete graphs into paths, stars, and cycles with four edges each
- \((G_m,H_m)\)-multidecomposition of \(K_{m,m}(\lambda)\)
- Path decompositions of Kneser and generalized Kneser graphs
- scientific article; zbMATH DE number 5914937 (Why is no real title available?)
- Balanced path decomposition of \(\lambda K_{n,n}\) and \(\lambda K^*_{n,n}\)
- Path decompositions of \(\lambda K_{n,n}\)
- Decomposition of the complete bipartite graph with a 1-factor removed into paths and stars
- Decompositions of a \(\lambda K_{m,n}\) into graphs of four vertices and five edges
- Decompositions of complete 3-uniform hypergraphs into cycles of constant prime length
- Edge Disjoint Paths of Increasing Order in Complete Bipartite Graphs
- Decomposition of Bipartite Graphs Into Paths
- On the existence of uniformly resolvable decompositions of K_v and K_v-I into paths and kites
- Decomposition of complete bipartite graphs into paths and cycles
- Decompositions of a complete multidigraph into almost arbitrary paths
- scientific article; zbMATH DE number 812067 (Why is no real title available?)
- A bivariate chromatic polynomial for signed graphs
- Decomposition of complete bipartite digraphs and complete digraphs into directed paths and directed cycles of fixed even length
- Decomposition of product graphs into sunlet graphs of order eight
- On ascending subgraph decomposition of graphs
- \(K_n( \lambda )\) is fully \(\{P_5,C_6\}\)-decomposable
- Decompositions into two paths
- Decompositions of complete 3-uniform hypergraphs into cycles of some special even lengths
- Decomposition of cartesian product of complete graphs into sunlet graphs of order eight
- Decomposition of product graphs into paths and cycles of length four
- Encryption and decryption using decomposition of complete graph \(K_{3(6n+1)}\)
- Multi-decomposition of graphs into paths and Y-trees of order five
- Decomposition of the unit graph of the commutative rings
- Decomposition of complete bipartite multigraphs into paths and cycles having \(k\) edges
- Decomposition of complete graphs into paths and stars
This page was built for publication: Note on the decomposition of \(\lambda K_{m,n}\) (\(\lambda K^*_{m,n}\)) into paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1066165)
