A Complete Solution to the Conjecture on the Inverse Collatz–Sinogowitz Irregularity Problem

The Collatz-Sinogowitz irregularity index of a graph G is defined as CS(G) = λ(G) -d(G), where λ(G) is the spectral radius and d(G) is the average degree of G. Alazemi, Andelić and Dimitrov [Open Math.21 (2023) #20220572] conjectured that, for any positive integer i larger than a given constant and integer c ≥ 2, (i) there exists a connected c-cyclic graph of order n with CS(G) = i, provided that n divides 2(c -1); and (ii) there are infinitely many connected c-cyclic graphs whose Collatz-Sinogowitz irregularity indices lie in the interval (i, i + 1).They proved that the conjecture holds for c = 1.In this paper, we give a complete solution to the conjecture.We show that statement (i) does not hold and statement (ii) is true.Our method relies on a graph operation that preserves both the spectral radius and the average degree.Additionally, we improve a known upper bound for the Collatz-Sinogowitz irregularity index.Aouchiche et al. [European J. Oper.Res.191 (2008) 661-676] established the upper bound CS(G) ≤ n 4 -1 + 1 n .We refine this result by proving that, for any connected graph G with n vertices, CS(G) ≤ n 4 -1, with only finitely many exceptions.