Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.12499 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911268225417216 |
|---|---|
| author | Hasunuma, Toru |
| author_facet | Hasunuma, Toru |
| contents | 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 $δ(G) \geq \left\lfloor \frac{3k}{2} \right\rfloor +m-1$ contains a subtree $T' \cong T$ such that $G-V(T')$ is still $k$-connected, where $δ(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 $δ(G) \geq k+m-1$ contains a subtree $T' \cong T$ such that $G-E(T')$ is $k$-connected (respectively, $k$-edge-connected),
$\bullet$ every $k$-edge-connected cograph $G$ with $δ(G) \geq k+m-[k = 1]$ contains a subtree $T' \cong T$ such that $G-V(T')$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_12499 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Mader's Conjecture and Its Variants for Cographs Hasunuma, Toru Combinatorics 05C40, 05C05, 05C07 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 $δ(G) \geq \left\lfloor \frac{3k}{2} \right\rfloor +m-1$ contains a subtree $T' \cong T$ such that $G-V(T')$ is still $k$-connected, where $δ(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 $δ(G) \geq k+m-1$ contains a subtree $T' \cong T$ such that $G-E(T')$ is $k$-connected (respectively, $k$-edge-connected), $\bullet$ every $k$-edge-connected cograph $G$ with $δ(G) \geq k+m-[k = 1]$ contains a subtree $T' \cong T$ such that $G-V(T')$ 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. |
| title | Mader's Conjecture and Its Variants for Cographs |
| topic | Combinatorics 05C40, 05C05, 05C07 |
| url | https://arxiv.org/abs/2511.12499 |