Long cycles passing through a specified path in a graph. (English) Zbl 0919.05036

Hirohata, Kazuhide

J. Graph Theory 29, No. 3, 177-184 (1998).

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

Keywords:

independent set; cycle; length; path