On the representation number of a crown graph
Glen, Marc and Kitaev, Sergey and Pyatkin, Artem (2018) On the representation number of a crown graph. Discrete Applied Mathematics, 244. pp. 89-93. ISSN 0166-218X
|
Text (Glen-etal-DAM-2018-On-the-representation-number-of-a-crown)
Glen_etal_DAM_2018_On_the_representation_number_of_a_crown.pdf Accepted Author Manuscript License: ![]() Download (221kB)| Preview |
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.
Creators(s): |
Glen, Marc, Kitaev, Sergey ![]() | Item type: | Article |
---|---|
ID code: | 63469 |
Keywords: | word-representable graph, crown graph, cocktail party graph, representation number, Electronic computers. Computer science, Computer Science(all) |
Subjects: | Science > Mathematics > Electronic computers. Computer science |
Department: | Faculty of Science > Computer and Information Sciences |
Depositing user: | Pure Administrator |
Date deposited: | 13 Mar 2018 14:23 |
Last modified: | 01 Jan 2021 12:31 |
Related URLs: | |
URI: | https://strathprints.strath.ac.uk/id/eprint/63469 |
Export data: |