Kaktusgraph
In der Graphentheorie bezeichnet ein Kaktusgraph (zum Teil auch nur Kaktus, manchmal auch Husimi-Baum) einen zusammenhängenden Graphen, in dem sich jedes Paar seiner Kreise höchstens einen gemeinsamen Knoten teilt.<ref>Vorlage:Cite book/URLVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/Meldung2 </ref>
Den Begriff Kaktusgraph (engl. cactus) führten Frank Harary und George Eugene Uhlenbeck ein.<ref>Vorlage:Cite book/URLVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/Meldung2 </ref> In dieser ursprünglichen Definition wurde jedoch verlangt, dass alle Kreise des Graphen Dreiecke sind.
Eigenschaften
- Ein Graph G ist ein Kaktusgraph genau dann, wenn die Anzahl seiner Zyklen seiner zyklomatischen Zahl <math>\mu (G)</math> entspricht.
- Kaktusgraphen sind außerplanare Graphen.
- Jeder planare 3-zusammenhängende Graph besitzt einen aufspannenden Kaktusgraphen, der die Eigenschaft hat, dass das Entfernen eines beliebigen Knoten den Graphen in maximal zwei Zusammenhangskomponenten teilt.<ref>Vorlage:Cite book/URLVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/Meldung2
</ref>
- Die Familie aller Kaktusgraphen kann durch einen verbotenen Minor charakterisiert werden. Dieser Minor entspricht dem vollständigen Graphen <math>K_4</math> in welchem eine Kante entfernt wurde.<ref>Vorlage:Cite book/URLVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/Meldung2</ref>
Einzelnachweise
<references/>