On the Word-Representability of Tensor Product Graphs
Abstract
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 × 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 Wn, complete graphs Kn, the Mycielskian of the cycle graph μn, and the extended Mycielskian of the cycle graph μ'n. Among our main results, we prove that W2n × G, μ2n × G, and μ'2n × G are always word-representable for any graph G; that Kn × Km is word-representable if and only if min{n,m} ≤ 3; and that tensor products G × H containing W2n+1 × W2m+1 or μ2n+1 × μ2m+1 or μ'2n+1 × μ'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.
Related
- The tensor product of the Fremlin tensor product of Banach lattice algebras
- Solution Analysis of Tensor Equation 𝒜 ltimes 𝒳 ltimes ℬ= 𝒞 via Semi Tensor Product with t-product
- Tensor product degenerate spin affine Hecke superalgebras
- Tensor Product Does Not Behave Additively on Delooping Level
- Einstein Metrics and Quantum Control on Symmetric Tensor Product Quotients
BibTeX
@misc{alshammari2026wordrepresentability,
title = {{On the Word-Representability of Tensor Product Graphs}},
author = {Nawaf Alshammari},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20881},
eprint = {2609.20881},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20881},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the Word-Representability of Tensor Product Graphs
AU - Nawaf Alshammari
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.20881
UR - https://arxiv.org/abs/2609.20881
AB - 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 × 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 μ_n, and the extended Mycielskian of the cycle graph μ'_n. Among our main results, we prove that W_2n × G, μ_2n × G, and μ'_2n × G are always word-representable for any graph G; that K_n × K_m is word-representable if and only if min{n,m} ≤ 3; and that tensor products G × H containing W_2n+1 × W_2m+1 or μ_2n+1 × μ_2m+1 or μ'_2n+1 × μ'_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.
ER -