Metraipolis › archive › dc_17a22acfdf44

On the Word-Representability of Tensor Product Graphs — arXiv:2609.20881

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.20881
License (as archived)
CC0-1.0
Archived
2026-10-10T02:10:26.502Z
SHA-256 of the archived text
1bd0f64f112fb698f85ae37a95547a2b327f88568c77b62a228bc436b2dbad07
Stable URL of this page
https://metraipolis.com/documento/dc_17a22acfdf44

How to cite

On the Word-Representability of Tensor Product Graphs — arXiv:2609.20881 — arXiv (en), https://arxiv.org/abs/2609.20881 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_17a22acfdf44 (Metraipolis archive dc_17a22acfdf44, sha256 1bd0f64f112fb698f85ae37a95547a2b327f88568c77b62a228bc436b2dbad07)
BibTeX
@misc{dc17a22acfdf44,
  title = {On the Word-Representability of Tensor Product Graphs — arXiv:2609.20881},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.20881},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_17a22acfdf44; sha256 1bd0f64f112fb698f85ae37a95547a2b327f88568c77b62a228bc436b2dbad07},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.20881. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Word-representable graphs are a class of graphs that can be represented by words, where edges and non-edges are determined by the alternation of letters in those words. The tensor product $G \times H$ (also known as the direct product or Kronecker product) is one of the four standard graph products. Problem 7.2.5 in Kitaev and Lozin's book \emph{Words and Graphs} (Springer, 2015) raised three open questions regarding the word-representability of tensor products. Despite extensive research on word-representable graphs, the word-representability of tensor products seems to have received no attention. This paper not only answers 2.5 of the questions posed by Kitaev and Lozin in Problem 7.2.5, but also initiates a systematic study, focusing on four fundamental families: wheel graphs $W_n$, complete graphs $K_n$, the Mycielskian of the cycle graph $\mu_n$, and the extended Mycielskian of the cycle graph $\mu'_n$. Among our main results, we prove that $W_{2n} \times G$, $\mu_{2n} \times G$, and $\mu'_{2n} \times G$ are always word-representable for any graph $G$; that $K_n \times K_m$ is word-representable if and only if $\min\{n,m\} \leq 3$; and that tensor products $G \times H$ containing $W_{2n+1} \times W_{2m+1}$ or $\mu_{2n+1} \times \mu_{2m+1}$ or $\mu'_{2n+1} \times \mu'_{2m+1}$ as induced subgraphs are non-word-representable. Our proofs exploit the hereditary nature of non-word-representability and the presence of non-comparability neighbourhoods.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-21 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.20881 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T01:48:20.581Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).