On cycles through prescribed vertices in weakly separable graphs (Q761466): Difference between revisions

Let G be an undirected graph and T a subset of V(G). A cycle C of G is called a T-cycle iff \(T\subseteq V(C)\). A special pair (X,Y), where \(X\subseteq V(C)-T\) and \(Y\subseteq E(G-X-T)\) is called a T-separator. In k-connected as well as in weakly separable k-connected graphs G (it means vertex connectivity) and in k-polytopal graphs G (which are isomorphic images of 1-skeletons of k-dimensional convex polytopes) the authors investigate the subsets T of V(G) with the property: G has a T-cycle iff G has no T-separator. On the other hand there are constructed such k-connected graphs H with the set \(T\subset V(H)\) that H has neither a T-cycle nor a T-separator. Further it is shown, that any \(k+2\) vertices of a weakly separable k- connected graph (k\(\geq 3)\) and of a k-polytopal graph (k\(\geq 2)\) lie on a common cycle. An analogous assertion is proved for the Plummer's \(C(m^+,n^-)\)-graphs. Any \(m+n\) vertices of a \(C(m^+,n^-)\)-graph lie on a common cycle \((2<m<5)\).