Path extendability of claw-free graphs |
| |
Authors: | Yu Sheng Jianglu Wang Yongjin Zhu |
| |
Institution: | a Institute of Systems Science, Chinese Academy of Sciences, Beijing 100080, China b Department of Mathematics, Shangdong Normal University, Jinan 250014, China c Department of Mathematics, University of Mississippi, MS 38677, USA |
| |
Abstract: | Let G be a connected, locally connected, claw-free graph of order n and x,y be two vertices of G. In this paper, we prove that if for any 2-cut S of G, S∩{x,y}=∅, then each (x,y)-path of length less than n-1 in G is extendable, that is, for any path P joining x and y of length h(<n-1), there exists a path P′ in G joining x and y such that V(P)⊂V(P′) and |P′|=h+1. This generalizes several related results known before. |
| |
Keywords: | Claw-free graphs Detour Locally connected Path extendable |
本文献已被 ScienceDirect 等数据库收录! |
|