Linkages and removable paths avoiding vertices

MaRDI QIDQ6430394zbMATH OpenFDO

Authors Xiying Du, Yanjia Li, Shi-Jie Xie, Xingxing Yu

Publication date 21 March 2023

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40) Structural characterization of families of graphs (05C75)

Abstract: We say that a graph $G$ is $(2,m)$-linked if, for any distinct vertices $a_1,ldots,a_m,b_1,b_2$ in $G$, there exist vertex disjoint connected subgraphs $A,B$ of $G$ such that $a_1,ldots,a_m$ is contained in $A$ and $b_1,b_2$ 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 $mge3$. 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 $a_1,ldots,a_m,b_1,b_2$ are distinct vertices of $G$, then there is a path $P$ in $G$ between $b_1$ and $b_2$ and avoiding $a_1,ldots,a_m$ such that $G-P$ is connected, improving a previous connectivity bound of $10m$.

This page was built for publication: Linkages and removable paths avoiding vertices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6430394)