Sandbox:DavidKohler/Relativized Alon Conjecture/Line graph
< Sandbox:DavidKohler/Relativized Alon Conjecture(Redirected from User: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 ei to ej if:
The adjacency matrix of the line graph is called the Hashimoto matrix of the graph G and is denoted HG.
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 |