Long paths with endpoints in given vertex-subsets of graphs
It is proved that if \(G\) is a connected graph of order \(n\) and \(t \geq 1\) a real number, and \(M\) is a set of vertices with \(| M| \geq n/t \geq 2\), then for any vertex \(v \in G\), there is a vertex \(u \in M\) with a path \(P\) from \(v\) to \(u\) such that \[ | P| \geq \min\left\{\frac{4}{4+t}d_G(u) + \frac{4-2t}{4+t}, \frac{2}{1+t}d_G(u) - 1, d_G(u) + 1 - t\right\}. \] It is also shown under the same conditions on \(G\), \(M\), \(n\) and \(t\) that either there is a cycle \(C\) containing all vertices of \(M\) or there exists a path \(P\) in \(G\) from vertices \(u_o\) to \(u_p\) in \(M\) such that \[ | P| \geq \min\left\{n, \frac{f(t)}{1+t(t)}(d_G(u_0) + d_G(u_p)) - 2t - \frac{6}{1+f(t)}\right\}. \] where \(f(t) = \min \{\frac{4}{t}, \frac{2}{t-1}\}\). These results are related to and motivated by the concept of cyclable sets of vertices.
- 2‐neighborhoods and hamiltonian conditions
- Cycles through prescribed vertices with large degree sum
- Cycles through specified vertices
- Graph theory
- Hamilton connected graphs
- scientific article; zbMATH DE number 3561382 (Why is no real title available?)
- scientific article; zbMATH DE number 568796 (Why is no real title available?)
- scientific article; zbMATH DE number 878896 (Why is no real title available?)
- Note on Hamilton Circuits
- On a conjecture of Woodall
- On maximal paths and circuits of graphs
- On the Erd�s-S�s conjecture
- On the Loebl-Koml�s-S�s conjecture
- Some Theorems on Abstract Graphs
- The Erdös-Sós conjecture for graphs of girth 5
This page was built for publication: Long paths with endpoints in given vertex-subsets of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q941396)
