Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.29629 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918427378057216 |
|---|---|
| author | Kenkireth, Benny George Sajith, Gopalan Sasidharan, Sreyas |
| author_facet | Kenkireth, Benny George Sajith, Gopalan Sasidharan, Sreyas |
| contents | We investigate the relationship between the lexicographic product of graphs and their multi-word-representation number. We establish bounds on the multi-word-representation number $μ$ for lexicographic powers and products. Specifically, if $G$ is a non-comparability graph, then $μ(G^{[k]}) \le k$, whereas if $G$ is the union of two comparability graphs, then $μ(G^{[k]}) = 2$. More generally, let $G_1$ and $G_2$ be graphs with $μ(G_1) = k_1$ and $μ(G_2) = k_2$. For their lexicographic product $H = G_1 \circ G_2$, we have $μ(H) \le k_1 + k_2$. This bound is tight: $μ(H) = k_1$ when $k_1 \ge k_2$ and $G_2$ is the union of $k_1$ comparability graphs. Furthermore, if $G_1$ and $G_2$ are minimal non-word-representable graphs, then $μ(G_1 \circ G_2) \le 3$. Finally, we study the function $τ(n)$, which measures the size of the largest word-representable induced subgraph guaranteed in every $n$-vertex graph. By constructing extremal graphs via lexicographic powers, we establish a sublinear upper bound, showing that $τ(n) \le n^{0.86}$ for sufficiently large $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_29629 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On Lexicographic Product and Multi-Word-Representability Kenkireth, Benny George Sajith, Gopalan Sasidharan, Sreyas Combinatorics Discrete Mathematics We investigate the relationship between the lexicographic product of graphs and their multi-word-representation number. We establish bounds on the multi-word-representation number $μ$ for lexicographic powers and products. Specifically, if $G$ is a non-comparability graph, then $μ(G^{[k]}) \le k$, whereas if $G$ is the union of two comparability graphs, then $μ(G^{[k]}) = 2$. More generally, let $G_1$ and $G_2$ be graphs with $μ(G_1) = k_1$ and $μ(G_2) = k_2$. For their lexicographic product $H = G_1 \circ G_2$, we have $μ(H) \le k_1 + k_2$. This bound is tight: $μ(H) = k_1$ when $k_1 \ge k_2$ and $G_2$ is the union of $k_1$ comparability graphs. Furthermore, if $G_1$ and $G_2$ are minimal non-word-representable graphs, then $μ(G_1 \circ G_2) \le 3$. Finally, we study the function $τ(n)$, which measures the size of the largest word-representable induced subgraph guaranteed in every $n$-vertex graph. By constructing extremal graphs via lexicographic powers, we establish a sublinear upper bound, showing that $τ(n) \le n^{0.86}$ for sufficiently large $n$. |
| title | On Lexicographic Product and Multi-Word-Representability |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2603.29629 |