图的k部划分的一个注记  

A Note on k-Partitions of Graphs

作　　者：刘木伙[1] 许宝刚[2] 

机构地区：[1]华南农业大学应用数学系,广州510642 [2]南京师范大学数学科学学院数学研究所,南京210023

出　　处：《数学学报（中文版）》2016年第2期247-252,共6页Acta Mathematica Sinica：Chinese Series

基　　金：国家自然科学基金资助项目(11331003;11171160;11201156);国家留学基金资助项目;江苏省自然科学基金(BK20131357);江苏高校优势学科建设工程资助项目

摘　　要：设k≥2是一个整数。本文证明了任意有m条边的图都存在一个顶点的划分V_1,V_2…,V_k,使得e(V_1,V_2…,V_k)≥k-1/k m+k-1/2k((2m+1/4)~1/2-1/2)-(k-2)~2/8k,且max{e(V_i):1≤i≤k}≤m/k^2+(k-1)/2k^2((2m+1/4)~1/2-1/2+3/8-7k-4/8k^2.我们的结果改进了[Fan G.,Hou J.,Zeng Q.,A bound for judicious k-partitions of graphs,Discrete Appl.Math.,2014,179:86—99]的主要结论.Suppose thatk≥2 is an integer. In this note, we prove that every graphwith m edges admits a partition V1, V2,... Vksuch that e（V_1,V_2…,V_k）≥k-1/k m＋k-1/2k（（2m＋1/4）~1/2-1/2）-（k-2）~2/8k This improves the main result of [Fan G., Hou J., Zeng Q., A bound forjudicious k-partitions of graphs, Discrete Appl. Math., 2014, 179： 86-99].

关 键 词：图的划分 界 图 

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