Packing complete multipartite graphs with 4-cycles
A \(k\)-cycle packing of a graph \(G\) is a set \(C\) of edge-disjoint \(k\)-cycles in \(G\). A \(k\)-cycle packing \(C\) of \(G\) is maximum if \(|C|\geq |C'|\) for all other \(k\)-cycle packings \(C'\) of \(G\). The leave of a \(k\)-cycle packing \(C\) of \(G\) is the set of edges of \(G\) that occur in no \(k\)-cycle in \(C\). The authors completely solve the problem of finding a maximum 4-cycle packing of any complete multipartite graph, and they present the minimum leaves explicitly. This is a very interesting extension and generalization of known results by \textit{J. Schönheim} and \textit{A. Bialostocki} [Can. Math. Bull. 18, 703-708 (1975; Zbl 0322.05139)] and \textit{D. G. Hoffman} and \textit{W. D. Wallis} [Bull. Inst. Comb. Appl. 1, 89-92 (1991; Zbl 0828.05051)], where this problem has been solved for complete graphs.
- Packing \(\lambda\)-fold complete multipartite graphs with 4-cycles
- Some results on 4-cycle packings.
- The Doyen-Wilson theorem for maximum packings of \(K_n\) with 4-cycles
- Maximum cyclic 4-cycle packings of the complete multipartite graph
- Almost resolvable maximum packings of complete graphs with 4-cycles
- Maximum packings with odd cycles
- Packings and coverings of the complete directed multigraph with 3- and 4-circuits
- The Doyen-Wilson theorem for maximum packings of \(K_n\) with 4-cycles
- 4-cycle decompositions of \((\lambda +m)K_{v+u} {\setminus } \lambda K_v\)
- Packings and coverings of various complete graphs with the 4-cycle with a pendant edge
- Maximum packing for perfect four-triple configurations
- Maximum cyclic 4-cycle packings of the complete multipartite graph
- Packing 5-cycles into balanced complete \(m\)-partite graphs for odd \(m\)
- Packing \(\lambda\)-fold complete multipartite graphs with 4-cycles
- Equitable block-colorings of \(C_4\)-decompositions of \(K_v-F\)
- Packing and covering the balanced complete bipartite multigraph with cycles and stars
- Maximum hexagon packing of K_v-L where L is a 2-regular subgraph.
- Some results on 4-cycle packings.
- scientific article; zbMATH DE number 6831075 (Why is no real title available?)
- Maximum (minimum) almost resolvable \((4,2)\)-cycle packing (covering) of a complete graph
- Maximal cyclic 4-cycle packings and minimal cyclic 4-cycle coverings of the complete graph
- scientific article; zbMATH DE number 1123811 (Why is no real title available?)
- scientific article; zbMATH DE number 812039 (Why is no real title available?)
- Forest leaves and four-cycles
- Packing 5-cycles into balanced complete n-partite graphs for even n: the 1-factor leave
- Leaves for packings with block size four
- Packings and Coverings of the Complete Bipartite Graph by Octagons
- Packing four copies of a tree into a complete bipartite graph
- scientific article; zbMATH DE number 2192081 (Why is no real title available?)
- Packings and coverings of lambda-fold line graphs of the complete graph with \(k\)-cycles, for \(k=4,6\)
- Group divisible (K₄-e)-packings with any minimum leave
- Almost resolvable maximum packings of complete graphs with 4-cycles
- Almost resolvable maximum packings of complete graphs with 5-cycles
- Enclosings of \(\lambda \)-fold 4-cycle systems
This page was built for publication: Packing complete multipartite graphs with 4-cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2713360)
