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

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

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

机构地区：[1]南京工业大学浦江学院基础教学部,江苏南京211112

出　　处：《数学的实践与认识》2020年第23期176-184,共9页Mathematics in Practice and Theory

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

摘　　要：平衡二部划分问题是图论的一个重要研究课题,本文研究了哈密尔顿平面图最小平衡二部划分上界的问题,主要证明了:哈密尔顿平面图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.

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

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