×

zbMATH — the first resource for mathematics

Long cycles passing through a specified path in a graph. (English) Zbl 0919.05036
Summary: For a graph \(G\) and an integer \(k\geq 1\), let \(\sigma_k(G)= \min\{\sum^k_{i= 1} d_G(v_i): \{v_1,\dots, v_k\}\) is an independent set of vertices in \(G\}\). Enomoto proved the following theorem. Let \(s\geq 1\) and let \(G\) be a \((s+2)\)-connected graph. Then \(G\) has a cycle of length \(\geq\min\{| V(G)|,\sigma_2(G)- s\}\) through any path of length \(s\). We generalize this result as follows. Let \(k\geq 3\) and \(s\geq 1\) and let \(G\) be a \((k+s-1)\)-connected graph. Then \(G\) has a cycle of length \(\geq\min\{| V(G)|,{2\over k}\sigma_k(G)- s\}\) passing through any path of length \(s\).

MSC:
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI