Hubbry Logo
search
logo
Cactus graph avatar
Cactus graph
Cactus graph
current hub
1575193

Cactus graph

logo
Community Hub0 Subscribers
Read side by side
Cactus graph
View on Wikipedia
from Wikipedia
A 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.

Properties

[edit]

Cacti are outerplanar graphs. Every pseudotree is a cactus. A nontrivial graph is a cactus if and only if every block is either a simple cycle or a single edge.

The family of graphs in which each component is a cactus is downwardly closed under graph minor operations. This graph family may be characterized by a single forbidden minor, the four-vertex diamond graph formed by removing an edge from the complete graph K4.[1]

Triangular cactus

[edit]
Friendship graphs are triangular cacti
Unsolved problem in mathematics
Are all triangular cacti graceful or nearly graceful?
More unsolved problems in mathematics

A triangular cactus is a special type of cactus graph such that each cycle has length three and each edge belongs to a cycle. For instance, the friendship graphs, graphs formed from a collection of triangles joined together at a single shared vertex, are triangular cacti. As well as being cactus graphs the triangular cacti are also block graphs and locally linear graphs.

Triangular cactuses have the property that they remain connected if any matching is removed from them; for a given number of vertices, they have the fewest possible edges with this property. 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. Since triangular cactus graphs are planar graphs, the largest triangular cactus can be used as an approximation to the largest planar subgraph, an important subproblem in planarization. As an approximation algorithm, this method has approximation ratio 4/9, the best known for the maximum planar subgraph 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 and , of

,

where is the number of vertices in the given graph and is the number of vertex classes met by edge class .

Every plane graph contains a cactus subgraph which includes at least fraction of the triangular faces of . 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]

Rosa's Conjecture

[edit]

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.[6] More precisely

All triangular cacti with t ≡ 0, 1 mod 4 blocks are graceful, and those with t ≡ 2, 3 mod 4 are near graceful.

Algorithms and applications

[edit]

Some facility location problems which are NP-hard for general graphs, as well as some other graph problems, may be solved in polynomial time for cacti.[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.[9]

Cacti represent electrical circuits that have useful properties. An early application of cacti was associated with the representation of op-amps.[10][11][12]

Cacti have also been used in comparative genomics as a way of representing the relationship between different genomes or parts of genomes.[13]

If a cactus is connected, and each of its vertices belongs to at most two blocks, then it is called a Christmas cactus. 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.[14]

In topological graph theory, the graphs whose cellular embeddings are all planar are exactly the subfamily of the cactus graphs with the additional property that each vertex belongs to at most one cycle. These graphs have two forbidden minors, the diamond graph and the five-vertex friendship graph.[15]

History

[edit]

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.[16][17] The same Harary–Uhlenbeck paper reserves the name "cactus" for graphs of this type in which every cycle is a triangle, but now allowing cycles of all lengths is standard.

Meanwhile, the name Husimi tree commonly came to refer to graphs in which every block is a complete graph (equivalently, the intersection graphs of the blocks in some other graph). 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.[18]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Cactus graph

View on Grokipedia
from Grokipedia
In graph theory, a cactus graph (also known as a cactus tree or Husimi tree) is a connected graph in which any two simple cycles share at most one vertex.[1] Equivalently, it is a connected graph in which every block (a maximal biconnected subgraph) is either a single edge or a cycle, and every edge belongs to at most one simple cycle.[2] Cactus graphs exhibit several characterizing properties that distinguish them from more general graph classes. Every cycle in a cactus graph is chordless, meaning no additional edges connect non-adjacent vertices within the cycle, and the circuit rank (the dimension of the cycle space) equals the total number of cycles in the graph.[1] They are always planar, allowing embedding in the plane without edge crossings, and every pseudotree—a connected graph containing at most one cycle—is a cactus graph.[1] Additionally, cactus graphs form a subclass of unit-distance graphs, where vertices can be represented as points in the plane with edges corresponding to unit lengths.[1] The number of unlabeled cactus graphs on n vertices follows the sequence 1, 1, 1, 2, 4, 9, 23, 63, ... for n = 1, 2, 3, ..., as cataloged in the Online Encyclopedia of Integer Sequences (OEIS A000083).[3] Not all graphs with chordless cycles are cacti; counterexamples include the theta graph (two vertices connected by three paths) and the Pasch graph.[1] Historically, cactus graphs were first studied as "Husimi trees" in the mid-20th century, named in honor of physicist Kodi Husimi, with foundational work by Frank Harary and George Eugene Uhlenbeck.[2] Their structure makes them particularly amenable to efficient algorithms for graph problems that are NP-hard in general graphs; for instance, computing all-pairs shortest paths requires O(n²) time, while finding minimum dominating sets, maximum independent sets, and various labeling and coloring problems can be solved in linear O(n) time on n-vertex cactus graphs.[2] Cactus graphs find applications in modeling real-world networks, such as telecommunications systems and material handling layouts, where the tree-like arrangement of cycles reflects hierarchical or modular connectivity with limited cycle overlaps.[2]

Definition and examples

Formal definition

A cactus graph is a connected graph in which any two simple cycles have at most one vertex in common.[4] Here, a simple cycle refers to a closed path in the graph with no repeated vertices except the starting and ending vertex. An equivalent formulation states that every edge in the graph belongs to at most one simple cycle.[4] Another equivalent definition describes a cactus graph as a connected graph in which every block—defined as a maximal biconnected subgraph or a bridge (a single edge whose removal increases the number of connected components)—is either a single edge or a cycle.[4][5] The connectivity requirement is essential; a disconnected graph satisfying the cycle condition would be a forest of cacti rather than a true cactus graph.[4]

Illustrative examples

A single cycle graph CnC_n for n≥3n \geq 3 serves as the simplest nontrivial example of a cactus graph, where the entire graph forms one cycle and every edge belongs to exactly that cycle.[6] Trees represent a degenerate case of cactus graphs, as they are connected acyclic structures with no cycles, making all blocks single edges.[6] A basic non-degenerate example beyond a single cycle is a chain of two cycles sharing exactly one vertex, such as a triangle and a quadrilateral connected at a common articulation point; visually, this appears as two loops emerging from a single junction, with no shared edges between the cycles.[6] The friendship graph, or windmill graph FnF_n, exemplifies a more complex cactus structure, consisting of nn triangles (3-cycles) all sharing a single central vertex while remaining otherwise disjoint; this forms a triangular cactus where the central vertex is the only intersection point among cycles.[7] Another illustrative variant includes a cycle with pendant trees attached at articulation points, such as a central cycle with tree branches extending from selected vertices; this maintains the cactus property as the trees introduce no new cycles and attachments occur at single vertices.[1] Graphs violating the cactus condition provide useful contrasts. The theta graph, formed by two vertices joined by three internally disjoint paths of positive length, is not a cactus because its three cycles share edges along the paths.[8] Similarly, the complete graph K4K_4 fails the definition, as its multiple 3-cycles share pairs of vertices and edges, creating blocks that are neither edges nor isolated cycles.[6]

Properties

Structural properties

A cactus graph is a connected graph in which every block is either an edge or a cycle, and any two blocks share at most one common vertex, which serves as an articulation point (cut vertex). This block structure ensures that the cycles are edge-disjoint and connected in a tree-like fashion via these articulation points, forming the block-cut tree of the graph.[9] Cactus graphs have treewidth at most 2, as their structure consists of cycles attached at single vertices without forming more complex minors that would increase the treewidth beyond that of series-parallel graphs.[10] A cactus graph is bipartite if and only if all of its cycles have even length. Since cycles in a cactus share no edges, the presence of any odd-length cycle introduces an odd circuit, preventing bipartition.[11] The domination number γ(G)\gamma(G) of a cactus graph GG of order n≥2n \geq 2 with k≥0k \geq 0 cycles and ℓ\ell leaves satisfies γ(G)≥13(n−ℓ+2(1−k))\gamma(G) \geq \frac{1}{3}(n - \ell + 2(1 - k)), with equality holding for specific constructions where the graph consists of cycles connected by paths and pendant edges in a controlled manner. More generally, cactus graphs can be classified such that γ(G)=13(n−ℓ+2(1−k)+m)\gamma(G) = \frac{1}{3}(n - \ell + 2(1 - k) + m) for some nonnegative integer mm, depending on the arrangement of blocks.[12]

Embedding properties

Cactus graphs exhibit favorable embedding properties due to their block structure, where every pair of cycles shares at most one vertex, facilitating straightforward planar representations. Specifically, they are a subclass of planar graphs, admitting an embedding in the plane without any edge crossings. This planarity arises from the tree-like arrangement of their blocks, which prevents the formation of configurations that would require crossings, such as those in non-planar graphs like K5K_5 or K3,3K_{3,3}.[11] A key embedding characteristic is outerplanarity: every cactus graph is outerplanar, meaning it possesses a planar embedding in which all vertices lie on the boundary of the outer face. In such an embedding, the cycles can be drawn as non-crossing boundaries attached at shared articulation points, ensuring no internal vertices and maintaining the outer face as a simple cycle encompassing all others. This property simplifies visualization and algorithmic processing, as the embedding aligns all vertices peripherally.[13] Cactus graphs also belong to the broader class of series-parallel graphs, which are graphs of treewidth at most 2 and can be constructed via series and parallel compositions starting from edges. Unlike the classical 2-terminal series-parallel graphs that often impose a maximum degree of 3, cactus graphs fit within this framework without such degree constraints, leveraging their cycle-block decomposition to achieve the required partial 2-tree structure. This inclusion underscores their partial order in the hierarchy of minor-closed graph families.[14] Regarding classical embedding invariants, the crossing number of any cactus graph is 0, reflecting its planarity and the absence of any unavoidable crossings in straight-line or polyline drawings. Similarly, the thickness—the minimum number of planar subgraphs whose union covers all edges—is 1, as the entire graph is already planar and requires no edge partitioning for embedding. These metrics highlight the simplicity of cactus embeddings compared to denser planar graphs.[11]

Variants

Triangular cacti

A triangular cactus is a connected cactus graph in which every block is a triangle, meaning all cycles are of length 3 and any two cycles share at most one vertex.[15] This structure ensures that the graph is outerplanar and consists solely of triangles connected at articulation points.[16] Prominent examples of triangular cacti include friendship graphs, where multiple triangles share a single common vertex, forming a windmill-like structure. More elaborate configurations arise in chains of triangles, such as triangular snakes, where triangles are sequentially attached by sharing individual vertices, creating a linear or tree-like backbone of cycles.[17] Triangular cacti exhibit a distinctive connectivity property: they remain connected after the removal of any matching, a set of pairwise non-adjacent edges. This resilience positions them as the minimal graphs (in terms of edges) that maintain connectivity under such removals for a fixed number of vertices.[17] The maximum triangular cactus subgraph of a given graph can be found in polynomial time via algorithms solving the graphic matroid parity problem, which models the selection of edge-disjoint triangles. The size (number of edges) of such a maximum triangular cactus is determined by a min-max formula: the minimum over partitions PP of the vertices into kk classes and QQ of the edges into mm classes of Φ(P,Q)=n−k+∑i=1m⌊(ui−1)/2⌋\Phi(P, Q) = n - k + \sum_{i=1}^m \lfloor (u_i - 1)/2 \rfloor, where nn is the number of vertices and uiu_i is the number of vertex classes incident to edges in class EiE_i.[18] This approach underpins approximation algorithms for the maximum planar subgraph problem; specifically, constructing a maximum triangular cactus followed by local optimization yields an approximation ratio of 4/94/9.[19]

Block cacti and other variants

Block cacti, also known as block-cactus graphs, generalize the class of standard cactus graphs by allowing blocks that are either cycles or complete graphs KnK_n for n≥2n \geq 2.[20] In such graphs, the structure remains tree-like in terms of block connectivity, with cut-vertices shared between blocks, but the inclusion of complete graph blocks permits larger cliques; however, cycles within a complete block may share edges, unlike in standard cacti. Blocks share only vertices, preventing edge overlaps between different blocks.[21] This extension broadens applications in areas like domatic partitioning and metric dimension computations, where the presence of cliques introduces additional structural complexity compared to cycle-only blocks.[22] Even cacti form a subclass of cacti where all cycles have even length, ensuring the graph is bipartite and free of odd cycles.[23] These graphs are particularly relevant in studies of Hamiltonian properties, such as prism-Hamiltonicity, where a spanning even cactus guarantees the existence of a Hamiltonian cycle in the prism over the graph.[24] The bipartite nature simplifies certain algorithmic tasks, like edge coloring, and connects to broader results on cycle decompositions in planar graphs.[25] Linear cacti, or linear cactus chains, are cacti whose block-cutpoint graph forms a path, meaning the cycles (or blocks) are arranged sequentially without branching.[26] This path-like structure eliminates tree-like ramifications, resulting in a chain of attached cycles or complete graphs connected at single vertices, which facilitates efficient computations for parameters like the Wiener index or labeling problems.[27] For instance, a linear cactus Pm(Kn)P_m(K_n) consists of mm identical complete graph blocks KnK_n linked by cut-vertices along a path.[28] Well-covered cacti are variants where every maximal independent set has the same cardinality, a property that holds uniformly across the graph's structure.[29] In the context of block-cacti, this well-coveredness is characterized by specific conditions on the blocks, such as cycles of even length or complete graphs satisfying independence number constraints, ensuring balanced independent set sizes without isolated vertices.[30] These graphs are useful in factorization and domination studies, as the uniform independence supports efficient matching and covering algorithms.[31] Unlike standard cacti, which restrict blocks to cycles or edges and thus limit clique sizes to at most 3, block cacti and their variants like linear or well-covered forms allow arbitrary complete blocks, increasing the maximum clique size while ensuring single-vertex sharing between blocks to prevent edge overlaps between different blocks.[32] This modification enhances the graphs' expressiveness for modeling clustered structures, though block-cacti are not necessarily outerplanar (unlike standard cacti) and have treewidth equal to the size of the largest clique minus one, which exceeds 2 for cliques larger than K3.

Characterizations and algorithms

Graph-theoretic characterizations

Cactus graphs admit several graph-theoretic characterizations based on forbidden subgraphs and minors that ensure the tree-like arrangement of their cycles, where cycles intersect at most at single vertices. A fundamental forbidden subgraph characterization is that a graph is a cactus if and only if it is connected and contains no subgraph in which two cycles share an edge. The minimal such forbidden subgraph is the diamond graph, denoted K4−eK_4 - e, consisting of four vertices with all edges present except one, forming two triangles sharing an edge.[33] This condition prevents any edge from belonging to multiple cycles, preserving the block structure where each biconnected component is either an edge or a single cycle. Additionally, cactus graphs forbid the theta subgraph θ\theta, formed by two vertices joined by three internally vertex-disjoint paths of positive length; this structure embeds two cycles sharing exactly two vertices but no edge, which would merge them into a single non-cyclic block.[34] In terms of minors, cactus graphs are precisely the connected graphs excluding the diamond graph K4−eK_4 - e as a minor. Any graph containing a diamond minor admits a model where branch sets correspond to vertices connected in a way that realizes two cycles sharing an edge after contractions and deletions, violating the cactus property. Cactus graphs are structurally analogous to block graphs, which are connected graphs whose blocks are complete cliques arranged in a tree-like fashion via the block-cut tree. In cacti, blocks are instead simple cycles (or edges), yielding a similar block-cut tree structure but with cyclic rather than clique blocks; this equivalence highlights cacti as "cyclic block graphs."[35]

Recognition and computational algorithms

Cactus graphs can be recognized in linear time by first computing the biconnected components of the graph using a depth-first search (DFS) traversal, which identifies the blocks in O(n + m) time, where n is the number of vertices and m is the number of edges. For each biconnected component, verify that it is either a single edge (K_2) or a simple cycle by checking if the number of edges equals the number of vertices and the component is 2-connected; if all blocks satisfy this condition and the graph is connected, it is a cactus.[36] This approach leverages the block structure to ensure no two cycles share an edge, as shared edges would merge blocks into non-cyclic structures. The block-cut tree, which represents the decomposition of the graph into blocks and cut vertices, can also be constructed in O(n + m) time via the same DFS-based method. Verification then proceeds by inspecting each block in the tree: edges correspond to trivial blocks, while cycles are confirmed by the equality of vertices and edges in non-trivial blocks, ensuring the tree-like articulation points connect them without violating the cactus property. This decomposition not only aids recognition but also facilitates further computations on the structure. Finding a maximum cactus subgraph— the subgraph with the maximum number of edges that is a cactus—is NP-hard in general graphs, as it corresponds to selecting edge-disjoint cycles connected at vertices while maximizing edges, reducible from known hard covering problems. However, when the input graph is outerplanar, the problem becomes polynomial-time solvable due to the bounded treewidth and structured embeddings allowing dynamic programming approaches. Dynamic programming on the block-cut tree enables efficient solutions for related problems in recognized cactus graphs. For instance, counting the number of cycles reduces to tallying the cycle blocks in the decomposition, achievable in linear time post-recognition. Similarly, computing a maximum matching involves propagating states (such as matched or unmatched vertices) across the tree, considering matching options within each cycle block (which can be solved via standard cycle matching in constant time per block) and combining them at cut vertices, yielding an overall linear-time algorithm.[37]

Applications

In optimization and facility location

Cactus graphs enable efficient solutions to several NP-hard optimization problems in facility location and related areas, owing to their decomposition into a block-cut tree—a tree structure where nodes represent cycles (blocks) or cut-vertices (articulation points), allowing dynamic programming techniques to reduce computations to tree-based optimization. This structure facilitates polynomial-time algorithms for problems intractable on general graphs. In facility location, the p-median problem, which seeks to place p uncapacitated facilities to minimize the total weighted distance to demand points, can be solved in polynomial time on cactus graphs via dynamic programming on the block tree. Specifically, for the connected variant—requiring the facilities to induce a connected subgraph—an O(n²p²) time algorithm decomposes the cactus into blocks and hinges (cut-vertices), computing optimal facility placements for subgraphs rooted at each articulation point by combining solutions from child blocks using programs for grafts, cycles, and hinges. This approach extends to the standard uncapacitated p-median by relaxing connectivity, leveraging the same DP framework to evaluate facility costs across the tree structure. A simpler case, the 1-median problem, admits a linear-time solution using parametric search on the block tree to find the optimal single facility location minimizing total distance. Covering problems, such as vertex cover and edge cover, are solvable in linear time on cactus graphs due to their outerplanar nature and bounded treewidth of at most 2, which permits dynamic programming on a linear-time computable tree decomposition. Vertex cover, requiring a minimum set of vertices incident to all edges, reduces to standard DP states tracking coverage in each bag of the decomposition. Edge cover, the minimum set of edges incident to all vertices, follows similarly, as it complements maximum matching, which is computable in linear time on outerplanar graphs via DP along a canonical ordering. For layout problems like minimum linear arrangement—seeking a vertex ordering minimizing the sum of absolute differences in positions over edges—the problem is solvable in polynomial time on simple cactus graphs. The algorithm orders cycles by non-decreasing length (treating bridges as infinite), producing a linear extension that respects this order and achieves optimality by exploiting the block structure where edges belong to at most one cycle.

In modeling and other fields

Cactus graphs find applications in modeling electrical circuits, particularly those with specific structural constraints that align with the graph's property of having edge-disjoint cycles. In nonlinear resistive circuits, the cactus structure facilitates the enumeration and analysis of solutions by representing loops as cycles that share at most one vertex, avoiding shared wires or edges that could complicate circuit behavior. This modeling approach has been used to study the existence, uniqueness, and multiplicity of equilibrium points in such circuits.[38] In comparative genomics, cactus graphs provide a framework for aligning and visualizing multiple related genomes, capturing evolutionary relationships such as gene duplications, losses, and rearrangements. The structure organizes genomic sequences into blocks connected at articulation points, allowing efficient representation of orthologous regions and nested substructures across species. Tools like the Cactus aligner leverage this to construct reference-free whole-genome alignments and pangenome graphs, enabling scalable analysis of hundreds of vertebrate genomes for phylogenetic inference and annotation.[39][40] Cactus graphs are utilized in reliability analysis of fault-tolerant networks, where their edge-disjoint cycle property ensures redundancy without overlapping failure paths. Cactus-based network topologies, such as those derived from generalized Petersen graphs or grid structures, are evaluated for subnetwork reliability under probabilistic fault models using techniques like the principle of inclusion-exclusion to derive approximations and upper bounds on connectivity. This makes them suitable for designing resilient communication systems with minimal single points of failure beyond articulation vertices.[41][42]

Open problems and conjectures

Rosa's conjecture

A graceful labeling of a graph GG with mm edges is a bijection f:V(G)∪E(G)→{0,1,…,m}f: V(G) \cup E(G) \to \{0, 1, \dots, m\} such that ff restricted to the vertices is injective, ff restricted to the edges is injective, and for every edge uvuv, ∣f(u)−f(v)∣=f(uv)|f(u) - f(v)| = f(uv).[43] In 1988, Alexander Rosa conjectured that every triangular cactus—a connected cactus graph in which every block is a triangle—with tt blocks is graceful if t≡0t \equiv 0 or 1(mod4)1 \pmod{4}, and nearly graceful otherwise.[43] A nearly graceful labeling satisfies the injectivity and difference conditions but allows the edge labels to use {1,2,…,m−1,m+1}\{1, 2, \dots, m-1, m+1\} instead of {1,2,…,m}\{1, 2, \dots, m\}, addressing cases where graceful labelings are impossible due to the parity of the sum of vertex degrees (which must equal the triangular number m(m+1)/2m(m+1)/2).[43] Rosa suggested using Skolem sequences to construct such labelings for triangular cacti.[43] Partial results support the conjecture for specific subclasses of triangular cacti. For instance, it has been proven for all triangular snakes (path-like triangular cacti) using almost graceful labelings, which are a strengthening of nearly graceful ones.[43] The conjecture also holds for friendship graphs, which are triangular cacti consisting of multiple triangles sharing a single common vertex.[44] In 2022, it was shown to hold for Dutch windmill graphs with three pendant triangles, settling the conjecture for this additional family.[45] For cases where t≡2t \equiv 2 or 3(mod4)3 \pmod{4}, counterexamples confirm that such triangular cacti are not graceful, but they admit nearly graceful labelings, aligning with Rosa's prediction.[43] As of 2025, Rosa's conjecture remains open for general triangular cacti, despite progress on subclasses and related labeling techniques like those involving Langford and hooked Skolem sequences.[43] Ongoing research in graph labeling surveys continues to explore extensions and potential proofs, but no general resolution has been achieved.[43]

Other unresolved questions

Generalizing cactus structures to hypergraphs, known as hypercacti, introduces several unresolved questions. For instance, characterizing hypergraphs where every pair of distinct vertices is joined by at most kk internally vertex-disjoint paths for k>2k > 2 remains open, as hypercacti solve this for k=2k=2. Similarly, the case of exactly kk such paths lacks a full characterization beyond hypertrees for k=1k=1. Alternative block-based definitions of hypercacti also require investigation to determine equivalences or relationships with path-based versions.[46] In variants like block cacti, determining exact formulas for the domination number continues to pose challenges despite progress on specific subclasses. While explicit formulas exist for domination numbers in equidistant m-cactus chains and weighted cacti, sharper bounds or classifications for general block cacti, including locating-total or eternal domination, are unresolved, with conjectures on efficiency beyond exponential time for bounded treewidth instances.[47][48][49]

History

Origins in Husimi trees

The concept of Husimi trees emerged in the context of statistical mechanics during the mid-20th century, particularly as tools for handling cluster expansions in models of interacting particles and spins. In 1950, physicist Kôdi Husimi introduced graph-theoretic structures to simplify the calculation of irreducible cluster integrals in Mayer's theory of non-ideal gases and related systems, where these integrals represent contributions from connected configurations of particles without redundant cycles. These structures approximated lattice models by focusing on connected graphs that avoid overlapping cycles, facilitating exact computations in infinite approximations while capturing essential correlations. Building on Husimi's ideas, Frank Harary and George E. Uhlenbeck formalized the notion in their 1953 paper, coining the term "Husimi trees" to describe connected graphs in which no edge belongs to more than one cycle. This definition extended the cycle-free Cayley trees—used in Bethe lattice approximations for phase transitions in the Ising model—by permitting limited cycles (such as triangles or quadrilaterals) to better mimic short-range loops in real lattices like the triangular or square grids. In this framework, pure Husimi trees were specialized cases, such as those composed solely of edges (reducing to trees) or solely of triangles (forming what would later be recognized as triangular cacti), enabling recursive enumeration for cluster sums. Harary and Uhlenbeck's work emphasized enumerative combinatorics, deriving functional equations via Pólya's methods to count rooted and unrooted Husimi trees characterized by cycle types (e.g., n2n_2 edges, n3n_3 triangles). These graphs provided a tractable approximation for cluster expansions in the Ising model, where exact solutions on infinite lattices are challenging, by balancing tree-like simplicity with cyclic realism to estimate critical temperatures and correlation lengths. Their block structure, where cycles share at most a single vertex, ensured the graphs remained tree-like at the level of blocks, aligning with the hierarchical approximations needed in statistical physics. Subsequent enumerations, such as those for mixed cycle types, further supported applications in virial coefficients and partition functions.

Evolution of terminology

The concept of what are now known as cactus graphs was initially termed "Husimi trees" by Frank Harary and George E. Uhlenbeck in their 1953 paper, where they defined such structures as connected graphs in which no edge lies on more than one cycle, honoring earlier work by K. Husimi on cluster integrals in statistical mechanics.[50] In the same work, they coined the term "cactus" specifically for the subclass of Husimi trees consisting solely of triangles, analogizing the branching, pad-like arrangement of triangles to the structure of a cactus plant.[50] This marked an early terminological distinction, with "cactus" evoking the plant's prickly, interconnected yet singly attached components. During the 1960s, the terminology began shifting toward "cacti" or "cactus graphs" for the broader class of Husimi trees, extending the plant-inspired name to encompass cycles of arbitrary lengths while retaining the shared-vertex condition that mimics articulated branches.[2] A pivotal milestone in this evolution was Alexander Rosa's 1967 paper on vertex valuations, which introduced "triangular cacti" as connected graphs whose blocks are exclusively 3-cycles, applying the term in the study of labelings that presaged graceful graph labelings and related conjectures.[51] By the 1980s, the term "cactus graph" gained formal standardization in graph theory, particularly through definitions emphasizing block structures. Researchers, including Arthur T. White, characterized cactus graphs as connected planar graphs in which every block is either a cycle or an edge—often termed block-cycle graphs—integrating the concept into topological and embedding studies.[1] This adoption solidified the nomenclature, distinguishing it from the earlier "Husimi trees" while highlighting structural properties like edge-disjoint cycles. Variants in naming persisted, with "cactus trees" frequently used interchangeably for the connected variants, underscoring their tree-like block-cutpoint graphs. The terminology also influenced outerplanar graph research, as cactus graphs form a key subclass where cycles can be embedded without crossings beyond the outer face.[1]

References

  1. Cactus Graph -- from Wolfram MathWorld
  2. [PDF] Cactus Graphs and Some Algorithms - arXiv
  3. [1408.4005] Cactus Graphs and Some Algorithms - arXiv
  4. Block -- from Wolfram MathWorld
  5. https://arxiv.org/pdf/1408.4005.pdf
  6. [PDF] On the (S2)-condition of edge rings for cactus graphs - KOPS
  7. [PDF] Graph Orientations and Signings That Are Saturated with Alternating ...
  8. [PDF] DOMINATION NUMBER AND (SIGNLESS LAPLACIAN) SPECTRAL ...
  9. [PDF] Computing the clique-width of Cactus graphs - CEUR-WS
  10. [PDF] Degree Realization by Bipartite Cactus Graphs - arXiv
  11. [PDF] A classification of cactus graphs according to their domination number
  12. Proper orientation of cacti - ScienceDirect.com
  13. The shortest connection game - ScienceDirect.com
  14. [PDF] arXiv:1403.1999v2 [math.CO] 2 Apr 2014
  15. [PDF] On the graceful conjecture for triangular cacti
  16. Cactus graph - EPFL Graph Search
  17. [PDF] Local Optimization Algorithms for Maximum Planar Subgraph - HAL
  18. [PDF] A Better Approximation Algorithm for Finding Planar Subgraphs
  19. The domatic number of block-cactus graphs - ScienceDirect.com
  20. A generalization of menger's theorem for certain block—cactus graphs
  21. [PDF] Metric dimension of antipodal and pendant-free block-cactus graphs
  22. A counterexample to prism-hamiltonicity of 3-connected planar graphs
  23. On the Hamiltonian Property Hierarchy of 3-Connected Planar Graphs
  24. [PDF] arXiv:1604.01282v1 [math.CO] 5 Apr 2016
  25. [PDF] Some new perspectives on distance two labeling
  26. [PDF] Extremal Polygonal Cacti for Wiener Index and Kirchhoff Index
  27. [PDF] Academic Journal of Applied Mathematical Sciences
  28. [PDF] A CHARACTERIZATION OF WELL COVERED BLOCK-CACTUS ...
  29. Well-covered graphs and factors - ScienceDirect.com
  30. Well-covered graphs and factors | Discrete Applied Mathematics
  31. (PDF) Enumeration of labeled block-cactus graphs - ResearchGate
  32. [PDF] Minor-Obstructions for Apex Sub-unicyclic Graphs - arXiv
  33. [PDF] The Hat Guessing Number of Cactus Graphs and Cycles - arXiv
  34. [PDF] Enumerations, Forbidden Subgraph Characterizations, and the Split ...
  35. The obnoxious center problem on weighted cactus graphs
  36. Algorithm to find a maximum 2-packing set in a cactus - ScienceDirect
  37. https://arxiv.org/abs/1601.03038
  38. Cactus Graphs for Genome Comparisons - SpringerLink
  39. Progressive Cactus is a multiple-genome aligner for the thousand ...
  40. Reliability Analysis of the Cactus-Based Networks Based on ...
  41. Reliability Analysis of the Cactus-Based Networks ... - ResearchGate
  42. [PDF] A Dynamic Survey of Graph Labeling
  43. [PDF] Alpha Labeling of Amalgamated Cycles
  44. A Tight Extremal Bound on the Lovász Cactus Number in Planar ...
  45. [PDF] An Optimal Algorithm to Find Maximum Independent Set and ... - camo
  46. Note A characterization of hypercacti - ScienceDirect.com
  47. DOMINATION NUMBERS OF m-CACTUS CHAINS - ResearchGate
  48. [PDF] weighted domination number of cactus graphs
  49. Locating‐Total Domination Number of Cacti Graphs - Wei - 2020
  50. ON THE NUMBER OF HUSIMI TREES, I 1. Introduction. - PNAS
  51. [PDF] A DYNAMIC SURVEY OF GRAPH LABELING 1. Introduction Most ...
User Avatar
No comments yet.