Methods of Generating Integral Graphs
by
K. T. Balinska
Poznan

The problem "Which graphs have integral spectra?" posed by Frank Harary and Alan Schwenk in 1974 is studied. Some classes of integral graphs are known. Results for graphs with maximum degree 3 and 4 have been obtained by D. Cvetkovi\'c (1974, 1975), A. Schwenk (1978), S. Simi\'c (1995) and others. Moreover, several graph operations (e.g., Cartesian product, weak and strong tensor products) on integral graphs can be used for constructing infinite families of integral graphs with increasing order.

We have proposed a procedure of studying integral graphs by generating, step by step, all connected integral graphs with a fixed order. This results not only in the set of all structures, data on the number of these graphs and sets of their invariants but also in definitions of new infinite families of integral graphs. Several algorithms - exact and randomized are described and some properties of the generated set of (almost 600) connected integral graphs of small order ( < 14) are discussed.

Conjecture 1. The proportion c(n)/c₁(n) of the number of integral graphs to the number of connected integral graphs does not tend to 1 when n, the number of vertices, grows.

Conjecture 2. The order of the automorphism group of integral graphs (n > 1) is bigger than 1.

Problem 1. Determine whether the sequences c₁(n)/c₁(n-2) for the number of connected integral graphs with n odd and n even are bounded when n grows.

Problem 2. Determine the upper bound for the order of integral graphs with maximum degree bigger than 3.

Problem 3. Determine the set of "primitive" integral graphs, i.e. those that can not be generated using graph operations on integral graphs.

Problem 4. Find all partitions of K_n into m (m=2) edge disjoint connected integral graphs of the same order.

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-02.