On the representation number of a crown graph.

A graph G = ( V , E ) is word-representable if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if x y is an edge in E . It is known (Kitaev and Pyatkin, 2008) that any word-representable graph G is k -word-representable for some k , that is, there exists a word w representing G such that each letter occurs exactly k times in w . The minimum such k is called G ’s representation number. A crown graph (also known as a cocktail party graph) H n , n is a graph obtained from the complete bipartite graph K n , n by removing a perfect matching. In this paper, we show that for n ≥ 5 , H n , n ’s representation number is ⌈ n ∕ 2 ⌉ . This result not only provides a complete solution to the open Problem 7.4.2 in Kitaev and Lozin (2015), but also gives a negative answer to the question raised in Problem 7.2.7 in Kitaev and Lozin (2015) on 3-word-representability of bipartite graphs. As a byproduct, we obtain a new example of a graph class with a high representation number. [ABSTRACT FROM AUTHOR]