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
Keywords:
independent set; cycle; length; path
Full Text: