Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646879 | Discrete Mathematics | 2016 | 5 Pages |
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
Ilkyoo Choi, Jaehoon Kim, Suil O,