On Cycles in 3-Connected Graphs |
| |
Authors: | Hao Li |
| |
Institution: | (1) Laboratoire de Recherche en Informatique, URA 410, C.N.R.S. Bat. 490, Université de Paris-sud, 91405-Orsay cedex, France. e-mail: li@lri.fr, FR |
| |
Abstract: | Let G be a 3-connected graph of order n and S a subset of vertices. Denote by δ(S) the minimum degree (in G) of vertices of S. Then we prove that the circumference of G is at least min{|S|, 2δ(S)} if the degree sum of any four independent vertices of S is at least n+6. A cycle C is called S-maximum if there is no cycle C
′ with |C
′∩S|>|C∩S|. We also show that if ∑4
i=1
d(a
i)≥n+3+|⋂4
i=1
N(a
i)| for any four independent vertices a
1, a
2, a
3, a
4 in S, then G has an S-weak-dominating S-maximum cycle C, i.e. an S-maximum cycle such that every component in G−C contains at most one vertex in S.
Received: March 9, 1998 Revised: January 7, 1999 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|