Suil O, Spectral radius and fractional matchings in graphs

Spectral radius and fractional matchings
in graphs
Suil O
Georgia State University
2014/12/23 Tuesday 4PM-5PM
Room 1409
A fractional matching of a graph G is a function f giving each edge a number between 0 and 1 so that \sum_{e \in \Gamma(v)} f(e) \le 1 for each v \in V(G), where \Gamma(v) is the set of edges incident to v. The fractional matching number of G, written \alpha'_*(G), is the maximum of \sum_{e \in E(G)} f(e) over all fractional matchings f. Let G be an n-vertex graph with minimum degree d, and let \lambda_1(G) be the largest eigenvalue of G. In this talk, we prove that if k is a positive integer and \lambda_1(G) < d\sqrt{1+\frac{2k}{n-k}}[/latex], then [latex]\alpha'_*(G) > \frac{n-k}{2}.

Tags:

Comments are closed.