| 图的k部划分的一个注记 |
| |
| 引用本文： | 刘木伙,许宝刚.图的k部划分的一个注记[J].数学学报,2016,59(2):247-252. |
| |
| 作者姓名： | 刘木伙 许宝刚 |
| |
| 作者单位： | 1.华南农业大学应用数学系 广州 510642;2.南京师范大学数学科学学院数学研究所 南京 210023 |
| |
| 基金项目： | 国家自然科学基金资助项目(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]的主要结论.
|
| 关 键 词： | 图的划分 界 图 |
A Note on k-Partitions of Graphs |
| |
| Mu Huo LIU,Bao Gang XU.A Note on k-Partitions of Graphs[J].Acta Mathematica Sinica,2016,59(2):247-252. |
| |
| Authors: | Mu Huo LIU Bao Gang XU |
| |
| Institution: | 1.Department of Applied Mathematics, South China Agricultural University, Guangzhou 510642, P. R. China;2.Institute of Mathematics, School of Mathematical Science, Nanjing Normal University, Nanjing 210023, P. R. China |
| |
| Abstract: | Suppose that k ≥ 2 is an integer. In this note, we prove that every graph with m edges admits a partition V1, V2, . . ., Vk such that e(V1, V2, . . ., Vk) ≥ (k-1)/k·m + (k-1)/(2k)·(√2m + 1/4-1/2)-((k-2)2)/(8k), and max{e(Vi) : 1 ≤ i ≤ k} ≤ m/(k2) + (k-1)/(2k2) (√2m + 1/4-1/2)+ 3/8-(7k-4)/(8k2). This improves the main result of Fan G., Hou J., Zeng Q., A bound for judicious k-partitions of graphs, Discrete Appl. Math., 2014, 179: 86-99]. |
| |
| Keywords: | partition of graph bound graph |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《数学学报》浏览原始摘要信息 |
| 点击此处可从《数学学报》下载免费的PDF全文 |
|
