Document Type
Lecture
Publication Date
10-16-2015
Abstract
A fractional matching of a graph G is a function : E(G) that for each vertex v, e (v) (e) 1, where (v) is the set of edges incident to v. The fractional matching number of G, written f(G), is the maximum of e E(G) (e) over all fractional matchings . In this talk, we talk about some lower bounds for f(G) in terms of V(G) E(G) (G) and (G). f [01] such By viewing every matching as a fractional matching, we have (G) (G) for every graph G, where (G) is the maximum size of a matching in G, but equality need not hold. We also talk about how large the di erence (ratio) between f(G) and (G) in a (connected) graph can be. In 2005, Gregory and Haemers had given a relationship between 3(G) and the existence of a perfect matching in a d-regular graph with even number of vertices, where 3(G) is the third largest eigenvalue of an adjacency matrix of G. After that, some research between 3(G) and (G) in a d-regular G was investigated. In addition to the above two results, we give a relationship between 1(G) and f(G), where 1(G) is the largest eigenvalue of an adjacency matrix of G. (This is a partly joint work with Behrend, Choi, Kim, and West.)
Relational Format
presentation
Recommended Citation
O, Suil, "Fractional matchings of graphs" (2015). Combinatorics Seminar. 32.
https://egrove.olemiss.edu/math_combinatorics/32
