|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
Графы, представимые в виде слов. Обзор результатов
С. В. Китаевa, А. В. Пяткинbc a University of Strathclyde, Livingstone Tower, 26 Richmond St., Glasgow, G1 1XH, UK
b Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
c Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия
Аннотация:
Будем говорить, что буквы $x$ и $y$ чередуются в слове $w$, если при удалении из $w$ всех букв кроме $x$ и $y$ получается либо слово вида $xyxy\dots$, либо слово вида $yxyx\dots$ (каждое из этих слов может иметь как чётную, так и нечётную длину). Граф $G=(V,E)$ представим в виде слова, если существует конечное слово $w$ над алфавитом $V$, в котором буквы $x$ и $y$ чередуются тогда и только тогда, когда $xy\in E$.
Графы, представимые в виде слов, включают многие важные классы графов, например: графы пересечения хорд, $3$-графы и графы сравнимости. В настоящей статье даётся полный обзор известных результатов по теории графов, представимых в виде слов, включая самые последние достижения в этой области. Табл. 2, ил. 11, библиогр. 48.
Ключевые слова:
представление графов, ориентация, слово, паттерн.
Статья поступила: 11.08.2017 Переработанный вариант: 12.12.2018
Образец цитирования:
С. В. Китаев, А. В. Пяткин, “Графы, представимые в виде слов. Обзор результатов”, Дискретн. анализ и исслед. опер., 25:2 (2018), 19–53; J. Appl. Industr. Math., 12:2 (2018), 278–296
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da894 https://www.mathnet.ru/rus/da/v25/i2/p19
|
Статистика просмотров: |
Страница аннотации: | 422 | PDF полного текста: | 277 | Список литературы: | 60 | Первая страница: | 8 |
|