У этого класса графа есть имя?

12

Это сформулировано путем расширения пороговых графиков . Учитывая пороговый граф где C - клика, а I - независимое множество, мое расширение выглядит следующим образом: Каждая вершина v I может быть заменена новой кликой K v, такой, что вершины K v имеют такие же соседи v .(C,I)CIvIKvKvv

Я думаю, что это должно быть изучено, но это трудно найти в Graphclasses.org.

Исин Цао
источник
Кажется, это график пересечения вложенных интервалов ( graphclasses.org/classes/gc_347.html ), но мне нужно проверить.
Исин Цао

Ответы:

15

C4P42P3C4P42K2C4P4) -без графов. Я не думаю, что у него есть имя; по крайней мере, его нет на сайте graphclasses.org.

Чтобы увидеть, что это правильная характеристика, рассмотрим представление тривиально совершенных графов как транзитивных замыканий корневых лесов. Лес порождает (связанный) пороговый граф тогда и только тогда, когда он имеет направленный путь, который содержит все неконечные узлы: добавление новой изолированной вершины в лесу соответствует добавлению нового одноузлового дерева, которое не Не меняйте это свойство, и добавление новой вершины, связанной со всеми остальными, соответствует добавлению нового корня, связанного со всеми предыдущими корнями дерева, что снова не меняет это свойство (новый корень может быть частью пути) ,

2P3

2K2P42P3

Дэвид Эппштейн
источник
2P3(C4,P4)
2P3