Premium
Paths extendable to cycles
Author(s) -
Parsons T. D.
Publication year - 1978
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/jgt.3190020408
Subject(s) - mathematics , combinatorics , path (computing) , integer (computer science) , graph , path length , set (abstract data type) , discrete mathematics , computer science , computer network , programming language
Let k be a positive integer, and S a nonempty set of positive integers. Suppose that G is a connected graph containing a path of length k , and that each path P of length k in G is contained in some cycle C ( P ) of length s ∈ S . We prove that every path of length less than k can be extended to a path of length k in G . This result answers conjectures of Entringer and Reid regarding when certain paths may be extended to cycles.