On the representation number of a crown graph

Marc Glen, Sergey Kitaev, Artem Pyatkin

Research output: Contribution to journalArticle

2 Citations (Scopus)
12 Downloads (Pure)

Abstract

A graph G = (V,E) is word-representable if there exists a word ω over the alphabet V such that letters x and y alternate in ω 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 ω representing G such that each letter occurs exactly k times in ω. The minimum such k is called G’s representation number.
A crown graph (also known as a cocktail party graph) Hn,n is a graph obtained from the complete bipartite graph Kn,n by removing a perfect matching. In this paper, we show that for n≥ 5,Hn,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 languageEnglish
Pages (from-to)89-93
Number of pages5
JournalDiscrete Applied Mathematics
Volume244
Early online date23 Mar 2018
DOIs
Publication statusPublished - 31 Jul 2018

Keywords

  • word-representable graph
  • crown graph
  • cocktail party graph
  • representation number

Fingerprint Dive into the research topics of 'On the representation number of a crown graph'. Together they form a unique fingerprint.

  • Cite this