Panpositionable hamiltonicity and panconnectivity of the arrangement graphs
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.
- The paths embedding of the arrangement graphs with prescribed vertices in given position
- Panpositionable hamiltonicity of the alternating group graphs
- Panpositionable Hamiltonian graphs.
- Determining the Hamilton-connectedness of certain vertex-transitive graphs
- Edge-fault-tolerant pancyclicity of arrangement graphs
- A group-theoretic model for symmetric interconnection networks
- Arrangement graphs: A class of generalized star graphs
- Embedding of cycles in arrangement graphs
- scientific article; zbMATH DE number 52113 (Why is no real title available?)
- scientific article; zbMATH DE number 3550742 (Why is no real title available?)
- On embedding cycles into faulty twisted cubes
- On the arrangement graph.
- On the spanningw-wide diameter of the star graph
- Panconnectivity, fault-tolerant hamiltonicity and hamiltonian-connectivity in alternating group graphs
- Pancyclic graphs. I
- Panpositionable hamiltonicity of the alternating group graphs
- Parallel concepts in graph theory
- On the bipanpositionable bipanconnectedness of hypercubes
- Survey on path and cycle embedding in some networks
- Determining the Hamilton-connectedness of certain vertex-transitive graphs
- The paths embedding of the arrangement graphs with prescribed vertices in given position
- Conditional fault tolerance of arrangement graphs
- Orienting the arrangement graphs
- Two node-disjoint paths in balanced hypercubes
- Improving the panconnectedness property of locally twisted cubes
- Flexible cycle embedding in the locally twisted cube with nodes positioned at any prescribed distance
- Fault diagnosability of arrangement graphs
- Edge-fault-tolerant pancyclicity of arrangement graphs
- Panpositionable Hamiltonian graphs.
- Panpositionable hamiltonicity of the alternating group graphs
- Linearly many faults in arrangement graphs
- Embedding a Hamiltonian cycle in the crossed cube with two required vertices in the fixed positions
- Conditional matching preclusion for the arrangement graphs
- Panconnectivity and edge-pancyclicity of multidimensional torus networks
- The panpositionable panconnectedness of augmented cubes
This page was built for publication: Panpositionable hamiltonicity and panconnectivity of the arrangement graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2425998)
