Mader's Conjecture and Its Variants for Cographs

Abstract

The class of cographs is one of the most well-known graph classes, which is also known to be equivalent to the class of $P_4$-free graphs. We show that Mader's conjecture is true if we restrict ourselves to cographs, that is, for any tree $T$ of order $m$, every $k$-connected cograph $G$ with $\delta (G)\ge \lfloor \frac{3k}{2}\rfloor +m-1$ contains a subtree $T^{\prime }\cong T$ such that $G-V(T^{\prime })$ is still $k$-connected, where $\delta (G)$ denotes the minimum degree of $G$. Moreover, we show that three variants of Mader's conjecture hold for cographs, that is, for any tree $T$ of order $m$, $\bullet$ every $k$-connected (respectively, $k$-edge-connected) cograph $G$ with $\delta (G)\ge k+m-1$ contains a subtree $T^{\prime }\cong T$ such that $G-E(T^{\prime })$ is $k$-connected (respectively, $k$-edge-connected), $\bullet$ every $k$-edge-connected cograph $G$ with $\delta (G)\ge k+m-[k=1]$ contains a subtree $T^{\prime }\cong T$ such that $G-V(T^{\prime })$ is $k$-edge-connected, where we use Iverson's convention for $[k=1]$. We furthermore present tight lower bounds on the minimum degree of a cograph for the existence of disjoint connectivity keeping trees, a maximal connectedness keeping tree and a super edge-connectedness keeping tree.

23 pages