![](/files/happy5.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ (3,6) $](/files/tex/54cca356ae4bc518fc2bb0e473f1368b61415fcc.png)
![$ 2k + 4 $](/files/tex/bb5d192e8d6a16e90cc773b79783d49620f76ede.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ K = \{3, -1, -1, -1\} $](/files/tex/acf0918d0c9caeff482349970a3636db0ddfca51.png)
![$ P = {x_1, ..., x_k\} $](/files/tex/e613a55348a12a5a8c95a79d7689bfa7ab7435bd.png)
![$ x_i $](/files/tex/dce4936db6220b56450615964eb030778cb2790f.png)
![$ i = 1, \dots , k $](/files/tex/b2dc2586f78a0a5695206b04bab6ea68dbb0ff46.png)
![$ N = - P $](/files/tex/f936c56cf996ce092f80ad0718fb169d863bf1fe.png)
A -polyhedron is a cubic graph embedded in the plane so that all of its faces are
-gons or hexagons. Such graphs exist only for
. The
-polyhedra are also known as fullerene graphs since they correspond to the molecular graphs of fullerenes.
The -polyhedra have precisely 4 triangular faces and they cover the complete graph
. Therefore, the eigenvalues
,
,
,
of
are also eigenvalues of every
-polyhedron. Patrick Fowler computed eigenvalues of numerous examples and observed that all other eigenvalues occur in pairs of opposite values
,
, a similar phenomenon as for bipartite graphs. From the spectral information, the
-polyhedra therefore behave like a combination of
and a bipartite graph.
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.
Bibliography
[FJS] 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. MathSciNet
[M] B. Mohar: Problem of the Month
* indicates original appearance(s) of problem.