О натягиваемых на 3-коклику графах без 3-лап с некликовыми μ-подграфами

Abstract

Говорят, что граф натягивается на некоторую свою 3-коклику, если любая вершина графа, не принадлежащая этой 3-коклике, смежна по крайней мере с двумя ее вершинами. В работе описаны конечные связные графы Г без 3-лап, в которых любые две вершины на расстоянии два лежат в порожденном 4-цикле, каждая вершина лежит в некоторой 3-коклике, и такие, что Г натягивается на одну свою 3-коклику и не натягивается на другую.

We say that a graph can be stretched on a 3-coclique if every vertex outside this 3-coclique is adjacent to at least two vertices from the 3-coclique. We describe finite connected claw-free graphs Г such that every pair of vertices at distance two lies in an induced 4-cycle, every vertex belongs to some 3-coclique and such that Г can be stretched on some 3-coclique and cannot be stretched on another one.