Minimum 2-edge connected spanning subgraph of certain graphs. (English) Zbl 1326.05075
Summary: Given an undirected 2-edge connected graph, finding a minimum 2-edge connected spanning subgraph is NP-hard. We solve the problem for Butterfly network, Benes network, Honeycomb network and Sierpiński gasket graph.
MSC:
| 05C40 | Connectivity |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C35 | Extremal problems in graph theory |
