Extremal permutations in routing cycles

Abstract: Let

G

be a graph on

n

vertices, labeled

v_{1}, l d o t s, v_{n}

and

p i

be a permutation on

[n] := 1, 2, c d o t s, n

. Suppose that each pebble

p_{i}

is placed at vertex

v_{p i (i)}

and has destination

v_{i}

. During each step, a disjoint set of edges is selected and the pebbles on each edge are swapped. Let

r t (G, p i)

, the routing number for

p i

, be the minimum number of steps necessary for the pebbles to reach their destinations. Li, Lu, and Yang prove that

r t (C_{n}, p i) l e n - 1

for any permutation on

n

-cycle

C_{n}

and conjecture that for

n g e q 5

, if

r t (C_{n}, p i) = n - 1

, then

p i = (123 c d o t s n)

or its inverse. By a computer search, they show that the conjecture holds for

n < 8

. We prove in this paper that the conjecture holds for all even

n

.

Full work available at URL: https://arxiv.org/abs/1404.1851

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cites Work

Cited In (3)

This page was built for publication: Extremal permutations in routing cycles