Cactus graph

In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common.

Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or (for nontrivial cacti) in which every block (maximal subgraph without a cut-vertex) is an edge or a cycle.

A nontrivial graph is a cactus if and only if every block is either a simple cycle or a single edge.

For instance, the friendship graphs, graphs formed from a collection of triangles joined together at a single shared vertex, are triangular cacti.

Every tree with an odd number of vertices may be augmented to a triangular cactus by adding edges to it, giving a minimal augmentation with the property of remaining connected after the removal of a matching.

[2] The largest triangular cactus in any graph may be found in polynomial time using an algorithm for the matroid parity problem.

[3] The algorithm for finding the largest triangular cactus is associated with a theorem of Lovász and Plummer that characterizes the number of triangles in this largest cactus.

[4] Lovász and Plummer consider pairs of partitions of the vertices and edges of the given graph into subsets, with the property that every triangle of the graph either has two vertices in a single class of the vertex partition or all three edges in a single class of the edge partition; they call a pair of partitions with this property valid.

Then the number of triangles in the largest triangular cactus equals the maximum, over pairs of valid partitions

This result implies a direct analysis of the 4/9 - approximation algorithm for maximum planar subgraph problem without using the above min-max formula.

[5] An important conjecture related to the triangular cactus is the Rosa's Conjecture, named after Alexander Rosa, which says that all triangular cacti are graceful or nearly-graceful.

[7][8] Since cacti are special cases of outerplanar graphs, a number of combinatorial optimization problems on graphs may be solved for them in polynomial time.

Every polyhedral graph has a Christmas cactus subgraph that includes all of its vertices, a fact that plays an essential role in a proof by Leighton & Moitra (2010) that every polyhedral graph has a greedy embedding in the Euclidean plane, an assignment of coordinates to the vertices for which greedy forwarding succeeds in routing messages between all pairs of vertices.

[15] Cacti were first studied under the name of Husimi trees, bestowed on them by Frank Harary and George Eugene Uhlenbeck in honor of previous work on these graphs by Kôdi Husimi.

This usage had little to do with the work of Husimi, and the more pertinent term block graph is now used for this family; however, because of this ambiguity this phrase has become less frequently used to refer to cactus graphs.