| Popis: |
A fractional matching of a graph G is a function f from E ( G ) to the interval 0 , 1 ] such that ? e ? ? ( v ) f ( e ) ? 1 for each v ? V ( G ) , where ? ( v ) is the set of edges incident to v . The fractional matching number of G , written α ? ' ( G ) , is the maximum of ? e ? E ( G ) f ( e ) over all fractional matchings f . For G with n vertices, m edges, positive minimum degree d , and maximum degree D , we prove α ? ' ( G ) ? max { m D , n - m d , d D + d n } . For the first two bounds, equality holds if and only if each component of G is r -regular or is bipartite with all vertices in one part having degree r , where r = D for the first bound and r = d for the second. Equality holds in the third bound if and only if G is regular or is ( d , D ) -biregular. |
Full Text from ScienceDirect