Panpositionable hamiltonicity and panconnectivity of the arrangement graphs (Q2425998): Difference between revisions

The arrangement graph \(A_{n,k}\) is the graph whose vertices are \(k\)-element arrangements of \(1, 2, \ldots , n\) with two ordered \(k\)-tuples joined by an edge if they differ in exactly one position. It turns out that \(A_{n,k}\) is panconnected, and pancyclic, for all \(n \geq3\) and \(n-k\geq2\). These properties follow from a new property the authors define which \(A_{n,k}\) possesses, namely that \(A_{n.k}\) is panpositionable Hamiltonian for \(k \geq1\) and \(n-k \geq 2\); that is, for any pair of distinct vertices \(x\) and \(y\) and for any integer \(l\) such that \(d(x,y) \leq l \leq |V(G)|-d(x,y)\), there is a Hamiltonian cycle \(C\) of \(G\) such that the distance between \(x\) and \(y\) measured on \(C\) is \(l\). The key procedure used to prove the theorem is demonstrated in showing \(A_{n,2}\) is panpositionable Hamiltonian for \(n\geq 4\). Given a pair of vertices \(x\) and \(y\), a Hamiltonian cycle is constructed on a subcomponent of \(A_{n,2}\) such that the \(x-y\) path is of a specified length. An algorithm is then provided to expand this path to the desired length by incorporating vertices in other subcomponents.