Nennen Sie die Graphklasse: Disjunkte Vereinigung einer Clique und einer unabhängigen Menge

Lassen  ein Graph sein, der die disjunkte Vereinigung einer Clique ist und ein unabhängiger Satz, dh G = K n 1 + ¯ K n 2 = K n 1 + I n 2$G$

Die Graphklasse aller derartigen Graphen ist durch die verbotenen induzierten Teilgraphen gekennzeichnet, die auf und ist somit der Schnittpunkt eines Clustergraphen und eines Teilungsgraphen (oder Schwellenwertgraphen).$\mathcal{H} = \{2K_2, P_3\}$

Hat diese (sehr einfache) Graphklasse einen Namen? Ich konnte die Diagrammklasse in ISGCI nicht finden  , und die mir bekannten Artikel zum Thema (z. B. Bearbeiten einfacher Diagramme und zum Problem der Cliquenbearbeitung ) beziehen sich nicht mit einem Namen auf die Klasse.

Hier ist eine Abbildung eines solchen Diagramms:

Das Kanten-Komplement von Diagrammen in Ihrer Klasse sind vollständig geteilte Diagramme: Sie können in eine unabhängige Menge und eine Clique unterteilt werden, sodass jeder Scheitelpunkt in der unabhängigen Menge an jeden Scheitelpunkt in der Clique angrenzt (siehe z. B. http: //www.mathcove.net/petersen/lessons/get-lesson?les=30 ). Daher können Sie Ihre Diagrammklasse als Co-Complete-Split-Diagramme bezeichnen.

In einem kürzlich erschienenen Artikel bezeichnen Hüffner, Komusiewicz und Nichterlein diese Klasse als dünn geteilte Graphen . Sie bezeichnen auch die Komplementklasse, die vollständigen geteilten Graphen, als dichte geteilte Graphen .

Hüffner, Komusiewicz und Nichterlein. "Bearbeiten von Graphen in wenigen Cliquen: Komplexitäts-, Approximations- und Kernelisierungsschemata."