不含某些子图的k连通图中的k可收缩边

最近Ando等证明了在一个$k$($kgeq 5$ 是一个整数) 连通图 $G$ 中,如果 $delta(G)geq k+1$, 并且 $G$ 中既不含 $K^{-}_{5}$,也不含 $5K_{1}+P_{3}$, 则$G$ 中含有一条 $k$ 可收缩边.对此进行了推广,证明了在一个$k$连通图$G$中,如果 $delta(G)geq k+1$,并且 $G$ 中既不含$K_{2}+(lfloorfrac{k-1}{2}rfloor K_{1}cup P_{3})$,也不含 $tK_{1}+P_{3}$ ($k,t$都是整数,且$tgeq 3$),则当 $kgeq 4t-7$ 时, $G$ 中含有一条 $k$ 可收缩边.

k-CONTRACTIBLE EDGES IN k-CONNECTED GRAPHS NOT CONTAINING SOME SPECIFIED GRAPHS

Recently, Ando et al. proved that in a $k$- ($kgeq 5$ is an integer) connected graph $G$, if $delta (G)geq k+1$, and $G$ contains neither $K^{-}_{5}$, nor $5K_{1}+P_{3}$, then $G$ has a $k$ contractible edge. In this paper, the result is generalized, and it is proved that in a $k$- conneted graph $G$, if $delta (G)geq k+1$, and $G$ contains neither $K_{2}+(lfloorfrac{k-1}{2}rfloor K_{1}cup P_{3})$, nor $tK_{1}+P_{3}$ (both $k$ and $t$ are integers, and $tgeq 3$) and if $kgeq 4t-7$, then $G$ has a $k$ contractible edge.