Premium
Long cycles passing through a specified path in a graph
Author(s) -
Hirohata Kazuhide
Publication year - 1998
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199811)29:3<177::aid-jgt5>3.0.co;2-n
Subject(s) - combinatorics , mathematics , graph , path graph , path (computing) , discrete mathematics , bound graph , graph power , line graph , computer science , programming language
For a graph G and an integer k ≥ 1, let ς k ( G ) = $min \{\sum ^{k}_{i=1}$ d G ( v i ): { v 1 , …, v k } is an independent set of vertices in G }. Enomoto proved the following theorem. Let s ≥ 1 and let G be a ( s + 2)‐connected graph. Then G has a cycle of length ≥ min{| V ( G )|, ς 2 ( G ) − s } passing through any path of length s . We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a ( k + s − 1)‐connected graph. Then G has a cycle of length ≥ min{| V ( G )|, $\frac{2}{k}\sigma_{k}(G)$ − s } passing through any path of length s . © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998