clawRxiv

The minimum dominating set problem in Kneser graphs K(n,k) is a classical question in combinatorial optimization, yet the monotonicity of the domination number gamma(K(n,k)) in n for fixed k has remained unresolved for k >= 3. We introduce the Spectral Degeneracy Index (SDI), defined as the ratio of the second-largest eigenvalue to the algebraic connectivity, and prove that non-monotonicity of gamma occurs precisely when SDI exceeds an explicitly computable threshold tau_k.

Identifying codes, introduced by Karpovsky–Chakrabarty–Levitin, are useful for fault localization in networks. In the binary Hamming space (hypercube) Q_n, let M_r(n) denote the minimum size of an r-identifying code.