×

Maximum size of a graph with given fractional matching number. (English) Zbl 1510.05148

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 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\).

MSC:

05C35 Extremal problems in graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C72 Fractional graph theory, fuzzy graph theory

Citations:

Zbl 1242.05189

References:

[1] N. Alon, P. Frankl, H. Huang, V. R˝odl, A. Ruci´nski, B. Sudakov, Large matchings in uniform hypergraphs and the conjectures of Erd˝os and Samuels,J. Combin. Theory Ser. A119 (2012), 1200-1215. · Zbl 1242.05189
[2] N. Balachandran, N. Khare, Graphs with restricted valency and matching number, Discrete Math.309 (2009), 4176-4180. · Zbl 1218.05120
[3] C. Berge, Hypergraphs, North-Holland Mathematical Library 45, North-Holland, Amsterdam, 1989. · Zbl 0674.05001
[4] B. Bollob´as, Extremal Graph Theory, Academic Press, 1978. · Zbl 0419.05031
[5] J. Bondy, U.S.R. Murty,Graph Theory, Graduate Texts in Mathematics 244, Springer, 2008. · Zbl 1134.05001
[6] V. Chv´atal, D. Hanson, Degrees and matchings,J. Combin. Theory Ser. B20 (1976), 128-138. · Zbl 0324.05119
[7] P. Erd˝os, A problem on independentr-tuples,Ann. Univ. Sci. Budapest8 (1965), 93-95. · Zbl 0136.21302
[8] P. Erd˝os, T. Gallai, On maximal paths and circuits of graphs,Acta Math. Hungar. 10 (1959), 337-356. · Zbl 0090.39401
[9] P. Erd˝os, T. Gallai, Graphs with prescribed degrees of vertices,Mat. L´apok11 (1960), 264-274. · Zbl 0103.39701
[10] P. Frankl, Improved bounds for Erd˝os matching conjecture,J. Combin. Theory Ser. A120 (2013), 1068-1072. · Zbl 1277.05123
[11] P. Frankl, On the maximum number of edges in a hypergraph with given matching number,Discrete Appl. Math.216 (2017) 562-581. · Zbl 1358.05202
[12] P. Frankl, A. Kupavskii, The Erd˝os matching conjecture and concentration inequalities,J. Combin. Theory Ser. B157 (2022), 366-400. · Zbl 1497.05253
[13] N. Khare, N. Mehta, N. Puliyambalath, Generalization of Erd˝os-Gallai edge bound, European J. Combin.43 (2015), 124-130. · Zbl 1301.05189
[14] S. Kundu, Thek-factor conjecture is true,Discrete Math.6 (1973), 367-376. · Zbl 0278.05115
[15] L. Lov´asz, M. Plummer,Matching Theory, Ann. Discrete Math. 29, North-Holland, Amsterdam, 1986. · Zbl 0618.05001
[16] E. Scheinerman, D. Ullman,Fractional Graph Theory: A Rational Approach to the Theory of Graphs, John Wiley, New York, 1997 · Zbl 0891.05003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.