Cactus graph

A cactus graph

In graph theory , a cactus graph (sometimes just a cactus ) describes a connected graph in which each pair of its circles shares at most one common node .

The term cactus graph (Engl. Cactus ) led Frank Harary and George Uhlenbeck a. In this original definition, however, it was required that all circles on the graph be triangles.

properties

A graph G is a cactus graph if and only if the number of its cycles corresponds to its cyclomatic number . ${\ displaystyle \ mu (G)}$
Cactus graphs are extraplanar graphs.
Every planar 3-connected graph has a spanning cactus graph, which has the property that removing any node divides the graph into a maximum of two connected components.
The family of all cactus graphs can be characterized by a forbidden minor . This minor corresponds to the complete graph in which an edge was removed. ${\ displaystyle K_ {4}}$

Individual evidence

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

[1] Dennis Geller, Bennet Manvel: Reconstruction of cacti . In: Canad. J. Math. . 21, 1969, pp. 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, No. 4, 1953, pp. 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, No. 3, 2010, pp. 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, No. 3, 1988, pp. 354-362. doi : 10.1109 / 31.1748 .