p-complete square-free Word-representation of Word-representable Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914218120314880 |
|---|---|
| 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 V such that distinct letters x and y alternate in w iff $xy \in E$. We introduce p-complete squares and p-complete square-free word-representable graphs. A word is p-complete square-free if no induced subword over any subset of letters contains a square XX with $|X| \ge p$. A graph is p-complete square-free if it admits such a representation. We define p-complete square-free uniform word-representations and study their properties. We show that any graph admitting such a representation forbids Kp as an induced subgraph and that the recognition problem is NP-hard for arbitrary p. For p=1 and 2, we give complete characterisations. We prove that every $K_p$-free circle graph admits a p-complete square-free uniform representation and that any 3-complete square-free uniform word-representable graph has representation number at most three. We present a constructive method for generating new examples for p=3. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_05110 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | p-complete square-free Word-representation of Word-representable Graphs Das, Biswajit Hariharasubramanian, Ramesh Discrete Mathematics Combinatorics A graph G(V, E) is word-representable if there exists a word w over V such that distinct letters x and y alternate in w iff $xy \in E$. We introduce p-complete squares and p-complete square-free word-representable graphs. A word is p-complete square-free if no induced subword over any subset of letters contains a square XX with $|X| \ge p$. A graph is p-complete square-free if it admits such a representation. We define p-complete square-free uniform word-representations and study their properties. We show that any graph admitting such a representation forbids Kp as an induced subgraph and that the recognition problem is NP-hard for arbitrary p. For p=1 and 2, we give complete characterisations. We prove that every $K_p$-free circle graph admits a p-complete square-free uniform representation and that any 3-complete square-free uniform word-representable graph has representation number at most three. We present a constructive method for generating new examples for p=3. |
| title | p-complete square-free Word-representation of Word-representable Graphs |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2505.05110 |