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

G. Gutin; Y. Hao; Y. Zhou

Matemática y estadísticaCombinatoria y matemática discreta

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

G. Gutin, Y. Hao, Y. Zhou

Preprint

En palabras de los autores

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))$ .

Resultado principalEl resumen no menciona limitaciones.

Leer el paper PDF

Apareció: martes, 22 de septiembre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 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

En palabras de los autores

Más de Combinatoria y matemática discreta ese día

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