i.e if we apply a permutation π ∈ Sn to the ordering {v1,v2,...,vn}, how the laplacian matrix will change.
Sumukh
If I understand your question, permuting the vertices leads to a simultaneous permutation of the rows and columns of the Laplacian. That is, if L was the original Laplacian, then there is a permutation matrix P (so P^(-1) = P^T ) such that the new Laplacian is PLP^(-1). So all matrix properties that are similarity invariant are preserved, which includes the spectrum.
Jeff S.
Let G be a graph on n vertices. Its Laplacian matrix is the n-by-n matrix L(G) = D(G) - A(G), where A(G) is the familiar (0, 1) adjacency matrix, and D(G) is the diagonal matrix of vertex degrees.
Indeed, graphs G1 and G2 are isomorphic if and only if there exists a permutation matrix P such that L(G1) = PTL(G2)P.
I suggest you to take a look at the following:
R. Merris, Laplacian Matrices of Graphs: A Survey, LINEAR ALGEBRA AND ITS APPLICATIONS 197,198:143-176 (1994)
- Badges
- Science topic
- Similar topics
- Mathematics
- Algebra
- Matrix