For a finite graph G whose vertices are different natural numbers we call two infinite permutations of the natural numbers G-different if they have two adjacent vertices of G somewhere in the same position. The maximum number of pairwise G-different permutations of the naturals is always finite. We study this maximum as a graph invariant and relate it to a problem of the first two authors on colliding permutations. An improvement on the lower bound for the maximum number of pairwise colliding permutations is obtained. © 2008 Society for Industrial and Applied Mathematics.

Graph-different permutations / Korner, Janos; Malvenuto, Claudia; Gabor, Simonyi. - In: SIAM JOURNAL ON DISCRETE MATHEMATICS. - ISSN 0895-4801. - STAMPA. - 22:2(2008), pp. 489-499. [10.1137/070692686]

Graph-different permutations

KORNER, JANOS;MALVENUTO, Claudia;
2008

Abstract

For a finite graph G whose vertices are different natural numbers we call two infinite permutations of the natural numbers G-different if they have two adjacent vertices of G somewhere in the same position. The maximum number of pairwise G-different permutations of the naturals is always finite. We study this maximum as a graph invariant and relate it to a problem of the first two authors on colliding permutations. An improvement on the lower bound for the maximum number of pairwise colliding permutations is obtained. © 2008 Society for Industrial and Applied Mathematics.
2008
extremal combinatorics; permutations; shannon capacity of graphs
01 Pubblicazione su rivista::01a Articolo in rivista
Graph-different permutations / Korner, Janos; Malvenuto, Claudia; Gabor, Simonyi. - In: SIAM JOURNAL ON DISCRETE MATHEMATICS. - ISSN 0895-4801. - STAMPA. - 22:2(2008), pp. 489-499. [10.1137/070692686]
File allegati a 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/11573/227834
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 11
social impact