Existence of resolvable path designs

DOI10.1016/S0195-6698(13)80120-5MaRDI QIDQ923105zbMATH OpenOpenAlexFDO

Authors Katherine Heinrich, Min-Li Yu, Jean-Claude Bermond

Publication date 1990

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0195-6698(13)80120-5

zbMATH Keywords

\(P_ k\)-factorcomplete multigraphfactorizationpartitionresolvablespanning subgraph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

Let \(\lambda K_ n\) denote the complete multigraph on n vertices in which every edge has multiplicity \(\lambda\), and let \(P_ k\) denote the path with k vertices. A \(P_ k\)-factor of \(\lambda K_ n\) is a spanning subgraph each component of which is isomorphic to \(P_ k\). The authors prove that the edge set of \(\lambda K_ n\) has a partition into \(P_ k\)-factors, \(k\geq 2\), if and only if \(n\equiv 0(mod k)\) and \(\lambda\) k(n-1)\(\equiv 0(mod 2k-2)\).

Recommendations

• On resolvable mixed path designs
• On path factorizations of complete multipartite graphs
• Resolvable tree designs
• scientific article; zbMATH DE number 5823698
• Almost resolvable P_k‐decompositions of complete graphs

Cites work

• Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs
• Graph decompositions, handcuffed prisoners and balanced p-designs
• Handcuffed designs
• scientific article; zbMATH DE number 3970750 (Why is no real title available?)
• Resolvable path designs
• The Oberwolfach problem and factors of uniform odd length cycles

Cited in

(22)

• Nesting directed cycle systems of even length
• Resolvable tree designs
• Path factorizations of complete multipartite graphs
• On path factorizations of complete multipartite graphs
• \(G\)-designs and related designs
• On the chromatic index of path decompositions
• Uniformly resolvable decompositions of \(K_v\) into paths on two, three and four vertices
• scientific article; zbMATH DE number 5127213 (Why is no real title available?)
• A survey on the existence ofG-Designs
• Uniformly resolvable decompositions of K_v into P₃ and K₃ graphs
• Almost resolvable P_k‐decompositions of complete graphs
• On tree factorizations of K_n
• scientific article; zbMATH DE number 1933062 (Why is no real title available?)
• A note on uniformly resolvable \(\{P_4, C_6\}\)-designs
• Complex uniformly resolvable decompositions of K_v
• Uniformly resolvable decompositions of K_n into 1-factors and P_k-factors
• Partial S(k-1,k,v)'s inducing P_k-decompositions of K_v
• Block colourings of star systems
• Scheduling to reduce close contacts: resolvable grid graph decomposition and packing
• Uniformly resolvable \({P_4, C_k}\)-decomposition of \(K_n\) -- a complete solution
• The existence of restricted resolvable designs. I: (1,2)-factorizations of \(K_{2n}\)
• On resolvable mixed path designs

This page was built for publication: Existence of resolvable path designs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q923105)