TY - JOUR
T1 - The seating couples problem in the even case
AU - Meszka, Mariusz
AU - Pasotti, Anita
AU - Pellegrini, Marco Antonio
PY - 2024
Y1 - 2024
N2 - In this paper we consider the seating couples problem with an even number of seats, which, using graph theory terminology, can be stated as follows. Given a positive even integer v=2n and a list L containing n positive integers not exceeding n, is it always possible to find a perfect matching of K_v whose list of edge-lengths is L? Up to now a (non-constructive) solution is known only when all the edge-lengths are coprime with v. In this paper we firstly present some necessary conditions for the existence of a solution. Then, we give a complete constructive solution when the list consists of one or two distinct elements, and when the list consists of consecutive integers 1,2,...,x, each one appearing with the same multiplicity. Finally, we propose a conjecture and some open problems.
AB - In this paper we consider the seating couples problem with an even number of seats, which, using graph theory terminology, can be stated as follows. Given a positive even integer v=2n and a list L containing n positive integers not exceeding n, is it always possible to find a perfect matching of K_v whose list of edge-lengths is L? Up to now a (non-constructive) solution is known only when all the edge-lengths are coprime with v. In this paper we firstly present some necessary conditions for the existence of a solution. Then, we give a complete constructive solution when the list consists of one or two distinct elements, and when the list consists of consecutive integers 1,2,...,x, each one appearing with the same multiplicity. Finally, we propose a conjecture and some open problems.
KW - Seating couples problem
KW - Skolem sequence
KW - Matching
KW - Seating couples problem
KW - Skolem sequence
KW - Matching
UR - http://hdl.handle.net/10807/286836
U2 - 10.1016/j.disc.2024.114182
DO - 10.1016/j.disc.2024.114182
M3 - Article
SN - 0012-365X
VL - 347
SP - N/A-N/A
JO - Discrete Mathematics
JF - Discrete Mathematics
ER -