Fan-type theorem for path-connectivity

✍ Scribed by Zhiquan Hu; Feng Tian; Bing Wei; Yoshimi Egawa; Kazuhide Hirohata

• Publisher: John Wiley and Sons
• Year: 2002
• Tongue: English
• Weight: 165 KB
• Volume: 39
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.10028

✦ Synopsis

Abstract

For a connected noncomplete graph G, let μ(G):=min{max {d~G~(u), d~G~(v)}:d~G~(u, v)=2}. A well‐known theorem of Fan says that every 2‐connected noncomplete graph has a cycle of length at least min{|V(G)|, 2μ(G)}. In this paper, we prove the following Fan‐type theorem: if G is a 3‐connected noncomplete graph, then each pair of distinct vertices of G is joined by a path of length at least min{|V(G)|−1, 2μ(G)−2}. As consequences, we have: (i) if G is a 3‐connected noncomplete graph with $\mu(G)> {{|V(G)|}\over {2}}$, then G is Hamilton‐connected; (ii) if G is a (s+2)‐connected noncomplete graph, where s≥1 is an integer, then through each path of length s of G there passes a cycle of length≥min{|V(G)|, 2μ(G)−s}. Several results known before are generalized and a conjecture of Enomoto, Hirohata, and Ota is proved. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 265–282, 2002 DOI 10.1002/jgt.10028