TOPICS
Search

Cactus Graph


CactusGraph

A cactus graph, sometimes also called a cactus tree, a mixed Husimi tree, or a polygonal cactus with bridges, is a connected graph in which any two graph cycles have no edge in common. Equivalently, it is a connected graph in which any two (simple) cycles have at most one vertex in common. Cactus graphs may also be defined as a connected planar graph in which every block is a cycle or an edge (White 2001, p. 57).

Every cycle of a cactus graph is a chordless. However, there exist graphs (e.g., the theta_0-graph and Pasch graph) whose cycles are all chordless but which are not cactus graphs.

The inequality

 mu(G)=nu(G),

where mu is the circuit rank and nu is the total number of undirected graph cycles holds for a connected graph G iff it is a cactus graph (Volkmann 1996).

Every cactus graph is a unit-distance graph (Erdős et al. 1965).

Every pseudotree is a cactus graph.

The numbers of cactus graphs on 1, 2, ... nodes are 1, 1, 2, 4, 9, 23, 63, 188, ... (OEIS A000083).


See also

Chordless Cycle, Graph Cycle, Pseudotree, Tree, Unit-Distance Graph

Explore with Wolfram|Alpha

References

Bona, M.; Bousquet, M.; Labelle, G.; and Leroux, P. "Enumeration of m-ary Cacti." Adv. Appl. Math. 24, 22-56, 2000.Chao, C. Y. and Whitehead, E. G. Jr. "On Chromatic Equivalence of Graphs." In Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976) (Ed. Y. Alavi and D. R. Lick). Berlin: Springer-Verlag, pp. 121-131, 1978.Erdős, P.; Harary, F.; and Tutte, W. T. "On the Dimension of a Graph." Mathematika 12, 118-122, 1965.Ford, G. W. and Uhlenbeck, G. E. "Combinatorial Problems in the Theory of Graphs III." Proc. Nat. Acad. Sci. USA 42, 529-535, 1956.Geller, D. and Manvel, B. "Reconstruction of Cacti." Canad. J. Math. 21, 1354-1360, 1969.Harary, F. and Uhlenbeck, G. "On the Number of Husimi Trees, I." Proc. Nat. Acad. Sci. USA 39, 315-322, 1953.Husimi, K. "Note on Mayers' Theory of Cluster Integrals." J. Chem. Phys. 18, 682-684, 1950.Sloane, N. J. A. Sequence A000083/M1191 in "The On-Line Encyclopedia of Integer Sequences."Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. New York: Springer, p. 91, 2008.Volkmann, L. "Estimations for the Number of Cycles in a Graph." Per. Math. Hungar. 33, 153-161, 1996.White, A. T. "Imbedding Problems in Graph Theory." Ch. 6 in Graphs of Groups on Surfaces: Interactions and Models (Ed. A. T. White). Amsterdam, Netherlands: Elsevier, 2001.

Referenced on Wolfram|Alpha

Cactus Graph

Cite this as:

Weisstein, Eric W. "Cactus Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CactusGraph.html

Subject classifications