An O(klog(n/k)) Bound on Spanning Bipartite Connectivity

G. Gutin; Y. Hao; Y. Zhou

Math & statisticsCombinatorics & discrete math

An $O (k lo g (n / k))$ Bound on Spanning Bipartite Connectivity

G. Gutin, Y. Hao, Y. Zhou

Preprint

In the authors' words

For integers $1 \leq k \leq 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^{3} lo g n)$ , and Yuster subsequently obtained $f (k, n) \leq 22 k^{2} lo g_{2} n$ . We prove that, for $2 \leq k \leq n /2$ , \[ f(k,n)\le\min\left\{n-1, \left\lfloor6(k-1)\log_2\frac{n}{k-1}\right\rfloor\right\}. \] In particular, $f (k, n) = O (k lo g (n / k))$ .

Main resultThe abstract does not state a limitation.

Read the paper PDF

Appeared: Tuesday, September 22. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: All proofs were written by the authors without the assistance of AI. However, GPT-6 Astra was used to check the correctness of our proofs, and no mistakes were found

An O(klog(n/k)) Bound on Spanning Bipartite Connectivity

In the authors' words

More on Combinatorics & discrete math that day

Circular s-choice parking functions: an exact closed formula via rotational symmetry

Single-Fragment Forensic Coding via Multidimensional Cyclically Permutable Codes

The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach

Proof of Almkvist's conjecture on the unimodality of partition polynomials

On infinite families of [Pn​]-irregular graphs

An $O (k lo g (n / k))$ Bound on Spanning Bipartite Connectivity

On infinite families of $[P_{n}]$ -irregular graphs