The first interior shell of the Bougard-Joret extremal problem

Read full text
Authors: Felipe A. Santibáñez-Leal
Cited by: 4
References: 3

Abstract

Version 0.02 proves the entire admissible first interior shell: for every integer k at least 3 and every independence number a from 2 through k+1, the minimum size of a k-connected graph of order a+k+1 and independence number a is ceiling(k(a+k+1)/2). The construction combines classical Harary graphs, complement matchings and injective missing-neighbor pairs, with a self-contained connectivity proof for all parity cases. All extremizers at a=2 are complements of disjoint cycles of lengths at least five. The complete nonstar-tree characterization at a=k-1 from version 0.01 is retained. Exact finite controls cover 75 graphs and include an independent NetworkX audit. The original disproof remains credited to Das and Gupta; classical and previously published parameter overlaps are identified. This settles a restricted infinite shell, not the general revised first regime or second regime. Preprint, not peer reviewed.

Fields of Study & Subjects

Advanced Graph Theory Research Complexity and Algorithms in Graphs Interconnection Networks and Systems

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
5 September 2026
Language
EN
Document type
Preprint