betaFeedback

WorksMathematics

Perfect Partitions of Regular Bipartite Graphs

Abstract

Let In,nI_{n,n} be a fixed perfect matching of the complete bipartite graph Kn,nK_{n,n}, and let Ln,1=Kn,n−In,nL_{n,1}=K_{n,n}-I_{n,n}. A perfect set of Ln,1L_{n,1} is a 11-factorization of Ln,1L_{n,1}, that is, a set of n−1n-1 pairwise edge-disjoint perfect matchings whose union is E(Ln,1)E(L_{n,1}); a perfect partition of Ln,1L_{n,1} is a partition of the set of all perfect matchings of Ln,1L_{n,1} into perfect sets. Brualdi, Chiang, and Li (2005) asked whether Ln,1L_{n,1} admits a perfect partition. Identifying both sides of the bipartition with [n]={1,2,…,n}[n]=\{1,2,\ldots ,n\}, the perfect matchings of Ln,1L_{n,1} are exactly the derangements of [n][n], the perfect sets correspond bijectively to the reduced Latin squares of order nn, and the perfect partitions are exactly the perfect matchings of the (n−1)(n-1)-uniform hypergraph whose vertices are the derangements of [n][n] and whose edges are the perfect sets. We first give, for every nn, a constructive lower bound on the maximum number of pairwise disjoint perfect sets of Ln,1L_{n,1}. We then show that L5,1L_{5,1} has exactly 4242 distinct perfect partitions and that L6,1L_{6,1} has at least 8282 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,1L_{7,1}, resolving the n=7n=7 open problem raised by Brualdi et al.

Paper details

vlnc:W_edefd4jp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…