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
connectedplanar 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 -graph and Pasch graph)
whose cycles are all chordless but which are not cactus graphs.
The inequality
where
is the circuit rank and is the total number of undirected graph
cycles holds for a connected graph iff it is a cactus graph (Volkmann 1996).
Bona, M.; Bousquet, M.; Labelle, G.; and Leroux, P. "Enumeration of -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." Mathematika12, 118-122, 1965.Ford,
G. W. and Uhlenbeck, G. E. "Combinatorial Problems in the Theory of
Graphs III." Proc. Nat. Acad. Sci. USA42, 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. USA39, 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.