Nazwij klasę wykresów: Rozłączne połączenie kliki i zbioru niezależnego

9

Pozwolić sol być wykresem będącym rozłącznym związkiem kliki i niezależnym zbiorem, tj.

sol=K.n1+K.n2)¯=K.n1+jan2).

Klasa grafów wszystkich takich wykresów charakteryzuje się zabronionym indukowanym zestawem a zatem jest to przecięcie wykresu skupień i wykresu podziału (lub progu).H.={2)K.2),P.3)}

Czy ta (bardzo prosta) klasa grafów ma nazwę? Nie mogłem znaleźć klasy grafów na  ISGCI , a artykuły, które znam na ten temat (np. Edycja prostych wykresów i problem z edycją kliki ) nie odnoszą się do klasy po nazwie.

Oto rysunek takiego wykresu:

wykres podziału klastra

reference-request graph-theory graph-classes Pål GD
źródło
1
Niestety „podzielone wykresy klastrowe” wydają się być używane do innej koncepcji (wykresy, na których każdy podłączony komponent jest podzielony).
David Eppstein

Odpowiedzi:

7

Uzupełnieniem krawędzi wykresów w twojej klasie są kompletne wykresy podzielone: ​​można je podzielić na niezależny zbiór i klikę, tak że każdy wierzchołek w niezależnym zestawie sąsiaduje z każdym wierzchołkiem kliki (patrz na przykład http: //www.mathcove.net/petersen/lessons/get-lesson?les=30 ). Dlatego możesz nazwać swoje współdzielone wykresy dzielone klasy wykresu.

Bart Jansen
źródło
Dzięki, Bart. Nie ześlizguje się z języka, ale myślę, że będzie trzeba.
Pål GD
Co z niezależnym podzielonym wykresem ? A może byłoby to mylone z czymś innym?
Pål GD
6

W ostatnim artykule Hüffner, Komusiewicz i Nichterlein nazywają tę klasę rzadkimi wykresami podziału . Odnoszą się również do klasy dopełniacza, kompletnych wykresów podziału, jako gęstych wykresów podziału .

Hüffner, Komusiewicz i Nichterlein. „Edycja wykresów w kilka kliknięć: złożoność, aproksymacja i schematy jądra”.

Pål GD
źródło