Journal of Graph Theory Дискретная математика и комбинаторика
Vertex‐Based Localization of Erdős–Gallai Theorems for Paths and Cycles
Аннотация
ABSTRACT For a simple graph , let and denote the number of vertices and edges in , respectively. The Erdős–Gallai theorem for paths states that in a simple ‐free graph, , where denotes a path with length (i.e., with edges). In this paper, we generalize this result as follows: For each , let be the length of the longest path that contains . We show that The Erdős–Gallai theorem for cycles states that in a simple graph with circumference (i.e., the length of the longest cycle) at most , we have . We strengthen this result as follows: For each , let be the length of the longest cycle that contains , or 2 if is not part of any cycle. We prove that where denotes the circumference of . Furthermore, we characterize the class of extremal graphs that attain equality in these bounds.