Maximum size of a graph with given fractional matching number
For an integer \(r \geq 2\), an \(r\)-uniform hypergraph is a pair \(H=(V(H),E(H))\) with vertex set \(V(H)\) and edge set \(E(H) \subseteq \genfrac{(}{)}{0pt}{1}{V(H)}{r}\). The matching number of \(H\) is the size of a maximum matching in \(H\). A fractional matching of an \(r\)-uniform hypergraph \(H\) is a function \(f\) assigning each edge with a real number in \([0, 1]\) so that \( \sum_{e \in \Gamma(v)} {f(e)} \leq 1\) for each \(v \in V (H)\), where \(\Gamma(v)\) is the set of edges incident with \(v\) in \(H\). The fractional matching number of \(H\) is the maximum value of \(\sum_{e \in E(H)} {f(e)} \) over all fractional matchings \(f\). In this paper, for three integers \(n\), \(k\), and \(d\), the authors determine the maximum size of a graph on \(n\) vertices with fractional matching number \(k\) and maximum degree at most \(d\). As a consequence, they obtain the maximum size of a graph with a given number of vertices and a fractional matching number. This partially confirms a conjecture proposed by \textit{N. Alon} et al. [J. Comb. Theory, Ser. A 119, No. 6, 1200--1215 (2012; Zbl 1242.05189)] on the maximum size of \(r\)-uniform hypergraph with a fractional matching number for the special case when \(r = 2\).
- A note on exact minimum degree threshold for fractional perfect matchings
- On the fractional matching polytope of a hypergraph
- On a criterion for matchability in hypergraphs
- Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
- Sharp lower bounds on the fractional matching number
- Matchings in n-partite n-graphs
- Perfect matchings in uniform hypergraphs with large minimum degree
- A note on perfect matchings in uniform hypergraphs
- Degrees and matchings
- Generalization of Erdős-Gallai edge bound
- Graph theory
- Graphs with restricted valency and matching number
- scientific article; zbMATH DE number 3169205 (Why is no real title available?)
- scientific article; zbMATH DE number 3652373 (Why is no real title available?)
- scientific article; zbMATH DE number 43754 (Why is no real title available?)
- scientific article; zbMATH DE number 1131873 (Why is no real title available?)
- scientific article; zbMATH DE number 3221072 (Why is no real title available?)
- Improved bounds for Erdős' matching conjecture
- Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
- Matching theory
- On maximal paths and circuits of graphs
- On the maximum number of edges in a hypergraph with given matching number
- The Erdős matching conjecture and concentration inequalities
- The k-factor conjecture is true
- Matchings in n-partite n-graphs
- A note on maximum size of a graph without isolated vertices under the given matching number
- The maximum number of cliques in graphs with given fractional matching number and minimum degree
- On the fractional matching extendability of Cayley graphs of abelian groups
- Maximum size of a graph with given matching number and covering number
- Spectral radius and critical covered graphs
- Generalized Turán number of matchings for connected graphs
This page was built for publication: Maximum size of a graph with given fractional matching number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2088698)
