2
$\begingroup$

Is there a nice way of relating the adjacency, incidence , Laplacian matrices and other matrices associated to a graph of a total graph with its original graph, or, say, at least relating that of the line graph with the graph?

I think there must be some relation. I also think the rank of the Laplacian of the graph and that of the graph also are closely related. Are there any references for this? Thanks beforehand.

$\endgroup$

2 Answers 2

1
$\begingroup$

If $C$ is the incidence matrix (rows indexed by vertices, columns by edges, two 1s in each column) then $CC^T$ is the Laplacian matrix and $C^TC-2I is the adjacency matrix of the linegraph. From this it follows that the non-zero eigenvalues of the Laplacian are the same as the non-zero (eigenvalues + 2) of the linegraph.

$\endgroup$
0
$\begingroup$

Not sure if I really understand what exactly you are looking for. There is a paper by Vic Reiner and some of his former REU students on the “critical group of a line graph”. This relates the Smith normal form of the laplacian matrix to that of its line graph, in a pretty strong way. The Smith normal form gives you, in particular, the rank of a matrix over any field.

$\endgroup$
1
  • $\begingroup$ The paper you refer to has good results, but unfortunately quite unrelated to the question I asked. I just asked what the relation(in mostly linear algebraic parameters) between the adjacency matrix/incidence matrix/laplacian matrix of a graph and the same matrices of its total graph is? If there is no known relation, my next question was whether such relation exists between a graph and its line graph $\endgroup$
    – vidyarthi
    Apr 11, 2019 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.