Beri nama kelas grafik: Pisahkan penggabungan dari klik dan satu set independen

9

Misalkan  adalah grafik yang merupakan gabungan yang terpisah dari sebuah klik dan satu set independen, yaitu G = K_ {n_1} + \ overline {K_ {n_2}} = K_ {n_1} + I_ {n_2}.G

G=Kn1+Kn2¯=Kn1+In2.

Kelas grafik dari semua grafik tersebut dicirikan oleh subgraph diinduksi terlarang yang disetel H={2K2,P3} dan dengan demikian merupakan perpotongan dari grafik cluster dan grafik split (atau ambang).

Apakah kelas grafik ini (sangat sederhana) memiliki nama? Saya tidak dapat menemukan kelas grafik di  ISGCI , dan makalah yang saya tahu tentang topik (misalnya Mengedit Grafik Sederhana dan Pada masalah pengeditan kelompok ) tidak merujuk kelas dengan nama.

Berikut adalah gambar dari grafik tersebut:

grafik cluster-split

reference-request graph-theory graph-classes Pål GD
sumber
1
Sayangnya "grafik cluster split" tampaknya digunakan untuk konsep yang berbeda (grafik di mana setiap komponen yang terhubung dibagi).
David Eppstein

Jawaban:

7

Tepi-komplemen grafik di kelas Anda adalah grafik split lengkap: mereka dapat dipartisi ke dalam set independen dan klik, sehingga setiap simpul dalam set independen berdekatan dengan setiap simpul dalam klik (lihat, misalnya, http: //www.mathcove.net/petersen/lessons/get-lesson?les=30 ). Oleh karena itu, Anda dapat memanggil grafik perpecahan bersama kelas grafik Anda.

Bart Jansen
sumber
Terima kasih, Bart. Itu tidak benar-benar menggulung lidah, tapi kurasa itu harus dilakukan.
Pål GD
Bagaimana dengan grafik split independen ? Atau mungkin itu akan membingungkan dengan sesuatu yang lain?
Pål GD
6

Dalam sebuah artikel baru-baru ini, Hüffner, Komusiewicz, dan Nichterlein menyebut kelas ini sebagai grafik split yang jarang . Mereka juga merujuk ke kelas komplemen, grafik split lengkap, sebagai grafik split padat .

Hüffner, Komusiewicz, dan Nichterlein. "Mengedit Grafik ke dalam Beberapa Klik: Skema Kompleksitas, Perkiraan, dan Kernelisasi."

Pål GD
sumber