Назовите класс графа: дизъюнктное объединение клики и независимого множества

9

Пусть  - граф, который является несвязным объединением клики и независимого множества, то есть G

G=Kn1+Kn2¯=Kn1+In2.

Класс графов всех таких графов характеризуется набором запрещенных индуцированных подграфов и, таким образом, является пересечением кластерного графа и расщепленного (или порогового) графа.H={2K2,P3}

У этого (очень простого) класса графа есть имя? Мне не удалось найти класс графа в  ISGCI , и статьи, которые я знаю по этой теме (например, Редактирование простых графиков и О проблеме редактирования клики ), не ссылаются на класс по имени.

Вот рисунок такого графика:

график расщепления кластеров

reference-request graph-theory graph-classes Пол Г.Д.
источник
1
К сожалению, кажется, что «разделенные графы кластеров» используются для другой концепции (графики, в которых каждый связанный компонент разделен).
Дэвид Эппштейн

Ответы:

7

Граничные дополнения графов в вашем классе являются полными расщепленными графами: они могут быть разбиты на независимый набор и клику, так что каждая вершина в независимом наборе смежна с каждой вершиной в клике (см., Например, http: //www.mathcove.net/petersen/lessons/get-lesson?les=30 ). Следовательно, вы могли бы назвать свой класс графов полностью завершенными расщепленными графами.

Барт Янсен
источник
Спасибо, Барт. Это не совсем скатывается с языка, но я думаю, что это нужно сделать.
Пол GD
Как насчет независимого сплит-графа ? Или это может быть перепутано с чем-то еще?
Пол Г.Д.
6

В недавней статье Хюффнер, Комусевич и Нихтерлейн называют этот класс разреженными расщепленными графами . Они также ссылаются на класс дополнения, полные расщепленные графы, как плотные расщепленные графы .

Хюффнер, Комусевич и Нихтерляйн. «Редактирование графиков в несколько кликов: схемы сложности, аппроксимации и ядра».

Пол Г.Д.
источник