Independent Sets and Balanced Cycle-Linkings in 2-Connected Graphs
Abstract
For every α≥3 and all sufficiently large n, we identify a single graph that simultaneously maximizes the number of independent sets of every size among all n-vertex $2$-connected graphs with independence number α. This graph is unique up to isomorphism and is a balanced cycle-linking of the disjoint union of α cliques whose orders differ by at most one. More precisely, for each 3≤β≤α, the graphs maximizing the number of independent β-sets are exactly the cycle-linkings whose clique-size cyclic words are ⌊β/2⌋-balanced. These results extend the corresponding extremal result for connected graphs to the $2$-connected setting. The proof combines generalized Turán-type clique counting and the edge-extremal theory of $2$-connected graphs with a coefficientwise balancing-switch argument. The switch also shows that a shortest imbalance of length r first affects the independent-set count in degree 2r.
Related
- Hitting Maximum Independent Sets in Dense and Highly Connected Graphs
- Sharp bounds for Duke--Erdős--Rödl problems on cycle-connected subgraphs
- Hamilton-connected cores and five cycle--wheel Ramsey numbers
- Contractable 2-connected subgraphs in minimally 3-connected graphs
- Modulo k-orientations of highly edge-connected signed graphs
BibTeX
@misc{wang2026independent,
title = {{Independent Sets and Balanced Cycle-Linkings in 2-Connected Graphs}},
author = {Shuaichao Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15637},
eprint = {2609.15637},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15637},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Independent Sets and Balanced Cycle-Linkings in 2-Connected Graphs
AU - Shuaichao Wang
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15637
UR - https://arxiv.org/abs/2609.15637
AB - For every α≥3 and all sufficiently large n, we identify a single graph that simultaneously maximizes the number of independent sets of every size among all n-vertex $2$-connected graphs with independence number α. This graph is unique up to isomorphism and is a balanced cycle-linking of the disjoint union of α cliques whose orders differ by at most one. More precisely, for each 3≤β≤α, the graphs maximizing the number of independent β-sets are exactly the cycle-linkings whose clique-size cyclic words are ⌊β/2⌋-balanced. These results extend the corresponding extremal result for connected graphs to the $2$-connected setting. The proof combines generalized Turán-type clique counting and the edge-extremal theory of $2$-connected graphs with a coefficientwise balancing-switch argument. The switch also shows that a shortest imbalance of length r first affects the independent-set count in degree 2r.
ER -