科研之友
微信
新浪微博
Facebook
分享链接
摘要
Let alpha(G), alpha'(G), K(G) and K'(G) denote the independence number, the matching number, connectivity and edge connectivity of a graph G, respectively. We determine the finite graph families F-l and F-2 such that each of the following holds. (i) If a connected graph G satisfies K'(G) >= alpha(G) - 1, then G has a spanning closed trail if and only if G is not contractible to a member of F-1. (ii) If K'(G) >= max{2, alpha(G) - 3}, then G has a spanning trail. This result is best possible. (iii) If a connected graph G satisfies K'(G) >= 3 and alpha'(G) <= 7, then G has a spanning closed trail if and only if G is not contractible to a member of F-2.
- 出版日期2017-2-6
