Cactus graph

In graph theory called a cactus graph (sometimes even cactus ) a connected graph in which every pair of his circles more than sharing a common node.

The term cactus graph (English cactus ), introduced Frank Harary and George Eugene Uhlenbeck. In this original definition was, however, requires that all circuits of the graph are triangles.

Properties

  • A graph G is a cactus graph if and only if its number of cycles corresponding to its cyclomatic number.
  • Cactus graphs are extraplanar graph.
  • Each planar 3-connected graph has a spanning cactus graph having the property that the removal of any node splits the graph into at most 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 is removed.
George Uhlenbeck Circuit rank Graph minor Digital Object Identifier
460612
de