A Sublinear Minimum-Degree Condition for $2$-Connected Subgraphs of All Orders

Abstract

Motivated by an analogue of pancyclicity, we study minimum-degree conditions ensuring that a $2$-connected graph $G$ of order $n$ contains a $2$-connected subgraph of every order $\ell \in \{4,5,\dots ,n\}$. Yin and Wu [A minimum degree condition for a 2-connected graph containing all possible orders of 2-connected subgraphs, Discrete Appl. Math. 387 (2026), 129-136] initiated the study of this problem and showed that the condition $\delta (G)\ge \lceil n/3\rceil +1$ is sufficient. Kashima conjectured that the condition $\delta (G)\ge \sqrt{3n}$ is sufficient. In this paper, we prove that every $2$-connected graph $G$ of order $n$ with $\delta (G)\ge 2n^{2/3}+6n^{1/3}+2$ contains a $2$-connected subgraph of every order from $4$ to $n$. In particular, this gives the first sufficient minimum-degree condition of sublinear order in $n$.

5 pages