哈密尔顿平面图最小平衡二部划分的上界

Upper bounds on minimum balanced bipartition of Hamilton plane graphs

设G(V,F)是一个图,V1,V2是V的一个二部划分,用e(V1,V2)表示一条边的两个端点在不同划分里边的总数目,当‖V1|-|V2‖≤1时,称V1,V2是V的一个平衡二部划分。最小平衡二部划分是指寻找G(V,F)的一个平衡二部划分使得e(V1,V2)最小。对于哈密尔顿平面图G(V,F),研究了当Perfect-内部三角形最大边函数值与最小边函数值之差为d时,e(V1,V2)最小值的上界与d之间的关系。

A balanced bipartition of a graph G(V,E)is a bipartition V1 and V2 of V(G)such that‖V1|-|V2‖≤1.The minimum balanced bipartition problem asks for a balanced bipartition minimizing e(V1,V2),where e(V1,V2)is the number of edges joining V1 and V2.In this paper,for Hamilton plane graphs,we study the relation between upper bounds on the minimum of e(V1,V2)and d,which is the difference between the maximum edge function value and the minimum edge function value of Perfect-inner triangle.