# Section2.3Line Graphs and Covers

Let \(D\) be the incidence matrix of an orientation of the graph \(X\). Then

*signed adjacency matrix*. The entries of \(S\) are indexed by \(E(X)\), and the \(ab\)-entry is non-zero if and only if the edges \(a\) and \(b\) are adjacent in the line graph \(L(X)\) of \(X\), so we have a signed adjacency matrix for \(L(X)\).

A signed ajacency matrix \(T\) of a graph \(Y\) determines a *two-fold cover* \(Z\) of \(Y\), as follows. The vertex set of the cover is

The pairs

##### Lemma2.3.1

Here \(|S|=A(Y)\). We offer another view of this result. If \(A\) and \(B\) are symmetric \(01\)-matrices such that \(A\circ B=0\), then \(A-B\) is a signed adjacency matrix and

This leads us to an easy construction of the adjacency matrix of the cover.

Now we turn to our line graphs. The cover can be constructed as follows. Choose one arc \((u,v)\) for each edge \(\{u,v\}\) of \(X\). (This defines an orientation of the graph.) Our matrix \(S\) is a signing of \(A(L(X))\)—its rows and columns are indexed by our chosen arcs, and the entry corresponding to a pair of distinct overlapping arcs is 1 if they have the same head or tail, and \(-1\) otherwise. Rather than represent the vertices of the cover by pairs \(((u,v),i)\), we proceed thus: if \((u,v)\) is one of our chosen arcs then we use \((u,v)\) to denote \(((u,v),0)\) and \((v,u)\) for \(((u,v),1)\). The following procedure implements this.

We test that our two constructions agree on the Petersen graph, and see that cover is isomorphic to the line graph of the direct product of the Petersen graph with \(K_2\). (This product is itself a cover of the Petersen graph.)