## Abstract

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 xy 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.

Original language | English |
---|---|

Pages (from-to) | 89-93 |

Number of pages | 5 |

Journal | Discrete Applied Mathematics |

Volume | 244 |

DOIs | |

Publication status | Published - 31 Jul 2018 |

## Keywords

- Cocktail party graph
- Crown graph
- Representation number
- Word-representable graph
- PERKINS SEMIGROUP