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 |