偶图的圈

Circles in Bipartite Graphs

Jackson（1981）对一类特殊的偶图给出了其圈长的估计：设G是以（A，B）为顶点二分划的偶图，k=min｛d（u）｜u∈A）｝≥2，2≤｜A｜≤k，｜B｜≤2k－2，则最长圈C（G）＝2｜A｜．这里对上述结果进行了改进得到下述定理：设G是以（A，B）为顶点二分划的偶图，d（x*）＝min｛d（u）｜u∈A｝＝k≥2，λ＝min｛d（u）｜u∈A＼｛x*｝≥k，2≤｜A｜≤λ，｜B｜≤λ＋k－2，则C（G）＝2｜A｜．容易验证Jackson的结果是这个定理的一个特例．

Jackson (1981) gave an estimation of tbe circumferences of some special kinds of bipartite graphs:Let G be a bipartite graph with bipartition (A, B), k=min {d (u)|u∈A)} ≥ 2，≤ |A |≤k, |B|≤2k - 2, then the longest circles C (G) = 2 |A |. By improving this result the next theorem is proved: Let G be a bipartite graph with bipartition (A, B), d (x* ) =min {d (u)|u∈A} =k≥2, λ=min {d (u)|u∈A\ {x* } }≥k, 2≤|A|≤λ, |B|≤λ+k-2. then C (G) =2|A|. It is easy to prove that Jackson's result is a special example of this theorem.