Maximum Size of a Graph with Given Fractional Matching Number

  • Tianlong Ma
  • Jianguo Qian
  • Chao Shi

Abstract

For three integers $n,k,d$, we determine the maximum size of a graph on $n$ vertices with fractional matching number $k$ and maximum degree at most $d$. As a consequence, we obtain the maximum size of a graph with given number of vertices and fractional matching number. This partially confirms a conjecture proposed by Alon et al. on the maximum size of $r$-uniform hypergraph with a fractional matching number for the special case when $r=2$.

Published
2022-09-09
Article Number
P3.55