An embedding technique in the study of word-representability of graphs

An embedding technique in the study of word-representability of graphs Full article

Journal

Discrete Applied Mathematics
ISSN: 0166-218X

Output data

Year: 2024, Volume: 346, Pages: 170-182 Pages count : 13 DOI: 10.1016/j.dam.2023.12.017

Tags

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

Authors

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

Affiliations

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

Submitted:	Aug 28, 2023
Accepted:	Dec 14, 2023
Published online:	Jan 9, 2024
Published print:	May 13, 2024

Web of science:	WOS:001145182600001
Scopus:	2-s2.0-85181002965
Elibrary:	66063039
OpenAlex:	W4390150971

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