Long paths and cycles through specified vertices in \(k\)-connected graphs. (Q2715999)

Paths in graphs are studied. An \((x,Y,z;m)\)-path is a path connecting the vertices \(x,z\), passing through all vertices of \(Y\) and having the length \(m\). Two theorems are proved.NEWLINENEWLINETheorem 1. Let \(k\) and \(d\) be integers with \(d\geq k\geq 4\), and let \(G\) be a \(k\)-connected graph with \(| V(G)| \geq 2d-1\). Let \(x\) and \(z\) be distinct vertices of \(G\), and let \(Y\) be a subset of \(V(G) - \{x,z\}\) with cardinality at most \(k-1\). Suppose that \(\max \{d_G(u), d_G(v)\}\geq d\) for any nonadjacent distinct vertices \(u\) and \(v\) in \(V(G) - \{x,z\}\). Then \(G\) contains an \((x,Y,z;2d-2)\)-path.NEWLINENEWLINETheorem 2 is very similar and concerns the existence of a certain cycle.