On the Existence of a Long Path Between Specified Vertices in a 2-Connected Graph |
| |
Authors: | Kazuhide Hirohata |
| |
Institution: | (1) Department of Mathematics, Keio University, 3-14-1 Hiyoshi, Kohoku-ku, Yokohama 223, Japan. e-mail: hirohata@comb.math.keio.ac.jp, JP |
| |
Abstract: | Let G be a 2-connected graph with maximum degree Δ (G)≥d, and let x and y be distinct vertices of G. Let W be a subset of V(G)−{x, y} with cardinality at most d−1. Suppose that max{d
G(u), d
G(v)}≥d for every pair of vertices u and v in V(G)−({x, y}∪W) with d
G(u,v)=2. Then x and y are connected by a path of length at least d−|W|.
Received: February 5, 1998 Revised: April 13, 1998 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|