| 不含H子图的图上的最大割下界 |
| |
| 引用本文： | 林晶. 不含H子图的图上的最大割下界[J]. 福建工程学院学报, 2020, 0(1): 87-91. DOI: 10.3969/j.issn.1672-4348.2020.01.016 |
| |
| 作者姓名： | 林晶 |
| |
| 作者单位： | 福建工程学院数理学院 |
| |
| 摘 要： | 文章证明了对于由单个顶点连接任意t个点不交的完全二部图K2，s的所有顶点构成的图H，有f(m，H)≥m2+Ω(m(2t+1)/(3t+1))；特别当t=1时，该猜想近似成立。还证明了对于轮图W2k，有f(m，W2k)≥m2+Ω(m(2k+2)/(3k+2))。
|
| 关 键 词： | 最大割 不含H子图 下界 |
Lower bounds on maximum cuts in H-free graphs |
| |
| LIN Jing. Lower bounds on maximum cuts in H-free graphs[J]. ournal of Fujian University of Technology, 2020, 0(1): 87-91. DOI: 10.3969/j.issn.1672-4348.2020.01.016 |
| |
| Authors: | LIN Jing |
| |
| Affiliation: | Mathematics and Physics Institute, Fujian University of Technology |
| |
| Abstract: | This paper shows that, for any graph H obtained by connecting a single vertex to all vertices of the union of t vertex-disjoint K2,s, f（m,H）≥〖SX(〗m〖〗2〖SX)〗+Ω（m(2t+1)/(3t+1)）. In particular, the conjecture is confirmed asymptotically for t=1. It is also proved that for any wheel graph W2k, f（m,W2k）≥〖SX(〗m〖〗2〖SX)〗+Ω（m(2k+2)/(3k+2)） |
| |
| Keywords: | maximum cut H-free graphs lower bound |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《福建工程学院学报》浏览原始摘要信息 |
|
点击此处可从《福建工程学院学报》下载免费的PDF全文 |
