Tight lower bounds on the matching number in a graph with given maximum degree
Tight lower bounds on the matching number in a graph with given maximum degree
复制标题
给定最大度数的图中匹配数的严格下界
DOI：
10.1002/jgt.22244
复制
发表时间：
2016
影响因子：
0.9
通讯作者：
Anders Yeo
中科院分区：
文献类型：
--
作者：
Michael A. Henning;Anders Yeo
设k≥3。本文证明了n阶图G的匹配数α′（G）的三个界，其中n阶图的大小为m，最大度不超过k.若k是奇数，则α′（G）≥（k− 1 k（k2−3））n+（k2−k−2k（k2−3））m-k − 1 k（k2−3）。若k是偶数，则α′（G）≥nk（k+1）+n +1− 1 k。若k是偶数，则α′（G）≥（k+2k 2 +k+2）m−（k− 2k 2 +k+2）n−k+2k 2 +k+2。
Let k≥3 . We prove the following three bounds for the matching number, α′(G) , of a graph, G, of order n size m and maximum degree at most k. If k is odd, then α′(G)≥(k−1k(k2−3))n+(k2−k−2k(k2−3))m−k−1k(k2−3) . If k is even, then α′(G)≥nk(k+1)+mk+1−1k . If k is even, then α′(G)≥(k+2k2+k+2)m−(k−2k2+k+2)n−k+2k2+k+2 .