Standard

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

In: Discrete Applied Mathematics, Vol. 244, 31.07.2018, p. 89-93.

Research output: Contribution to journal › Article › peer-review

Harvard

Glen, M, Kitaev, S & Pyatkin, A 2018, 'On the representation number of a crown graph', Discrete Applied Mathematics, vol. 244, pp. 89-93. https://doi.org/10.1016/j.dam.2018.03.013

APA

Glen, M., Kitaev, S., & Pyatkin, A. (2018). On the representation number of a crown graph. Discrete Applied Mathematics, 244, 89-93. https://doi.org/10.1016/j.dam.2018.03.013

Vancouver

Glen M, Kitaev S, Pyatkin A. On the representation number of a crown graph. Discrete Applied Mathematics. 2018 Jul 31;244:89-93. doi: 10.1016/j.dam.2018.03.013

Author

Glen, Marc ; Kitaev, Sergey ; Pyatkin, Artem. / On the representation number of a crown graph. In: Discrete Applied Mathematics. 2018 ; Vol. 244. pp. 89-93.

BibTeX

@article{278f7ab19fa54ae79d8767119b9c5756,
title = "On the representation number of a crown graph",
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) 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.",
keywords = "Cocktail party graph, Crown graph, Representation number, Word-representable graph, PERKINS SEMIGROUP",
author = "Marc Glen and Sergey Kitaev and Artem Pyatkin",
year = "2018",
month = jul,
day = "31",
doi = "10.1016/j.dam.2018.03.013",
language = "English",
volume = "244",
pages = "89--93",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

RIS

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 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) 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 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) 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 - Cocktail party graph

KW - Crown graph

KW - Representation number

KW - Word-representable graph

KW - PERKINS SEMIGROUP

UR - http://www.scopus.com/inward/record.url?scp=85044267417&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2018.03.013

DO - 10.1016/j.dam.2018.03.013

M3 - Article

AN - SCOPUS:85044267417

VL - 244

SP - 89

EP - 93

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -

ID: 12176370