Том 9, серия 1, номер 2 , 2002 г., Стр. 48-90

УДК 519.17
Ю. Л. Орлович
Покрытия кликами, факторы и графы с изоморфными окружениями вершин

Аннотация:
Одна из известных проблем теории графов – проблема окружений – заключается в том, чтобы для данного конечного графа $H$ определить, существует ли связный граф $G$, в котором окружение каждой вершины порождает подграф, изоморфный графу $H$. Граф $G$, удовлетворяющий такому условию, принято называть реализацией графа $H$. В настоящее время проблема окружений решена для ряда конкретных графов $H$. Однако до сих пор не разработаны общие методы, которые для графов из каких-либо классов позволяли бы распознавать существование соответствующих им реализаций. Это отчасти объясняется тем, что в классе всех конечных графов проблема окружений алгоритмически неразрешима. В данной статье мы определяем достаточно широкие классы графов, для которых можно построить счетные множества как конечных, так и бесконечных реализаций, и предлагаем методы систематического выявления таких классов.
Ил. 9, библиогр. 32.

Орлович Ю. Л. ¹
1. Институт математики НАН Беларуси,
ул. Сурганова, 11, 220072 Минск, Республика Беларусь
е-mail: orlovich@im.bas-net.by

Статья поступила 10 января 2002 г.