The study of word-representable graphs asks a simple but surprisingly rich question: given a graph, can you write a sequence of letters such that two vertices are connected by an edge if and only if their corresponding letters alternate in a specific pattern throughout the word? Not all graphs have this property, and figuring out which ones do has been an active area of research. One natural way to build new graphs from old ones is through a construction called the tensor product, which combines two graphs by connecting vertices from each graph only when their counterparts are connected in both originals simultaneously. A textbook by Kitaev and Lozin posed several open questions about whether tensor products of word-representable graphs are themselves word-representable, and until now those questions had gone unanswered.
This paper takes on those open questions directly and resolves most of them. The authors focus on four well-known families of graphs: wheel graphs (a cycle with a central hub connected to every node), complete graphs (where every vertex connects to every other), and two more complex constructions called the Mycielskian and extended Mycielskian of cycle graphs, which are built by a process that increases a graph's complexity without adding triangles. By studying tensor products involving these families, the authors are able to answer two and a half of the three open questions posed in the textbook.
The main findings reveal a clean and satisfying pattern tied to whether key numbers are even or odd. Tensor products involving even-indexed wheel graphs or even-indexed Mycielskian graphs always turn out to be word-representable, no matter what the other graph in the product is. In contrast, tensor products involving odd-indexed versions of these graphs tend to produce graphs that are not word-representable. For complete graphs, the result is especially tidy: the tensor product of two complete graphs is word-representable if and only if the smaller of the two has at most three vertices. The proofs rely on a key property that non-word-representability spreads to larger graphs that contain problematic smaller structures, combined with careful analysis of neighborhood relationships within the products.