关于3-连通图最长圈的注(英文)

A Note on the Circumference of 3-connected Graphs

设C是3 -连通图G的一个最长圈,H是G -V(C)的一个分支满足|H |≥3 .文献[4]在给H附加一些条件后,证明|C|≥2 d(u) +2 d(v) -5 ,并且不等式严格成立除非G属于某些例外图类,这里u,v是G中两个不相邻的顶点.本文给出了上述例外图类的精确刻划.

Let C be a longest cycle in a 3-connected graph G and let H be a component of G-C such that |H|≥3. In , subject to some condition on H, it is shown that |C|≥ 2d(u)+2d(v)-5 with strict inequality unless G belongs to some exceptional class of graphs, where u,v are non-adjacent vertices. In this thesis, we supply an explicit characterization of the exceptional class of graphs for the above estimate of |C|.