On fixed edges and edge-reconstruction of series-parallel networks (Q5943041)

An edge \(e\) of a graph \(G\) is said to be a fixed edge of \(G\) if \(G-e+e' \cong G\) implies \(e'=e\) and a forced edge if \(G-e+e'\) is an edge-reconstruction of \(G\) implies \(e'=e\). A graph can be shown to be edge-reconstructible by showing a fixed edge of the graph to be a forced edge. A graph with no fixed edge is called a 1-edge free graph. A configuration is a special type of vertex-weighted graph and a graph \(G\) is said to contain a configuration \(C\) if \(C\) can be embedded as a vertex induced subgraph of \(G\) in a specified way. A configuration \(C\) is said to be excludable for a class \(\mathcal G\) of 1-edge free graphsf, if every graph in \(\mathcal G\) containing \(C\) has a fixed edge. The authors describe four collections of configurations and prove that they are excludable for 1-edge free 2-connected graphs. A graph is a series-parallel graph if it does not contain any subgraph homeomorphic to \(K_4\). A series-parallel network is a 2-connected series-parallel graph. The authors use the excluded configuration method to prove the following theorems: (1) If a graph is a 1-edge free series-parallel network, then it is isomorphic to either \(P_3 \vee K_1\) or \(P_4 \vee K_1\). (2) Every series-parallel network is edge-reconstructible. They propose to pursue the same techniques to characterize 1-edge free series-parallel graphs and to prove that all series-parallel graphs are edge-reconstructible.