ACO Defense of Research Proposal of Xiying Du, August 18, 2023
Title: On (2,m)-linked graphs
Date: August 18th, 2023
Time: 3:00pm ET
Location: Skiles 114
Zoom: https://gatech.zoom.us/j/94079457402?pwd=U1MwVlJkVXUzLzB3aEZCS2drb1Budz09
Committee:
Dr. Xingxing Yu (Advisor), School of Mathematics, Georgia Institute of Technology
Dr. Anton Bernshteyn, School of Mathematics, Georgia Institute of Technology
Dr. Tom Kelly, School of Mathematics, Georgia Institute of Technology
Abstract:
We say that a graph G is k-linked if, for any 2k distinct vertices s_1,...,s_k,t_1,...,t_k of G, there exist k pairwise disjoint paths P_1,...,P_k such that P_i is an s_i-t_i path for i=1,...,k. A fundamental result in structural graph theory is the characterization of 2-linked graphs, obtained independently by Robertson and Chakravarty [1980], Seymour [1980] and Thomassen [1980]. My research involves the notion ``(2,m)-linkage", which generalizes the concept of 2-linkage. A graph G is (2,m)-linked if, for any distinct vertices a_1,...,a_m,b_1,b_2 in G, there exist vertex-disjoint connected subgraphs A,B of G such that V(A) contains a_1,...,a_m and B is a b_1-b_2 path. I will discuss recent joint work with Yanjia Li, Shijie Xie, and Xingxing Yu, where we proved a sufficient condition on connectivity and average degree for a graph to be (2,m)-linked. This implies that every (2m+2)-connected graph G is (2,m)-linked and for any distinct vertices a_1, ..., a_m, b_1,b_2 of G, there is a path P in G between b_1 and b_2 and avoiding \{a_1, ..., a_m\} such that G-P is connected. I will also talk about my current and future work on a characterization of (2,3)-linked graphs.
