Structural and combinatorial properties of 2-swap word permutation graphs

Duncan Adamson; Nathan Flaherty; Igor Potapov; Paul G. Spirakis

doi:10.1007/978-3-031-55601-2_5

Structural and combinatorial properties of 2-swap word permutation graphs

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

^*Corresponding author for this work

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 v∘s=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 language	English
Title of host publication	LATIN 2024 - Theoretical informatics
Subtitle of host publication	16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part II
Editors	José A. Soto, Andreas Wiese
Place of Publication	Cham
Publisher	Springer
Pages	61-76
Number of pages	16
ISBN (Electronic)	9783031556012
ISBN (Print)	9783031556005
DOIs	https://doi.org/10.1007/978-3-031-55601-2_5
Publication status	Published - 6 Mar 2024
Event	16th Latin American Symposium on Theoretical Informatics, LATIN 2042 - Puerto Varas, Chile Duration: 18 Mar 2024 → 22 Mar 2024 https://latin2024.cmm.uchile.cl/

Publication series

Name	Lecture notes in computer science
Volume	14579
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th Latin American Symposium on Theoretical Informatics, LATIN 2042
Country/Territory	Chile
City	Puerto Varas
Period	18/03/24 → 22/03/24
Internet address	https://latin2024.cmm.uchile.cl/

Keywords

Combinatorics on words
Parikh vector
Graph algorithms
Permutation

Access to Document

10.1007/978-3-031-55601-2_5

Adamson-2024-Structural-and-combinatorial-LATIN-2024-AAM-CCBY
Copyright © 2024 the Authors. This work has been made available online in accordance with the University of St Andrews Open Access policy. This accepted manuscript is distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. The final published version of this work is available at https://doi.org/10.1007/978-3-031-55601-2_5.
Accepted author manuscript, 261 KBLicence: CC BY

Cite this

Adamson, D., Flaherty, N., Potapov, I., & Spirakis, P. G. (2024). Structural and combinatorial properties of 2-swap word permutation graphs. In J. A. Soto, & A. Wiese (Eds.), LATIN 2024 - Theoretical informatics: 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part II (pp. 61-76). (Lecture notes in computer science; Vol. 14579). Springer. https://doi.org/10.1007/978-3-031-55601-2_5

Adamson, Duncan ; Flaherty, Nathan ; Potapov, Igor et al. / Structural and combinatorial properties of 2-swap word permutation graphs. LATIN 2024 - Theoretical informatics: 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part II. editor / José A. Soto ; Andreas Wiese. Cham : Springer, 2024. pp. 61-76 (Lecture notes in computer science).

@inproceedings{c7b915dd1a684a23a5a2988c0962fbd7,

title = "Structural and combinatorial properties of 2-swap word permutation graphs",

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 v∘s=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.",

keywords = "Combinatorics on words, Parikh vector, Graph algorithms, Permutation",

author = "Duncan Adamson and Nathan Flaherty and Igor Potapov and Spirakis, {Paul G.}",

note = "Funding: This work is supported by the Leverhulme Research Centre for Functional Materials Design and EPSRC grants EP/P02002X/1, EP/R018472/1.; 16th Latin American Symposium on Theoretical Informatics, LATIN 2042 ; Conference date: 18-03-2024 Through 22-03-2024",

year = "2024",

month = mar,

day = "6",

doi = "10.1007/978-3-031-55601-2_5",

language = "English",

isbn = "9783031556005",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "61--76",

editor = "Soto, {Jos{\'e} A.} and Andreas Wiese",

booktitle = "LATIN 2024 - Theoretical informatics",

address = "Netherlands",

url = "https://latin2024.cmm.uchile.cl/",

}

Adamson, D, Flaherty, N, Potapov, I & Spirakis, PG 2024, Structural and combinatorial properties of 2-swap word permutation graphs. in JA Soto & A Wiese (eds), LATIN 2024 - Theoretical informatics: 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part II. Lecture notes in computer science, vol. 14579, Springer, Cham, pp. 61-76, 16th Latin American Symposium on Theoretical Informatics, LATIN 2042, Puerto Varas, Chile, 18/03/24. https://doi.org/10.1007/978-3-031-55601-2_5

Structural and combinatorial properties of 2-swap word permutation graphs. / Adamson, Duncan; Flaherty, Nathan; Potapov, Igor et al.
LATIN 2024 - Theoretical informatics: 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part II. ed. / José A. Soto; Andreas Wiese. Cham: Springer, 2024. p. 61-76 (Lecture notes in computer science; Vol. 14579).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Structural and combinatorial properties of 2-swap word permutation graphs

AU - Adamson, Duncan

AU - Flaherty, Nathan

AU - Potapov, Igor

AU - Spirakis, Paul G.

N1 - Funding: This work is supported by the Leverhulme Research Centre for Functional Materials Design and EPSRC grants EP/P02002X/1, EP/R018472/1.

PY - 2024/3/6

Y1 - 2024/3/6

N2 - 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 v∘s=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.

AB - 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 v∘s=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.

KW - Combinatorics on words

KW - Parikh vector

KW - Graph algorithms

KW - Permutation

U2 - 10.1007/978-3-031-55601-2_5

DO - 10.1007/978-3-031-55601-2_5

M3 - Conference contribution

AN - SCOPUS:85188729365

SN - 9783031556005

T3 - Lecture notes in computer science

SP - 61

EP - 76

BT - LATIN 2024 - Theoretical informatics

A2 - Soto, José A.

A2 - Wiese, Andreas

PB - Springer

CY - Cham

T2 - 16th Latin American Symposium on Theoretical Informatics, LATIN 2042

Y2 - 18 March 2024 through 22 March 2024

ER -

Adamson D, Flaherty N, Potapov I, Spirakis PG. Structural and combinatorial properties of 2-swap word permutation graphs. In Soto JA, Wiese A, editors, LATIN 2024 - Theoretical informatics: 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part II. Cham: Springer. 2024. p. 61-76. (Lecture notes in computer science). doi: 10.1007/978-3-031-55601-2_5