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.

Pasotti, A., Pellegrini, M. A., A Generalization of the Problem of Mariusz Meszka, <<GRAPHS AND COMBINATORICS>>, 2016; 32 (1): 333-350. [doi:10.1007/s00373-015-1563-0] [http://hdl.handle.net/10807/70606]

A Generalization of the Problem of Mariusz Meszka

Pellegrini, Marco Antonio
2016

Abstract

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.
2016
Inglese
Pasotti, A., Pellegrini, M. A., A Generalization of the Problem of Mariusz Meszka, <<GRAPHS AND COMBINATORICS>>, 2016; 32 (1): 333-350. [doi:10.1007/s00373-015-1563-0] [http://hdl.handle.net/10807/70606]
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/70606
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact