Article ID Journal Published Year Pages File Type
4646879 Discrete Mathematics 2016 5 Pages PDF
Abstract

Given a graph GG, the matching number   of GG, written α′(G)α′(G), is the maximum size of a matching in GG, and the fractional matching number   of GG, written αf′(G), is the maximum size of a fractional matching of GG. In this paper, we prove that if GG is an nn-vertex connected graph that is neither K1K1 nor K3K3, then αf′(G)−α′(G)≤n−26 and αf′(G)α′(G)≤3n2n+2. Both inequalities are sharp, and we characterize the infinite family of graphs where equalities hold.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,