The difference and ratio of the fractional matching number and the matching number of graphs

DOI10.1016/J.DISC.2015.12.005MaRDI QIDQ906487zbMATH OpenOpenAlexFDO

Authors Ilkyoo Choi, Suil O, Jaehoon Kim

Publication date 21 January 2016

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.07595

zbMATH Keywords

matching numberfractional matching number

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Given a graph $G$, the matching number of $G$, written $alph{a}^{\prime }(G)$, is the maximum size of a matching in $G$, and the fractional matching number of $G$, written $alpha{\text{'}}_f(G)$, is the maximum size of a fractional matching of $G$. In this paper, we prove that if $G$ is an $n$-vertex connected graph that is neither $K_1$ nor $K_3$, then $alpha{\text{'}}_f(G)-alph{a}^{\prime }(G)lefracn-26$ and $fracalpha{\text{'}}_f(G)alph{a}^{\prime }(G)lefrac3n2n+2$. Both inequalities are sharp, and we characterize the infinite family of graphs where equalities hold.

Recommendations

• The fractional matching numbers of graphs
• Nordhaus-Gaddum type inequality for the fractional matching number of a graph
• Sharp lower bounds on the fractional matching number
• A note on maximum fractional matchings of graphs
• Fractional matching number and eigenvalues of a graph

Cites work

• scientific article; zbMATH DE number 3141016 (Why is no real title available?)
• Minimum node covers and 2-bicritical graphs
• The Factorization of Linear Graphs

Cited in

(9)

• The skiving stock problem and its relation to hypergraph matchings
• A Ramsey-type theorem for the matching number regarding connected graphs
• Spectral radius and fractional perfect matchings in graphs
• Signless Laplacian spectral radius and fractional matchings in graphs
• Sharp lower bounds on the fractional matching number
• Nordhaus-Gaddum type inequality for the fractional matching number of a graph
• Integer \(k\)-matchings of graphs
• Fractional matching number and eigenvalues of a graph
• Combinatorics of unavoidable complexes

This page was built for publication: The difference and ratio of the fractional matching number and the matching number of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q906487)