PreprintCC BY 4.0arXiv
An O(klog(n/k)) Bound on Spanning Bipartite Connectivity
Abstract
For integers 1≤ k≤ n/2, let f(k,n) be the least integer s such that every s-connected graph on n vertices contains a spanning bipartite k-connected subgraph. Thomassen conjectured that f(k,n) is bounded by a function of k alone. Delcourt and Ferber proved f(k,n)=O(k3log n), and Yuster subsequently obtained f(k,n)≤22k2log2 n. We prove that, for 2≤ k≤ n/2, f(k,n)≤min{n−1, ⌊6(k−1)log2n/(k−1)⌋}. In particular, f(k,n)=O(klog(n/k)).
Related
- Maximum number of spanning trees in bipartite graphs with a given diameter
- Spanning bipartite quadrangulations in even triangulations of real projective spaces
- Wild number for spanning trees in complete and complete bipartite graphs
- Spectral radius and edge-disjoint spanning trees of graphs with edge connectivity
- A sharp upper bound on the number of spanning forests of regular graphs
BibTeX
@misc{gutin2026oklognk,
title = {{An $O(k\log(n/k))$ Bound on Spanning Bipartite Connectivity}},
author = {G. Gutin and Y. Hao and Y. Zhou},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23262},
eprint = {2609.23262},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23262},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - An O(klog(n/k)) Bound on Spanning Bipartite Connectivity
AU - G. Gutin
AU - Y. Hao
AU - Y. Zhou
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.23262
UR - https://arxiv.org/abs/2609.23262
AB - For integers 1≤ k≤ n/2, let f(k,n) be the least integer s such that every s-connected graph on n vertices contains a spanning bipartite k-connected subgraph. Thomassen conjectured that f(k,n) is bounded by a function of k alone. Delcourt and Ferber proved f(k,n)=O(k^3log n), and Yuster subsequently obtained f(k,n)≤22k^2log_2 n. We prove that, for 2≤ k≤ n/2, f(k,n)≤min{n−1, ⌊6(k−1)log_2n/(k−1)⌋}. In particular, f(k,n)=O(klog(n/k)).
ER -