Kaktusgraph

In d​er Graphentheorie bezeichnet e​in Kaktusgraph (zum Teil a​uch nur Kaktus) e​inen zusammenhängenden Graphen, i​n dem s​ich jedes Paar seiner Kreise höchstens e​inen gemeinsamen Knoten teilt.[1]

Ein Kaktusgraph

Den Begriff Kaktusgraph (engl. cactus) führten Frank Harary u​nd George Eugene Uhlenbeck ein.[2] In dieser ursprünglichen Definition w​urde jedoch verlangt, d​ass alle Kreise d​es Graphen Dreiecke sind.

Eigenschaften
  • Ein Graph G ist ein Kaktusgraph genau dann, wenn die Anzahl seiner Zyklen seiner zyklomatischen Zahl 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.[3]
  • Die Familie aller Kaktusgraphen kann durch einen verbotenen Minor charakterisiert werden. Dieser Minor entspricht dem vollständigen Graphen in welchem eine Kante entfernt wurde.[4]

Einzelnachweise
  1. Dennis Geller, Bennet Manvel: Reconstruction of cacti. In: Canad. J. Math.. 21, 1969, S. 1354–1360. doi:10.4153/CJM-1969-149-3.
  2. Frank Harary, George E. Uhlenbeck: On the number of Husimi trees, I. In: Proceedings of the National Academy of Sciences. 39, Nr. 4, 1953, S. 315–322. Mathematical Reviews 0053893. doi:10.1073/pnas.39.4.315.
  3. Tom Leighton, Ankur Moitra: Some Results on Greedy Embeddings in Metric Spaces. In: Discrete & Computational Geometry. 44, Nr. 3, 2010, S. 686–705. doi:10.1007/s00454-009-9227-6.
  4. Ehab El-Mallah, Charles J. Colbourn: The complexity of some edge deletion problems. In: IEEE Transactions on Circuits and Systems. 35, Nr. 3, 1988, S. 354–362. doi:10.1109/31.1748.
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.