Crown Graphs and Longest Word-Representants

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $G=(V,E)$ be a finite simple undirected graph. A word over $V$ is a finite sequence of vertices in which every vertex occurs. For distinct $x,y\in V$, let $w|_{\{x,y\}}$ be the word obtained by deleting every letter other than $x,y$. They alternate when this restriction has no equal consecutive letters, that is, it has the form $xyxy\cdots$ or $yxyx\cdots$, of either even or odd length. The word $w$ represents $G$ when, for every distinct $x,y$, \[ xy\in E\quad\Longleftrightarrow\quad x,y\text{ alternate in }w. \] Write $\mathrm{WR}(G)$ when such a word exists.

A word is $k$-uniform when every vertex occurs exactly $k$ times. For a word-representable graph its representation number is \[ \rho(G)=\min\{k\in\mathbb N:\text{some }k\text{-uniform word represents }G\}. \] Every word-representable graph admits a uniform representing word, so this minimum is defined. Uniform word length is $k|V|$; arbitrary repeated representing words are not used to measure the minimum.

A graph is bipartite if its vertices split into two sets and every edge joins the two sets. Every finite bipartite graph is word-representable. For $q\ge1$, the crown graph $H_{q,q}$ has vertex set $\{a_1,\ldots,a_q,b_1,\ldots,b_q\}$ and edges $a_ib_j$ exactly when $i\ne j$: it is $K_{q,q}$ with a perfect matching removed. The source computes $\rho(H_{q,q})=\lceil q/2\rceil$ for $q\ge5$. Here $\lceil x\rceil$ is the least integer at least $x$.

Statement recorded in the supplied source.

Among bipartite graphs of each fixed even order $2q$, do crown graphs maximize the representation number? Precisely, is \[ \rho(G)\le\rho(H_{q,q}) \] true for every $q\ge1$ and every bipartite graph $G$ with $2q$ vertices? In particular, for $q\ge5$ this is the bound $\rho(G)\le\lceil q/2\rceil$. The comparison uses shortest uniform word-representants, whose lengths are $2q\rho(G)$, as identified by the catalogue's literature review; it does not compare arbitrarily lengthened words. [S2]

Short English statement

At each fixed even number of vertices, do crown graphs need at least as many copies of each vertex as any other bipartite graph in a shortest uniform representation?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1435 (GRAPH-048). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Khyodeno Mozhui and K. V. Krishna, On the Conjecture of the Representation Number of Bipartite Graphs, arXiv:2506.01057v1 (2025), Section 1, pages 1--2, fixed-order crown extremality conjecture. https://arxiv.org/pdf/2506.01057v1.
• S3 Marc Glen, Sergey Kitaev and Artem Pyatkin, On the Representation Number of a Crown Graph, arXiv:1609.00674v1 (2016), abstract and Section 1.1. https://arxiv.org/pdf/1609.00674v1.