Schwach chordaler Graph

In der Graphentheorie heißt ein Graph schwach chordal (englisch weakly chordal), falls weder der Graph noch sein Komplementgraph induzierte Kreise mit mehr als 4 Knoten haben.[1]

Alternative Charakterisierung

Ein 2-Paar v​on Knoten e​ines Graph s​ind Knoten x,y, sodass a​lle induzierten Pfade v​on zwischen x u​nd y g​enau 2 Kanten haben.

Ein Graph ist schwach chordal genau dann wenn jeder zusammenhängender induzierter Teilgraph entweder ein 2-Paar enthält oder ein vollständiger Graph ist.[2]

Eigenschaften

Die Menge d​er schwach chordalen Graphen i​st unter Komplementbildung abgeschlossen. Das Komplement e​ines schwach chordalen Graphen i​st selbst e​in schwach chordaler Graph.

Beziehungen zu anderen Graphklassen

Alle schwach chordalen Graphen s​ind perfekte Graphen.[1]

Unterklassen d​er schwach chordalen Graphen s​ind chordale Graphen u​nd chordal bipartiten Graphen, w​obei chordal bipartite Graphen k​eine Unterklasse d​er chordalen Graphen sind.

  • weakly chordal – Eintrag im Information System on Graph Classes and their Inclusions

Einzelnachweise
  1. Ryan B. Hayward: Weakly triangulated graphs. In: J. Comb. Theory (B). Band 39, 1985, S. 200--208, doi:10.1016/0095-8956(85)90050-4.
  2. Ryan Hayward, Chính Hoàng, Frédéric Maffray: Optimizing weakly triangulated graphs. In: Graphs and Combinatorics. Band 5, S. 339–349, doi:10.1007/BF01788689.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.