Some forbidden subgraph conditions for a graph to have a \(k\)-contractible edge (Q1394805): Difference between revisions

An edge \(e\) of a \(k\)-connected graph \(G\) is said to be \(k\)-contractible if the graph resulting from the contraction of \(e\) remains \(k\)-connected. Denote by \(H_1\vee H_2\) the join of disjoint graphs \(H_1\) and \(H_2\), i.e., the graph obtained by adding to \(H_1\cup H_2\) edges joining all vertices in \(H_1\) to all vertices in \(H_2\). Let \(sH\) denote the graph consisting of \(s\) disjoint copies of a graph \(H\). Let \(k\) denote an integer \(\geq 5\). Two sufficient conditions are given for a \(k\)-connected graph \(G\) to contain a \(k\)-contractible edge, and they are shown to be sharp: (1) \(G\) contains neither \(K_2\vee sK_1\) nor \(K_1\vee tK_2\), where \(s\) and \(t\) are positive integers such that \(s(t-1)<k\). (2) \(G\) contains neither an edge-deleted \(K_5\) nor \(5K_1\vee P_3\) (where \(P_3\) denotes a path on three vertices) and the least valence is at least \(k+1\).