Pan-connectedness of graphs with large neighborhood unions |
| |
Authors: | Kewen Zhao |
| |
Affiliation: | (1) Department of Mathematics, Qiongzhou University, Wuzhishan City, Hainan, People’s Republic of China |
| |
Abstract: | Let G be a simple graph with n vertices. For any , let , and , and and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC 2(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC 2(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC 2(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected. |
| |
Keywords: | Pan-connected graphs Neighborhood unions |
本文献已被 SpringerLink 等数据库收录! |
|