Square-free Word-representation of Word-representable Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911402996793344 |
|---|---|
| author | Das, Biswajit Hariharasubramanian, Ramesh |
| author_facet | Das, Biswajit Hariharasubramanian, Ramesh |
| contents | A graph $G = (V, E)$ is word-representable, if there exists a word w over the alphabet V such that for letters ${x, y} \in V$ , $x$ and $y$ alternate in $w$ if and only if $xy \in E$. In this paper, we prove that any non-empty word-representable graph can be represented by a word containing no non-trivial squares. This result provides a positive answer to the open problem present in the book Words and graphs written by Sergey Kitaev, and Vadim Lozin. Also, we prove that for a word-representable graph $G$, if the representation number of $G$ is $k$, then every $k$-uniform word representing the graph $G$ is also square-free. Moreover, we prove that every minimal-length word representing a graph is square-free. Then, we count the number of possible square-free word-representations of a complete graph. At last, using the infinite square-free string generated from the Thue-Morse sequence, we prove that infinitely many square-free words represent a non-complete connected word-representable graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_14426 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Square-free Word-representation of Word-representable Graphs Das, Biswajit Hariharasubramanian, Ramesh Combinatorics A graph $G = (V, E)$ is word-representable, if there exists a word w over the alphabet V such that for letters ${x, y} \in V$ , $x$ and $y$ alternate in $w$ if and only if $xy \in E$. In this paper, we prove that any non-empty word-representable graph can be represented by a word containing no non-trivial squares. This result provides a positive answer to the open problem present in the book Words and graphs written by Sergey Kitaev, and Vadim Lozin. Also, we prove that for a word-representable graph $G$, if the representation number of $G$ is $k$, then every $k$-uniform word representing the graph $G$ is also square-free. Moreover, we prove that every minimal-length word representing a graph is square-free. Then, we count the number of possible square-free word-representations of a complete graph. At last, using the infinite square-free string generated from the Thue-Morse sequence, we prove that infinitely many square-free words represent a non-complete connected word-representable graph. |
| title | Square-free Word-representation of Word-representable Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2402.14426 |