An embedding technique in the study of word-representability of graphs | Sciact - Система учета научной деятельности ИМ СО РАН

An embedding technique in the study of word-representability of graphs Научная публикация

Журнал

Discrete Applied Mathematics
ISSN: 0166-218X

Вых. Данные

Год: 2024, Том: 346, Страницы: 170-182 Страниц : 13 DOI: 10.1016/j.dam.2023.12.017

Ключевые слова

Simplified de Bruijn type graph, Word-representability, Semi-transitive orientation, Homomorphism

Авторы

Huang Sumin ¹ , Kitaev Sergey ² , Pyatkin A.V. ³

Организации

1	School of Mathematical Sciences, Xiamen University, Xiamen 361005, PR China
2	Department of Mathematics and Statistics, University of Strathclyde, 26 Richmond Street, Glasgow G1 1XH, United Kingdom
3	Sobolev Institute of Mathematics, Koptyug ave, 4, Novosibirsk, 630090, Russia

Word-representable graphs, which are the same as semi-transitively orientable graphs, generalize several fundamental classes of graphs. In this paper we propose a novel approach to study word-representability of graphs using a technique of homomorphisms. As a proof of concept, we apply our method to show word-representability of the simplified graph of overlapping permutations that we introduce in this paper. For another application, we obtain results on word-representability of certain subgraphs of simplified de Bruijn graphs that were introduced recently by Petyuk and studied in the context of word-representability.

Huang S. , Kitaev S. , Pyatkin A.V.
An embedding technique in the study of word-representability of graphs
Discrete Applied Mathematics. 2024. V.346. P.170-182. DOI: 10.1016/j.dam.2023.12.017 WOS Scopus РИНЦ OpenAlex

Поступила в редакцию:	28 авг. 2023 г.
Принята к публикации:	14 дек. 2023 г.
Опубликована online:	9 янв. 2024 г.
Опубликована в печати:	13 мая 2024 г.

Web of science:	WOS:001145182600001
Scopus:	2-s2.0-85181002965
РИНЦ:	66063039
OpenAlex:	W4390150971

Пока нет цитирований