The connectivity of the SEE-graph and AEE-graph for the connected spanning \(k\)-edge subgraphs of a graph (Q1382830): Difference between revisions

For a connected graph \(G\) let \(T^*(G)\) be the graph whose vertices are the connected spanning \(k\)-edge subgraphs of \(G\). Two vertices \(F\) and \(H\) of \(T^*(G)\) are adjacent if \(| E(F) \Delta E(H) |=2\). \(T^*(G)\) is called the single edge-exchange transition graph (SEE-graph) of \(G\); see also \textit{F. Harary} and \textit{M. J. Planholt} [J. Graph Theory 13, No. 6, 703-712 (1989; Zbl 0699.05021)]. The author proves that the connectivity of \(T^*(G)\) is equal to the minimum degree of \(T^*(G)\). Similarly the adjacent edge-exchange transition graph (AEE-graph) \(T^*_a(G)\) of \(G\) is defined by: \(F\) and \(H\) are adjacent in \(T^*_a (G)\) if \(E(F)\Delta E(H) =\{e,f\}\) for some edges \(e\in F\) and \(f\in H\) which are adjacent in \(G\). Then the connectivity of \(T^*_a(G)\) is at least \(| E(G) |-k\).