Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
On the representation number of a crown graph. / Glen, Marc; Kitaev, Sergey; Pyatkin, Artem.
в: Discrete Applied Mathematics, Том 244, 31.07.2018, стр. 89-93.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
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