Graph-Different Permutations

Authors:
  • JKJános Körner
    János Körner
  • CMClaudia Malvenuto
    Claudia Malvenuto
  • GSGábor Simonyi
    Gábor Simonyi

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.

This publication has 3 references indexed in Scilit: