## Are planar graphs characterized by their Laplacian spectrum?

It is known that there exist many pairs of nonisomorphic graphs which have the
same set of eigenvalues, even when counting multiplicities. Such graphs have
identical characteristic polynomials (of their adjacency matrices) and are said
to be *cospectral*.

Such a result remains true even when we restrict to some rather limited classes
of graphs. For example, it is known that "almost all trees are cospectral".
This last statement holds in a much stronger sense; namely, there are many
nonisomorphic pairs of trees that have
the same characteristic polynomial not only for the adjacency matrix but at the
same time also for their Laplacian matrix and their distance matrix [1].

From another perspective, D. Cvetkovic and D. Stevanovic asked at the Glasgow Meeting on Algebraic Graph Theory
in July 2001, if the fullerene graphs may be determined by their eigenvalues
(characteristic polynomials) together with the collection of the angles between
the standard basis and the eigenspaces (cf. [2]).
Let us recall that fullerene graphs are 3-connected cubic planar graphs with 12 faces of
size 5 and all other faces of size 6.

The result of Tutte on the "spring" embeddings of planar graphs [3]
encouraged me to propose the following stronger conjectures:

**
Conjecture 1.** Eigenvalues and angles determine cubic 3-connected planar graphs
up to isomorphism.
**Conjecture 2.** Eigenvalues and angles of the Laplacian matrix determine
3-connected planar graphs up to isomorphism.

Bibliography:
[1] P. Botti, R. Merris, Almost all trees share a complete set of immanantal polynomials,
J. Graph Theory 17 (1993) 467-476.

[2] D. Cvetkovic, P. Rowlinson, S. Simic,
Eigenspaces of graphs, Encyclopedia of Mathematics and its Applications 66,
Cambridge University Press, Cambridge, 1997.

[3] W. T. Tutte, How to draw a graph, Proc. London Math. Soc. 13 (1963)
743-768.

Send comments to Bojan.Mohar@uni-lj.si

##### Revised: december 14, 2001.