二部图平衡二部划分的上界

作者：陈涛; 张超; 颜超

来源：数学的实践与认识, 2019, 49(24): 167-171.

• 二部图
• 哈密尔顿圈
• 平衡二部划分

设G(V,E)是一个图,V1,V2是V的一个二部划分,当||V1|-|V2||≤1时,称V1,V2是V的一个平衡二部划分,用e(V1,V2)表示一条边的两个端点在不同划分里边的总数目.最小平衡二部划分是指寻找G(V,E)的一个平衡二部划分使得e(V1,V2)最小.研究了二部图和哈密尔顿二部图,得到它们的最小平衡二部划分的上界分别为[m/2]和(n+2)/2.

• 单位
  南京工业大学浦江学院