IBS/KAIST Joint Discrete Math Seminar
An odd [1,b]-factor in regular graphs from eigenvalues
Suil O (오수일)
Department of Applied Mathematics and Statistics, SUNY-Korea
Department of Applied Mathematics and Statistics, SUNY-Korea
2019/06/19 Wed 4:30PM-5:30PM
An odd [1,b]-factor of a graph is a spanning subgraph H such that for every vertex v∈V(G), 1≤dH(v)≤b, and dH(v) is odd. For positive integers r≥3 and b≤r, Lu, Wu, and Yang gave an upper bound for the third largest eigenvalue in an r-regular graph with even number of vertices to guarantee the existence of an odd [1,b]-factor. In this talk, we improve their bound.
for each 
, where 
is the set of edges incident to v. The fractional matching number of G, written 
, is the maximum of 
over all fractional matchings f. Let G be an n-vertex graph with minimum degree d, and let 
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}](https://s0.wp.com/latex.php?latex=%5Clambda_1%28G%29+%3C+d%5Csqrt%7B1%2B%5Cfrac%7B2k%7D%7Bn-k%7D%7D%26%2391%3B%2Flatex%26%2393%3B%2C+then+%26%2391%3Blatex%26%2393%3B%5Calpha%27_%2A%28G%29+%3E+%5Cfrac%7Bn-k%7D%7B2%7D&bg=ffffff&fg=000000&s=0 "\lambda_1(G) < d\sqrt{1+\frac{2k}{n-k}}[/latex], then [latex]\alpha'_*(G) > \frac{n-k}{2}")
.
-free graphs 
is replaced by 
or 
is replaced by 
. This is a joint work with Guantao Chen, Jie Han, Songling Shan, and Shoichi Tsuchiya.