A (k,6)-polyhedron is a cubic graph embedded in the plane so that all of its faces are k-gons or hexagons. Such graphs exist only for k = 2,3,4,5. The (5,6)-polyhedra are also known as fullerene graphs since they correspond to the molecular graphs of fullerenes.
The (3,6)-polyhedra have precisely 4 triangular faces and they cover the complete graph K4. Therefore, the eigenvalues 3, -1, -1, -1 of K4 are also eigenvalues of every (3,6)-polyhedron. Patrick Fowler computed eigenvalues of numerous examples and observed that all other eigenvalues occur in pairs of opposite values x, -x, a similar phenomenon as for bipartite graphs. From the spectral information, the (3,6)-polyhedra therefore behave like a combination of K4 and a bipartite graph.
Fowler's Conjecture: Let G be the graph of a (3,6)-polyhedron with 2k + 4 vertices. Then the eigenvalues of G can be partitioned into threee classes: K = {3, -1, -1, -1}, P = {x1, ..., xk} (where xi is nonnegative for i = 1, ..., k), and N = - P.
Horst Sachs and Peter John (private communication) found some reduction procedures which allow Fowler's Conjecture to be proved for many infinite classes of (3,6)-polyhedra.
Added (april 2002): See also
[1] P. W. Fowler, P. E. John, H. Sachs, (3,6)-cages, hexagonal toroidal cages, and their spectra, Discrete mathematical chemistry (New Brunswick, NJ, 1998), pp. 139-174, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 51, Amer. Math. Soc., Providence, RI, 2000.
Send comments to Bojan.Mohar@uni-lj.si