Longest Paths and Longest Cycles in Graphs with Large Degree Sums |
| |
| Authors: | Ingo Schiermeyer Meike Tewes |
| |
| Affiliation: | 1.Fakult?t für Mathematik und Informatik, TU Bergakademie Freiberg, 09596 Freiberg, Germany. e-mail: schiermeyer,DE;2.Fakult?t für Mathematik und Informatik, TU Bergakademie Freiberg, 09596 Freiberg, Germany. e-mail: tewes@math.tu-freiberg.de,DE |
| |
| Abstract: | Let p(G) and c(G) denote the number of vertices in a longest path and a longest cycle, respectively, of a finite, simple graph G. Define σ4(G)=min{d(x 1)+d(x 2)+ d(x 3)+d(x 4) | {x 1,…,x 4} is independent in G}. In this paper, the difference p(G)−c(G) is considered for 2-connected graphs G with σ4(G)≥|V(G)|+3. Among others, we show that p(G)−c(G)≤2 or every longest path in G is a dominating path. Received: August 28, 2000 Final version received: May 23, 2002 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
