2020.10
Combinatorics Incheon
Combinatorics Incheon
Special Session on Factors and Eigenvalues of Graphs (SS-15)
Virtually, October 24, 2020
Organizer, Suil O, SUNY Korea
Subgraphs in odd-degree regular graphs
Ilkyoo Choi, Hankuk University of Foreign Studies; Ringi Kim, Inha University; Alexandr V. Kostochka, University of Illinois; Boram Park, Ajou University; André Raspaud, University of Bordeaux; Bjarne Toft, University of Southern Denmark; Douglas B. West*, Zhejiang Normal University and University of Illinois; Dara Zirlin, University of Illinois
Hanson, Loten, and Toft proved that every (2r+1)-regular graph with at most 2r cut-edges has a 2-factor. We generalize this by proving for k≤(2r+1)/3 that every (2r+1)-regular graph with at most 2r−3(k−1) cut-edges has a 2k-factor. The restrictions on k and on the number of cut-edges are sharp. We characterize the graphs having exactly 2r−3(k−1)+1 cut-edges but no 2k-factor. For k>(2r+1)/3, there are graphs without cut-edges that have no 2k-factor. We determine the maximum guaranteed size of a 2-regular subgraph in a 3-regular n-vertex graph. In particular, we prove that every multigraph with maximum degree 3 and exactly c cut-edges has a 2-regular subgraph that omits at most max{0,⌊(3n−2m+c−1)/2⌋} vertices. The bound is sharp; we describe the extremal multigraphs.
10:40 - 11:10, October 24, 2020
Eigenvalues and [a,b]-factor in regular graphs
Suil O, SUNY Korea
For positive integers, r≥3, h≥1, and k≥1, Bollobas, Saito, and Wormald proved some sufficient conditions for an h-edge-connected r-regular graph to have a k-factor in 1985. Lu gave an upper bound for the third largest eigenvalue in a connected r-regular graph to have a k-factor in 2010. Gu found an upper bound for certain eigenvalues in an h-edge-connected r-regular graph to have a k-factor in 2014. For positive integers a≤b, an even orodd [a,b]-factor of a graph G is a spanning subgraph H such that for each vertex v∈V(G), dH(v) is even orodd and a≤dH(v)≤b. In this talk, we provide sharp upper bounds for certain eigenvalues in an h-edge-connected r-regular graph G to guarantee the existence of an even [a,b]-factor or an odd [a,b]-factor. This result extends the one of Bollobas, Saito, and Wormald, the one of Lu, and the one of Gu.
11:10 - 11:30, October 24, 2020
On 1-factors with prescribed lengths in Tournaments
Dong Yeap Kang, University of Birmingham; Jaehoon Kim*, KAIST
In this talk, we introduced our result stating that every strongly 1050t-connected tournament contains all possible 1-factors with at most t components. This answers a question by K\"{u}hn, Osthus and Townsen. This result is best possible up to constant.
11:35 - 11:55, October 24, 2020
Isolated vertices, odd components and graph factors
Mikio Kano, Ibaraki University; Hongliang Lu*, Xi'an Jiaotong University
For a graph G, let i(G), odd(G) and ω(G) denote the number of isolated vertices, the number of odd components and the number of components of G, respectively. Then it is well-known that G has a 1-factor if and only if odd(G−S)≤|S| for all S⊂V(G). Also it is clear that i(G−S)≤odd(G−S)≤ω(G−S). In this talk, we will extend Tutte's Theorem and introduce some characterizations on Tutte's type conditions, isolated vertex conditions and tough conditions, using graph factors.
12:00 - 12:20, October 24, 2020