Cactus graph

From Wikipedia, the free encyclopedia
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, every edge in such a graph belongs to at most one simple cycle. Equivalently, every block (maximal subgraph without a cut-vertex) is an edge or a cycle.

Properties

Cacti are outerplanar graphs. Every pseudotree is a cactus. A 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]

Algorithms and 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 cacti.[2][3]

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

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

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

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 Moitra & Leighton (2008) 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.[9]

History

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 (ja).[10][11] 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.[12]

References

  1. ↑ El-Mallah, Ehab; Colbourn, Charles J. (1988), "The complexity of some edge deletion problems", IEEE Transactions on Circuits and Systems 35 (3): 354–362, doi:10.1109/31.1748 
  2. ↑ Ben-Moshe, Boaz; Bhattacharya, Binay; Shi, Qiaosheng (2005), "Efficient algorithms for the weighted 2-center problem in a cactus graph", Algorithms and Computation, 16th Int. Symp., ISAAC 2005, Lecture Notes in Computer Science 3827, Springer-Verlag, pp. 693–703, doi:10.1007/11602613_70 
  3. ↑ 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, ISBN 0-7695-2397-8 
  4. ↑ Korneyenko, N. M. (1994), "Combinatorial algorithms on a class of graphs", Discrete Applied Mathematics 54 (2–3): 215–217, doi:10.1016/0166-218X(94)90022-1.  Translated from Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci., (1984) no. 3, pp. 109-111 (Russian)
  5. ↑ Nishi, Tetsuo; Chua, Leon O. (1986), "Topological proof of the Nielsen-Willson theorem", IEEE Transactions on Circuits and Systems 33 (4): 398–405, doi:10.1109/TCS.1986.1085935 
  6. ↑ Nishi, Tetsuo; Chua, Leon O. (1986), "Uniqueness of solution for nonlinear resistive circuits containing CCCS’s or VCVS’s whose controlling coefficients are finite", IEEE Transactions on Circuits and Systems 33 (4): 381–397, doi:10.1109/TCS.1986.1085934 
  7. ↑ 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 
  8. ↑ Paten, Benedict; Diekhans, Mark; Earl, Dent; St. John, John; Ma, Jian; Suh, Bernard; Haussler, David (2010), Cactus Graphs for Genome Comparisons, "Research in Computational Molecular Biology", Lecture Notes in Computer Science, Lecture Notes in Computer Science 6044: 410–425, doi:10.1007/978-3-642-12683-3_27, ISBN 978-3-642-12682-6 
  9. ↑ Leighton, Tom; Moitra, Ankur (2010), "Some Results on Greedy Embeddings in Metric Spaces", Discrete & Computational Geometry 44 (3): 686–705, doi:10.1007/s00454-009-9227-6 .
  10. ↑ Harary, Frank; Uhlenbeck, George E. (1953), "On the number of Husimi trees, I", Proceedings of the National Academy of Sciences 39 (4): 315–322, doi:10.1073/pnas.39.4.315, MR 0053893 
  11. ↑ Husimi, Kodi (1950), "Note on Mayers' theory of cluster integrals", Journal of Chemical Physics 18 (5): 682–684, doi:10.1063/1.1747725, MR 0038903 
  12. ↑ See, e.g., MR 0659742, 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.

External links

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.