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

9

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

sol = {K.}_{n_{1}} + \bar{{K.}_{n_{2)}}} = {K.}_{n_{1}} + {ja}_{n_{2)}} .

$G = K_{n_1} + \overline{K_{n_2}} = K_{n_1} + I_{n_2} .$

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). $\mathcal{H} = \{2K_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

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