Покрытия кликами, факторы и графы с изоморфными окружениями вершин

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