Perfect Partitions of Regular Bipartite Graphs
Abstract
Let In,n be a fixed perfect matching of the complete bipartite graph Kn,n, and let Ln,1=Kn,n−In,n. A perfect set of Ln,1 is a $1$-factorization of Ln,1, that is, a set of n−1 pairwise edge-disjoint perfect matchings whose union is E(Ln,1); a perfect partition of Ln,1 is a partition of the set of all perfect matchings of Ln,1 into perfect sets. Brualdi, Chiang, and Li (2005) asked whether Ln,1 admits a perfect partition. Identifying both sides of the bipartition with [n]={1,2,… ,n}, the perfect matchings of Ln,1 are exactly the derangements of [n], the perfect sets correspond bijectively to the reduced Latin squares of order n, and the perfect partitions are exactly the perfect matchings of the (n−1)-uniform hypergraph whose vertices are the derangements of [n] and whose edges are the perfect sets. We first give, for every n, a constructive lower bound on the maximum number of pairwise disjoint perfect sets of Ln,1. We then show that L5,1 has exactly $42$ distinct perfect partitions and that L6,1 has at least $82$ distinct perfect partitions; these are the first examples demonstrating that perfect partitions need not be unique. Finally, we exhibit two distinct perfect partitions of L7,1, resolving the n=7 open problem raised by Brualdi et al.
Related
- The Cycle Rank Threshold: Perfect Matchings and Bipartite Parter Graphs
- Internal partitions of $5$-regular and $8$-regular graphs
- When are random regular triangle-free graphs bipartite?
- Turán numbers for suspensions of bipartite 2-regular graphs
- On subgroup perfect codes and regular sets in generalized Cayley graphs
BibTeX
@misc{ferreri2026perfect,
title = {{Perfect Partitions of Regular Bipartite Graphs}},
author = {Melanie J. Ferreri and Archana L. Parameswaran and Gexin Yu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07118},
eprint = {2611.07118},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07118},
}
RIS
TY - UNPB
TI - Perfect Partitions of Regular Bipartite Graphs
AU - Melanie J. Ferreri
AU - Archana L. Parameswaran
AU - Gexin Yu
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.07118
UR - https://arxiv.org/abs/2611.07118
AB - Let I_n,n be a fixed perfect matching of the complete bipartite graph K_n,n, and let L_n,1=K_n,n−I_n,n. A perfect set of L_n,1 is a $1$-factorization of L_n,1, that is, a set of n−1 pairwise edge-disjoint perfect matchings whose union is E(L_n,1); a perfect partition of L_n,1 is a partition of the set of all perfect matchings of L_n,1 into perfect sets. Brualdi, Chiang, and Li (2005) asked whether L_n,1 admits a perfect partition. Identifying both sides of the bipartition with [n]={1,2,… ,n}, the perfect matchings of L_n,1 are exactly the derangements of [n], the perfect sets correspond bijectively to the reduced Latin squares of order n, and the perfect partitions are exactly the perfect matchings of the (n−1)-uniform hypergraph whose vertices are the derangements of [n] and whose edges are the perfect sets. We first give, for every n, a constructive lower bound on the maximum number of pairwise disjoint perfect sets of L_n,1. We then show that L_5,1 has exactly $42$ distinct perfect partitions and that L_6,1 has at least $82$ distinct perfect partitions; these are the first examples demonstrating that perfect partitions need not be unique. Finally, we exhibit two distinct perfect partitions of L_7,1, resolving the n=7 open problem raised by Brualdi et al.
ER -