Sandbox:DavidKohler/Relativized Alon Conjecture/Line graph

The line graph associated to a given directed graph gives us information about non-backtracking walks in the original graph.

Definition

Let G be a directed graph, consider the directed graph whose vertices are the directed edges of the graph G and where there is a directed edge from e_i to e_j if:

• $\displaystyle e_{i}^{-1}\neq e_{j}$
• $\displaystyle h_{G}(e_{i})=t_{G}(e_{j})$

The adjacency matrix of the line graph is called the Hashimoto matrix of the graph G and is denoted H_G.

Properties

The line graph:

• can have self-loops but no multiple edges;
• cannot usually be endowed with an involution making it a graph (since it doesn't allow for multiple edges).

When G is a d-regular graph on n vertices, the line graph has dn vertices. The dn adjacency eigenvalues of the line graph are the irreducible eigenvalues of the original graph.

Example

To do
	Write an example. Make it nice