A Generalization of the Problem of Mariusz Meszka

Risultato della ricerca: Contributo in rivistaArticolo in rivistapeer review

1 Citazioni (Scopus)


Mariusz Meszka has conjectured that given a prime p = 2n + 1 and a list L containing n positive integers not exceeding n there exists a near 1-factor in K_p whose list of edge-lengths is L. In this paper we propose a generalization of this problem to the case in which p is an odd integer not necessarily prime. In particular, we give a necessary condition for the existence of such a near 1-factor for any odd integer p. We show that this condition is also sufficient for any list L whose underlying set S has size 1, 2, or n. Then we prove that the conjecture is true if S = {1, 2, t} for any positive integer t not coprime with the order p of the complete graph. Also, we give partial results when t and p are coprime. Finally, we present a complete solution for t ≤ 11.
Lingua originaleEnglish
pagine (da-a)333-350
Numero di pagine18
RivistaGraphs and Combinatorics
Stato di pubblicazionePubblicato - 2016


  • Complete graph
  • Cyclic decomposition
  • Edge-length
  • Near 1-factor
  • Skolem sequence


Entra nei temi di ricerca di 'A Generalization of the Problem of Mariusz Meszka'. Insieme formano una fingerprint unica.

Cita questo