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.

Meszka, M., Pasotti, A., Pellegrini, M. A., The seating couples problem in the even case, <<DISCRETE MATHEMATICS>>, 2024; 347 (11): N/A-N/A. [doi:10.1016/j.disc.2024.114182] [https://hdl.handle.net/10807/286836]

The seating couples problem in the even case

Pellegrini, Marco Antonio
2024

Abstract

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.
2024
Inglese
Meszka, M., Pasotti, A., Pellegrini, M. A., The seating couples problem in the even case, <<DISCRETE MATHEMATICS>>, 2024; 347 (11): N/A-N/A. [doi:10.1016/j.disc.2024.114182] [https://hdl.handle.net/10807/286836]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10807/286836
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact