Leaves for packings with block size four

zbMATH Open1468.05225arXiv1905.12151MaRDI QIDQ5000309FDOQ5000309

Tao Feng, Peter Dukes, Yanxun Chang

Publication date: 12 July 2021

Abstract: We consider maximum packings of edge-disjoint $4$-cliques in the complete graph $K_n$. When $nequiv1$ or $4pmod12$, these are simply block designs. In other congruence classes, there are necessarily uncovered edges; we examine the possible `leave' graphs induced by those edges. We give particular emphasis to the case $nequiv0$ or $3pmod12$, when the leave is $2$-regular. Colbourn and Ling settled the case of Hamiltonian leaves in this case. We extend their construction and use several additional direct and recursive constructions to realize a variety of $2$-regular leaves. For various subsets $Ssubseteq3,4,5,dots$, we establish explicit lower bounds on $n$ to guarantee the existence of maximum packings with any possible leave whose cycle lengths belong to $S$.

Full work available at URL: https://arxiv.org/abs/1905.12151

Recommendations

• Packing complete multipartite graphs with 4-cycles
• Some results on 4-cycle packings.
• Maximum packings of \(K_ n\) with copies of \(K_ 4-e\)
• Maximum (minimum) almost resolvable \((4,2)\)-cycle packing (covering) of a complete graph
• Packing \(\lambda\)-fold complete multipartite graphs with 4-cycles

zbMATH Keywords

maximum packingsleaves in a packing

Mathematics Subject Classification ID

Sampling theory, sample surveys (62D05) Combinatorial aspects of block designs (05B05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• A symmetric function generalization of the chromatic polynomial of a graph
• Packing graphs: The packing problem solved
• Title not available (Why is that?)
• Edge-decompositions of graphs with high minimum degree
• Title not available (Why is that?)
• The existence of HGDDs with block size four and its application to double frames
• HGDDs with block size four.
• Group divisible designs with block size four and group type \(g^{u} m^{1}\) for small \(g\)
• Title not available (Why is that?)
• Group divisible designs with block size four and group type \(g^um^{1}\) where \(g\) is a multiple of 8
• Group divisible designs with block-size four
• Group divisible designs with block size four and group type \(g^um^1\)
• On the Maximal Number of Pairwise Orthogonal Latin Squares of a Given Order
• Covering and packing for pairs
• Group divisible designs with block size 4 and type
• Group divisible designs with block size four and type —II
• Title not available (Why is that?)
• Graph divisible designs and packing constructions
• Matching divisible designs with block size four
• Graph-Theoretic Concepts in Computer Science

Cited In (1)

• Kite-group divisible packings and coverings with any minimum leave and minimum excess

This page was built for publication: Leaves for packings with block size four

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