Isospectral genus two graphs are isomorphic (Q2827776)

The genus of a finite and connected graph \(G=(V,E)\) is the dimension of its first homology group and it equals \(|E|-|V|+1\). The graphs of genus \(0\) are trees and graphs of genus \(1\) are cycles. The graphs of genus \(2\) are theta graphs which are defined as follows; if \(u\) and \(v\) are two (not necessarily distinct) vertices, denote by \(\Theta(k,l,m)\) the graph consisting of three internally disjoint paths joining \(u\) to \(v\) with lengths \(k,l,m\geq 0\) and \(kl+lm+mk>0\). A bridge is an edge of \(G\) whose deletion disconnects \(G\). A graph is bridgeless if it contains no bridges.NEWLINENEWLINEThe Laplacian of \(G\) is \(L=D-A\), where \(A\) is the adjacency matrix and \(D\) is the diagonal degree matrix of \(G\). Two graphs are called Laplacian isospectral or cospectral if their Laplacian eigenvalues are the same (including multiplicities).NEWLINENEWLINEThe main result of this paper is showing that two genus two bridgless graphs are Laplacian isospectral if and only if they are isomorphic. The authors remark that this result is not true for genus two graphs with bridges or for bridgeless graphs of genus three or for graphs of genus one.