Structural and combinatorial properties of 2-swap word permutation graphs

Duncan Adamson, Nathan Flaherty*, Igor Potapov, Paul G. Spirakis

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we study the graph induced by the 2-swap permutation on words with a fixed Parikh vector. A 2-swap is defined as a pair of positions s=(i,j) where the word w induced by the swap s on v is v[1]v[2]⋯v[i-1]v[j]v[i+1]⋯v[j-1]v[i]v[j+1]⋯v[n]. With these permutations, we define the Configuration Graph, G(P) for a given Parikh vector. Each vertex in G(P) corresponds to a unique word with the Parikh vector P, with an edge between any pair of words v and w if there exists a swap s such that vs=w. We provide several key combinatorial properties of this graph, including the exact diameter of this graph, the clique number of the graph, and the relationships between subgraphs within this graph. Additionally, we show that for every vertex in the graph, there exists a Hamiltonian path starting at this vertex. Finally, we provide an algorithm enumerating these paths from a given input word of length n with a delay of at most O(log n) between outputting edges, requiring O(n log n) preprocessing.

Original languageEnglish
Title of host publicationLATIN 2024 - Theoretical informatics
Subtitle of host publication16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part II
EditorsJosé A. Soto, Andreas Wiese
Place of PublicationCham
PublisherSpringer
Pages61-76
Number of pages16
ISBN (Electronic)9783031556012
ISBN (Print)9783031556005
DOIs
Publication statusPublished - 6 Mar 2024
Event16th Latin American Symposium on Theoretical Informatics, LATIN 2042 - Puerto Varas, Chile
Duration: 18 Mar 202422 Mar 2024

Publication series

NameLecture notes in computer science
Volume14579
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th Latin American Symposium on Theoretical Informatics, LATIN 2042
Country/TerritoryChile
CityPuerto Varas
Period18/03/2422/03/24

Fingerprint

Dive into the research topics of 'Structural and combinatorial properties of 2-swap word permutation graphs'. Together they form a unique fingerprint.

Cite this