Name
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1137/070692686 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
graph-different permutations,adjacent vertex,graph invariant,different natural number,natural number,pairwise colliding permutation,colliding permutation,different permutation,infinite permutation,maximum number,finite graph,permutations,extremal combinatorics | Permutation graph,Discrete mathematics,Combinatorics,Natural number,Golomb–Dickman constant,Vertex (geometry),Graph property,Permutation,Parity of a permutation,Stirling numbers of the first kind,Mathematics | Journal |
Volume | Issue | Citations |
22 | 2 | 3 |
PageRank | References | Authors |
0.51 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Körner | 1 | 3 | 0.51 |
| Claudia Malvenuto | 2 | 75 | 13.40 |
| Gábor Simonyi | 3 | 249 | 29.78 |