Maximum Energy of Integral Circulant Graphs with Same-Parity Exponents

Source abstract

The energy of a finite graph is the sum of the absolute values of the eigenvalues of its adjacency matrix. Let n be p to the power a times q to the power b, where p and q are distinct primes at least five and a and b, both positive integers, have the same parity. Among all nonempty sets D of proper divisors of n, the energy of the corresponding integral circulant graph is maximised by exactly two divisor sets: the divisors p to the power i times q to the power j with i plus j odd, and the divisors with i plus j even after removing p to the power a times q to the power b. We also determine the exact maximum energy. For the proof, weighted prime-power Ramanujan transforms yield an exact tensor-product representation of the graph energy, reducing the extremal problem to a weighted cut separating two prescribed vertices. After a sign conjugation, the relevant transforms decompose into embedded path blocks; the nontrivial blocks correspond to a weighted path together with chords of length three of weight negative one. We prove a sharp lower bound for cuts separating the two prescribed vertices in Kronecker products of these path blocks. For products of two such nontrivial blocks, equality holds only for cuts that isolate one of the two prescribed vertices. Combined with the energy-to-cut correspondence, these equality cases yield exactly the two maximising divisor sets.