User:DVD206/An isospectral transformation of trivalent graphs

An isospectral transformation of trivalent graphs

Abstract. We describe an essentially isospectral transformation of trivalent graphs into four-valent graphs. The transformation is motivated by the construction of a medial graph for a triangulation of a surface. The transformation gives a family of counterexamples for the graph analog of the classic inverse problem "Can you hear the shape of a drum?".

A graph G(V,E) is a pair of sets, where E is a subset of pairs of distinct elements of the set V. The elements of V are called vertices, and the elements of E edges. For every edge (a,b) in E b is called a neighbor of a. The number of neighbors of a vertex is called its degree.

The Laplacian matrix L of a graph G(V,E) is defined in the following way:

$L_{i,j}(G):={\begin{cases}\deg(v_{i})&{\mbox{if}}\ i=j\\-1&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ (v_{i}v_{j})\in E\\0&{\mbox{otherwise}}\end{cases}}$

A graph is called trivalent if its every node has exactly three neighbors. If it is embedded into a surface then its dual graph is a triangulation of the surface.

If we define an oriented incidence matrix M with element M_ev for edge e (connecting vertex i and j, with i > j) and vertex v given by

$M_{ev}=\left\{{\begin{array}{rl}1,&{\text{if}}\,v=i\\-1,&{\text{if}}\,v=j\\0,&{\text{otherwise}},\end{array}}\right.$

then the Laplacian matrix L satisfies

$L(G)=6I-Q^{T}Q\,,$

where $Q^{\text{T}}$ is the matrix transpose of Q.

The key observation of this paper is that

$L(M(G))=6I-QQ^{T},$

and, therefore, by the basic linear algebra the Laplacian spectra of the graphs G and M(G) are equal except the eigenvalue 6 w/some multiplicity.

The construction can be easily generalized to graphs of constant valency.

References

• "Convex Polytopes". B. Grunbaum, Interscience, 1967
• "Can one hear the shape of a drum?" M. Kac, American Mathematical Monthly 73 (4, part 2): 1–23, (1966)
• "One cannot hear the shape of a drum". Carolyn Gordon, David L. Webb and Scott Wolpert, Bull. Amer. Math. Soc. 27 (1992), 134-138
• "On 2D Inverse Problems". Wikibooks 2013