2023/03/21 by Xiying Du, Du, Xiying, Yanjia Li +5
Computer Science · Mathematics · #05C38 #05C40 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2303.12146
openalex publication_date 2023/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We say that a graph G is (2,m)-linked if, for any distinct vertices a1,…, am, b1,b2 in G, there exist vertex disjoint connected subgraphs A,B of G such that \a1, …, am\ is contained in A and \b1,b2\ is contained in B. A fundamental result in structural graph theory is the characterization of (2,2)-linked graphs, with different versions obtained independently by Robertson and Chakravarty, Seymour, and Thomassen. It appears to be very difficult to characterize (2,m)-linked graphs for m≥ 3. In this paper, we provide a partial characterization of (2,m)-linked graphs by adding an average degree condition. This implies that (2m+2)-connected graphs are (2,m)-linked. Moreover, if G is a (2m+2)-connected graph and a1, …, am, b1,b2 are distinct vertices of G, then there is a path P in G between b1 and b2 and avoiding \a1, …, am\ such that G-P is connected, improving a previous connectivity bound of 10m.