### Abstract

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 language | English |
---|---|

Pages (from-to) | 89-93 |

Number of pages | 5 |

Journal | Discrete Applied Mathematics |

Volume | 244 |

Early online date | 23 Mar 2018 |

DOIs | |

Publication status | Published - 31 Jul 2018 |

### Fingerprint

### Keywords

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

### Cite this

*Discrete Applied Mathematics*,

*244*, 89-93. https://doi.org/10.1016/j.dam.2018.03.013

}

*Discrete Applied Mathematics*, vol. 244, pp. 89-93. https://doi.org/10.1016/j.dam.2018.03.013

**On the representation number of a crown graph.** / Glen, Marc; Kitaev, Sergey; Pyatkin, Artem.

Research output: Contribution to journal › Article

TY - JOUR

T1 - On the representation number of a crown graph

AU - Glen, Marc

AU - Kitaev, Sergey

AU - Pyatkin, Artem

PY - 2018/7/31

Y1 - 2018/7/31

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

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

KW - word-representable graph

KW - crown graph

KW - cocktail party graph

KW - representation number

UR - https://www.sciencedirect.com/journal/discrete-applied-mathematics

U2 - 10.1016/j.dam.2018.03.013

DO - 10.1016/j.dam.2018.03.013

M3 - Article

VL - 244

SP - 89

EP - 93

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -