Cactus graph
A cactus graph (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, every edge in such a graph may belong to at most one cycle.
Cactus graphs 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 Kodi Husimi.[1][2] The same Harary–Uhlenbeck paper reserves the name "cactus" for graphs of this type in which every cycle is a triangle. However, the Husimi tree name also came to refer to graphs in which every biconnected component is a complete graph, and (perhaps due to this confusion) fell into disuse, while the name "cactus" came to mean the more general class of graph.[3]
Properties
Cactus graphs are outerplanar graphs. Every pseudotree is a cactus graph. A graph is a cactus graph if and only if every biconnected component is either a simple cycle or a single edge.
The family of graphs in which each connected 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.[4]
Applications
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 cactus graphs.[5][6]
They also represent electrical circuits that provably have useful properties. An early application of the cactus graphs was associated with the representation of op-amps by means of cactus graphs.[7][8][9]
References
- ^ Harary, F.; Uhlenbeck, G. (1953), "On the number of Husimi trees, I", Proceedings of the National Academy of Sciences, 39: 315–322, doi:10.1073/pnas.39.4.315, MR0053893.
- ^ Husimi, Kodi (1950), "Note on Mayers' theory of cluster integrals", Journal of Chemical Physics, 18: 682–684, doi:10.1063/1.1747725, MR0038903.
- ^ See, e.g., MR0659742, a 1983 review by Robert E. Jamison of a paper using the other definition, which attributes the ambiguity to an error in a book by Behzad and Chartrand.
- ^ El-Mallah, Ehab; Colbourn, Charles L. (1988), "The complexity of some edge deletion problems", IEEE Transactions on Circuits and Systems, 35 (3): 354–362, doi:10.1109/31.1748.
- ^ Ben-Moshe, Boaz; Bhattacharya, Binay; Shi, Qiaosheng (2005), "Efficient algorithms for the weighted 2-center problem in a cactus graph" (PDF), Algorithms and Computation, 16th Int. Symp., ISAAC 2005, Lecture Notes in Computer Science, vol. 3827, Springer-Verlag, pp. 693–703.
- ^ Zmazek, Blaz; Zerovnik, Janez (2005), "Estimating the traffic on weighted cactus networks in linear time", Ninth International Conference on Information Visualisation (IV'05), pp. 536–541, doi:10.1109/IV.2005.48.
- ^ Nishi, Tetsuo; Chua, Leon O. (1986), "Topological proof of the Nielsen-Willson theorem", IEEE Transactions on Circuits and Systems, CAS-33 (4): 398–405.
- ^ Nishi, Tetsuo; Chua, Leon O. (1986), "Uniqueness of solution for nonlinear resisitive circuits containing CCCS's or VCVS's whose controlling coefficients are finite", IEEE Transactions on Circuits and Systems, CAS-33 (4): 381–397.
- ^ Nishi, Tetsuo (1991), "On the number of solutions of a class of nonlinear resistive circuit", Proceedings of the IEEE International Symposium on Circuits and Systems, Singapore, pp. pages 766–769
{{citation}}:|pages=has extra text (help).