PreprintarXiv licencearXiv
The Exact Degree Threshold for Complement Connectivity
Abstract
For a graph G, we investigate sufficient degree conditions under which either G or its complement G̅ is k-connected. Motivated by a theorem of Hellwig and Volkmann, we introduce the notion of complement connectivity admissible pairs and define the parameter 𝒞(k) as the minimum degree threshold guaranteeing that either G or G̅ is k-connected whenever δ(G)≥𝒞(k) and Δ(G)≤ |V(G)|−1−𝒞(k). We prove that 𝒞(k)=2k−2 for every k≥2, thereby determining the exact degree threshold. As an application, we derive a Nordhaus--Gaddum type product condition, showing that for n≥4k−5, the condition δ(G)δ(G̅) ≥ (2k−3)(n−2k+2) guarantees that either G or G̅ is k-connected. Finally, we show that no analogous product condition depending only on k can exist.
Related
- A Threshold Constant for Exact Community Recovery in the Degree-Corrected Poisson Stochastic Block Model
- Maximum degree for random geometric graphs in the connectivity regime and beyond
- An improved minimum degree threshold for fractional clique decompositions in partite graphs
- The Connectivity Threshold for Friends and Strangers graphs
- When chromatic polynomials coincide with list-color functions: a threshold linear in the maximum degree
BibTeX
@misc{tekdas2026exact,
title = {{The Exact Degree Threshold for Complement Connectivity}},
author = {Arsen Berk Tekdaş},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14292},
eprint = {2610.14292},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14292},
}
RIS
TY - UNPB
TI - The Exact Degree Threshold for Complement Connectivity
AU - Arsen Berk Tekdaş
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.14292
UR - https://arxiv.org/abs/2610.14292
AB - For a graph G, we investigate sufficient degree conditions under which either G or its complement G̅ is k-connected. Motivated by a theorem of Hellwig and Volkmann, we introduce the notion of complement connectivity admissible pairs and define the parameter 𝒞(k) as the minimum degree threshold guaranteeing that either G or G̅ is k-connected whenever δ(G)≥𝒞(k) and Δ(G)≤ |V(G)|−1−𝒞(k). We prove that 𝒞(k)=2k−2 for every k≥2, thereby determining the exact degree threshold. As an application, we derive a Nordhaus--Gaddum type product condition, showing that for n≥4k−5, the condition δ(G)δ(G̅) ≥ (2k−3)(n−2k+2) guarantees that either G or G̅ is k-connected. Finally, we show that no analogous product condition depending only on k can exist.
ER -