Czy ta klasa wykresów ma nazwę?

Jest sformułowany przez rozszerzenie wykresów progowych . Biorąc pod uwagę wykres progowy gdzie jest kliką, a jest niezależnym zbiorem, moje rozszerzenie jest następujące: Każdy wierzchołek można zastąpić nową kliką tak, że wierzchołki mają to samo sąsiedzi .$(C,I)$$C$$I$$v\in I$$K_v$$K_v$$v$

Wydaje mi się, że należało to zbadać, ale trudno jest znaleźć coś takiego na graphclasses.org.

Uważam, że są to dokładnie od ( , , ) - to znaczy wykresy, których indukowane wykresy podrzędne nie obejmują 4-cykli, ścieżek 4-wierzchołkowych lub wykresów utworzonych z rozłącznego połączenia dwóch 3- ścieżki wierzchołków. Ta klasa wydaje się leżeć między samymi wykresami progowymi, które można scharakteryzować jako od ( , , ), a trywialnie doskonałymi wykresami (przecięcia przedziałów zagnieżdżonych), które można scharakteryzować jako ( , ) - wolne wykresy. Nie sądzę, że ma nazwę; przynajmniej wydaje się, że nie jest wymieniony na graphclasses.org.$C_4$$P_4$$2P_3$$C_4$$P_4$$2K_2$$C_4$$P_4$

Aby przekonać się, że jest to właściwa charakterystyka, rozważ reprezentację trywialnie doskonałych wykresów jako przechodnie zamknięcie ukorzenionych lasów. Las powoduje powstanie (połączonego) wykresu progowego wtedy i tylko wtedy, gdy ma skierowaną ścieżkę, która zawiera wszystkie węzły inne niż liście: dodanie nowego izolowanego wierzchołka odpowiada w lesie dodaniu nowego drzewa jednowęzłowego, które nie nie zmieni tej właściwości, a dodanie nowego wierzchołka połączonego ze wszystkimi innymi odpowiada dodaniu nowego katalogu głównego podłączonego do wszystkich poprzednich katalogów głównych drzewa, co ponownie nie zmienia tej właściwości (nowy katalog główny może być częścią ścieżki) .

Teraz twoja operacja zastępowania kliki odpowiada, w widoku drzewa trywialnie idealnego wykresu, podziałowi krawędzi drzewa na ścieżki (lub zastąpieniu drzewa o jednym wierzchołku ścieżką). Lasy, które można uzyskać z tej operacji, to te, w których istnieje jedna ścieżka skierowana, która zawiera wszystkie węzły z dwoma lub więcej dziećmi. Las ma taką ścieżkę wtedy i tylko wtedy, gdy nie ma dwóch niepowiązanych widelców (węzłów z dwojgiem lub większą liczbą dzieci, z których żadne nie może się ze sobą połączyć). Podgraf, który dostajesz na swoim trywialnie idealnym wykresie, gdy są dwa widelce, wynosi dokładnie .$2P_3$

Wykresy, których uzupełnienia są w klasie, o którą pytasz - to znaczy od ( , , co- ) - zostały zbadane przez Gurskiego, który wykazał, że są one takie same jak wykresy liniowej szerokości kliki przy większość dwa. Patrz twierdzenie 10 Gurskiego, Franka, „Charakteryzacje dla ko-grafów określonych przez ograniczone operacje szerokości NLC lub kliknięć”, Discrete Math. 306 (2006), nr 2, 271–277 .$2K_2$$P_4$$2P_3$