An Evolutionary Algorithm of Generating Integral Graphs
by
K. T. Zwierzynski
Poznan

A graph is integral if its spectrum (of its adjacency matrix) consists entirely of integers. Generating integral graphs is a difficult algorithmic problem not only because of the exponential growth of the search space but also because of the fact that the number of integral graphs is small in the set of all graphs of a given order.

In the proposed algorithm we apply an evolutionary technique, a well known optimization method. The following decisions have been made: each graph is coded as a binary vector (corresponding to its adjacency matrix), the fitness function uses spectrum and some structural properties of a given graph, and mutation (defined as a change of the binary vector at a random position) is the only evolutionary operator. Using as input: n - the number of vertices, p - the edge probability, m - the size of initial population, s - the number of iterations, and w - the scaling exponent it produces a set C of connected integral graphs on n vertices. The algorithm generates s populations as follows. An initial population of m graphs is generated using the G(n, p) model of random graphs. Then, the value of the fitness function is calculated for each element of the population and integral graphs (these having a maximum possible value of this function) are added to the set C. The next step is to select graphs to the parent population with probability proportional to the scaling expression. Using mutation to the elements of the parent population a new population is generated.

Parameters and results of implementation of this algorithm for n < 14 will be discussed.

The method described above could be used for generating other classes of graphs provided an appropriate fitness function is defined.

Problem 1. Find a set of graph operations such that any integral graph can be constructed or show that such a set does not exist.

Problem 2. Enumeration of connected integral graphs.

Date received: May 26, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafd-26.