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

DOI10.1016/J.DISC.2015.12.005zbMATH Open1329.05242arXiv1512.07595OpenAlexW2216111877MaRDI QIDQ906487FDOQ906487

Authors: Ilkyoo Choi, Suil O, Jaehoon Kim 

Publication date: 21 January 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

matching numberfractional matching number

Mathematics Subject Classification ID

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

Cites Work

• The Factorization of Linear Graphs
• Title not available (Why is that?)
• Minimum node covers and 2-bicritical graphs

Cited In (9)

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

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)