$k$-Connected Subgraphs of All Orders in Large Graphs with Minimum Degree at Least $n/q$
For every fixed pair of integers $k\ge 2$ and $q\ge 3$, we prove that every sufficiently large $k$-connected graph $G$ of order $n$ with minimum degree $δ(G)\ge n/q$ contains a $k$-connected subgraph of every order $\ell\in\{2k,2k+1,\ldots,n\}$. In the case $k=2$, this confirms a conjecture of Liu and Ning~\cite{LiuNing}. The proof combines two constructions. First, we construct a small $k$-connected subgraph $D$ such that every vertex outside $D$ has at least $k$ neighbors in $D$. By successively adding the vertices outside $D$, we obtain $k$-connected subgraphs of every order from $|V(D)|$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.18964
curl -X POST /api/v1/records/arxiv/2607.18964/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.18964/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'