MAXIMIZING SPECTRAL RADIUS OF GRAPHS IS AN OPTIMIZATION PROBLEM

Abstract

Threshold graphs (TGs) are important in graph theory for their special structure and numerous appli- cations. Especially interesting are the TGs that maximize the index, i.e., the largest eigenvalue. Characterization of radius maximizers among connected TG with a given number of vertices and edges in the general case is still an open problem. Therefore, computer enumeration that would help researchers make and prove hypotheses about such graphs’ structure seems promising. We consider this enumeration a combinatorial optimization problem and address it using metaheuristic methods, General Variable Neighborhood Search (GVNS) and improvement-based Bee Colony Optimization (BCOi). Preliminary results on moderate-sized examples showed that more systematic searches performed by GVNS performed slightly better than the random modifications utilized within BCOi. Our methodology defines the considered problem as an optimization task and utilizes two metaheuristic methods, Variable Neighborhood Search (VNS), which relies on iterative improvements of a single current best solution, and Bee Colony Optimization (BCO), a population-based metaheuristic from the Swarm Intelligence (SI) class. We use compact solution representation and several auxiliary data structures that should enable an efficient search of the solution space. In addition, we define several types of transformations that preserve the feasibility of the resulting solution. The proposed methods are compared on the graphs with a moderate number of vertices. Preliminary results are in favor of the VNS approach, however, we believe that both methods could be improved.