User:DVD206/An isospectral transformation of trivalent graphs
An isospectral transformation of trivalent graphs
[edit | edit source]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:
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 Mev for edge e (connecting vertex i and j, with i > j) and vertex v given by
then the Laplacian matrix L satisfies
where is the matrix transpose of Q.
The key observation of this paper is that
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
[edit | edit source]- "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