User:Daviddaved/Printed Version/Two new spectral theorems

From Wikibooks, open books for an open world
Jump to: navigation, search

Hamiltonian paths

The existence of the paths in a graph and its dual with the following properties plays an important role in the connection between global and local properties of the graph: Two sets of paths between two subsets of boundary nodes in the graph and its dual are Hamiltonian if the paths go through every edge of the graph or its dual.

The paths go through all vertices of G and G*

The following identity connects the weights of the paths of a network and its dual, an integral of conductivity over the network and the eigenvalues of the Laplacian of the dual graphs, that admit Hamiltonian paths.


\frac{\det\Lambda(P,Q)}{\det\Lambda^*(P^*,Q^*)} = \prod_{e\in E}\gamma(e)\frac{\det(K^*)}{\det(K)}.

Triangulation of surfaces

Let G be a graph embedded to a surface such that all faces of G are triangular. Such an embedding is called triangulation. The vertices of the dual graph G* of triangulation have degree 3.

Medial graph of triangulation

Exercise (***). Generalize the following example to prove that the spectra of G* and M(G) are equal, except possibly the eigenvalue {6}.


\sigma(G^*)\cup \{6\}=\sigma(M(G))\cup \{6\}
Medial graph