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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.