The splicing of cycle permutation graphs
Let \(\alpha\) be a permutation of order \(n\) and \(\beta\) be a permutation of order \(m\). Let \(M_ \alpha\) be a set of disjoint edges \(\{x_ k y_{\alpha(k)}: k= 1,\dots, n\}\) and \(M_ \beta\) be a set of disjoint edges \(\{u_ k v_{\beta(k)}: k= 1,\dots, m\}\). A splicing \((\alpha, \beta, i, j)\) is a permutation graph \(G\) with \(V(G)= V(M_ \alpha)\cup V(M_ \beta)\) and \(E(G)= F\cup M_ \alpha\cup M_ \beta\), where \(F\) is the union of two disjoint circuits \(C_ 1\), \(C_ 2\): \[ C_ 1 = x_ 1\dots x_ i u_ 1\dots u_ m x_{i+ 1}\dots x_ n x_ 1\quad\text{and}\quad C_ 2= y_ 1\dots y_ j v_ 1\dots v_ m y_{j+ 1}\dots y_ n y_ 1. \] Some sufficient conditions for determining whether a splicing \((\alpha, \beta, i, j)\) is Hamiltonian (or non-Hamiltonian) are obtained in this paper. Note that the operation of splicing is isomorphic to the operation of catenation (by re-labeling the vertices of \(C_ 1\) and \(C_ 2\)).
- On cycle permutation graphs
- scientific article; zbMATH DE number 1539546
- scientific article; zbMATH DE number 3898942
- scientific article; zbMATH DE number 622475
- Split permutation graphs
- scientific article; zbMATH DE number 3970804
- Splice graphs and their vertex-degree-based invariants
- On the Toughness of Cycle Permutation Graphs
- On permutation graphs
- scientific article; zbMATH DE number 3906532
This page was built for publication: The splicing of cycle permutation graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1345196)
