Exact values of the Bougard-Joret function in its open second regime up to order 22

Let f(n, α, k) be the minimum number of edges of a k-connected graph of order n with independence number α. Bougard and Joret conjectured f(n, α, k) = t(n, α) + ⌈kα/2⌉ when n > kα, where t(n, α) is the size of the balanced union of α cliques. Das and Gupta disproved the other line of the conjecture and left this second regime open. Bougard and Joret proved the second line only when ⌊n/α⌋ ≥ ⌈kα/2⌉ − α + 2 (for α ≥ 3). We compute f exactly at every triple outside that range with α ≥ 3, k ≥ 3 and n ≤ 23: 47 triples. At every one of them the value equals the conjectured one, by complete enumeration of every candidate graph below it (6,224,502,963 candidate graphs in all). The enumeration uses nauty with two pruning rules that are proved sound, and an exact filter checked against an independent implementation. The data support the second line of the conjecture in its smallest open cases; they do not prove it in general. Version 0.02 adds the eight open triples of order 23 (7,304,488 candidate graphs). Source code, enumeration records and the extremal graphs: https://github.com/fsantibanezleal/CAOS_RESEARCH (problems/combinatorics/bougard-joret, experiments EXP-005 to EXP-008).

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-07
DOI
https://doi.org/10.5281/zenodo.24044537
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Exact values of the Bougard-Joret function in its open second regime up to order 22

Felipe A. Santibáñez-Leal
1 links
Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
preprint

Exact values of the Bougard-Joret function in its open second regime up to order 22

Felipe A. Santibáñez-Leal
preprint en

Abstract

Let f(n, α, k) be the minimum number of edges of a k-connected graph of order n with independence number α. Bougard and Joret conjectured f(n, α, k) = t(n, α) + ⌈kα/2⌉ when n > kα, where t(n, α) is the size of the balanced union of α cliques. Das and Gupta disproved the other line of the conjecture and left this second regime open. Bougard and Joret proved the second line only when ⌊n/α⌋ ≥ ⌈kα/2⌉ − α + 2 (for α ≥ 3). We compute f exactly at every triple outside that range with α ≥ 3, k ≥ 3 and n ≤ 23: 47 triples. At every one of them the value equals the conjectured one, by complete enumeration of every candidate graph below it (6,224,502,963 candidate graphs in all). The enumeration uses nauty with two pruning rules that are proved sound, and an exact filter checked against an independent implementation. The data support the second line of the conjecture in its smallest open cases; they do not prove it in general. Version 0.02 adds the eight open triples of order 23 (7,304,488 candidate graphs). Source code, enumeration records and the extremal graphs: https://github.com/fsantibanezleal/CAOS_RESEARCH (problems/combinatorics/bougard-joret, experiments EXP-005 to EXP-008).

Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon