Nordhaus-Gaddum upper bounds for graph connectivity parameters
We examine upper bounds on Nordhaus-Gaddum type problems for parameters related to graph connectivity. Our main result is that for a graph $G$ on $n$ vertices where both $G$ and its complement $G^c$ are connected, then the sum of the algebraic connectivity of $G$ and the algebraic connectivity of $G^c$ cannot exceed $n-3$ (with finitely many exceptions with a small number of vertices). We obtain similar results for the isoperimetric number of a graph, and explore similar Nordhaus-Gaddum type questions for the Cheeger constant and the second eigenvalue of the normalized Laplacian matrix.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.12751
curl -X POST /api/v1/records/arxiv/2606.12751/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.12751/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'