On homotopy of connected graphs having the same degree function (Q5931418): Difference between revisions

Let \(G\) be a simple graph with complement \(G'\). Suppose that \(e_1=x_1y_1\) and \(e_2=x_2y_2\) are edges of \(G\) while \(e_x=x_1x_2\) and \(e_y=y_1y_2\) are edges of \(G'\). The replacement in \(G\) of \(\{e_1,e_2\}\) by \(\{e_x,e_y\}\) is called a switch. The switch is a \(II\)-, \(\Pi\)-, or \(O\)-switch according to whether neither, exactly one, or both of \(x_1y_2\) and \(x_2y_1\) are edges of \(G\), respectively. If \(G\) and \(H\) are two simple graphs with the same vertex set, write \(G=^d H\) if every vertex has the same valence in each of the two graphs. For \(X\in\{II,\Pi,O\}\), we say that \(G\) is \(X\)-equivalent to \(H\) if there exists a sequence of simple graphs \(G=F_1,\dots,F_k=H\) such that \(F_{i+1}\) is obtained from \(F_i\) by a single \(X\)-switch for \(1\leq i\leq k-1\). Theorem 3.2: If \(G\) and \(H\) are trees such that \(G =^d H\), then they are \(\Pi\)-equivalent. Theorem 4.10: If \(G\) and \(H\) are simple graphs such that \(G =^d H\) having cycle spaces of dimension \(\leq 2\), and if they are not isomorphic to the graph consisting of a pair of 3-circuits with one common vertex, then there exists a sequence of simple graphs \(G=R_1,\dots,R_k=H\) such that \(R_{i+1}\) is obtained from \(R_i\) \((1\leq i\leq k-1)\) by a \(\Pi\)- or a \(O\)-switch and each graph \(R_i\) also has dimension \(\leq 2\). Theorem 5.1: If \(G\) and \(H\) are simple graphs such that \(G =^d H\) having the same number \(c\) of components, then there exists a sequence of simple graphs \(G=F_1,\dots,F_k=H\) such that \(F_{i+1}\) is obtained from \(F_i\) \((1\leq i\leq k-1)\) by a single switch and each graph \(F_i\) has \(\leq c\) components. All proofs provide polynomial time algorithms for finding an appropriate sequence of switches.