基于星结构对哈密尔顿平面图平衡二部划分的研究

Study on Balanced Bipartitions of Hamilton Plane Graphs based on Star Structure

平衡二部划分问题是图论的一个重要研究课题,本文研究了哈密尔顿平面图最小平衡二部划分上界的问题,主要证明了:哈密尔顿平面图G(V,E),|V|=n,1)若G(V,E)含有normal子图,则G(V,E)至少含有一个连续平衡二部划分V1,V2使得e(V1,V2)≤n;2)若G(V,E)含有h-normal子图,则G(V,E)至少含有一个平衡二部划分V1,V2使得e(V1,V2)≤n.

Balanced bipartitions is an important topic in Graph Theory.In this paper,we study upper bounds on minimum bisections of Hamilton plane graphs and prove:Let G(V,E)be Hamilton plane graph,|V|=n,(1)if G(V,E)contains normal subgraphs,G(V,E)admits a consecutive bisection V1,V2 such that e(V1,V2)≤n;(2)if G(V,E)admits h-normal subgraphs,G(V,E)admits a bisection V1,V2 such that e(V1,V2)<n.