  We consider the problem of characterizing graphs with the maximum spectral
radius among the connected graphs with given numbers of vertices and edges. It
is well-known that the candidates for extremal graphs are threshold graphs, but
only a few partial theoretical results have been obtained so far. Therefore, we
approach to this problem from a novel perspective that involves incomplete
enumeration of different threshold graphs with a given characteristic. 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 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.
