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

Upper bounds on minimum balanced bipartition of Hamilton plane graphs

作　　者：陈涛[1] CHEN Tao(Nanjing Tech University Pujiang Institute,Nanjing 211112,China)

机构地区：[1]南京工业大学浦江学院,南京211112

出　　处：《运筹学学报》2020年第3期161-166,共6页Operations Research Transactions

基　　金：江苏省高校自然科学基金(No.18KJB110014)。

摘　　要：设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.

关 键 词：平面图 哈密尔顿圈 平衡二部划分 

分 类 号：O157.5[理学—数学]