Let $G=(V,E)$ be a finite undirected graph on $n$ vertices and $m$ edges. The line digraph of $G$, denoted $L(G)$, is an associated directed graph that captures edge incidences of $G$. More precisely, interpret each undirected edge of $G$ as two directed edges so that $G$ is now a directed graph. Then the vertices of $L(G)$ are the $nm$ directed edges, and a vertex (corresponding to directed edge $\vec{e}$) is connected to a vertex (corresponding to directed edge $\vec{e}'$) if $\vec{e}$ feeds into $\vec{e}'$ in $G$.

My question is regarding the structure of $G$ given the structure of $L(G)$.

Suppose $G$ is a Cayley graph for the group $\Gamma$ and symmetric generating set $S$, then can $L(G)$ also be interpreted as a Cayley digraph of some group and (non-symmetric) generating set?

EDIT: In light of Prof.Godsil's answer and the references therein, the answer to this is NO. The automorphism groups of $G$ and $L(G)$ are the same, and so since $L(G)$ is larger than $G$ (except when $G$ is a path or cycle), $L(G)$ is not a Cayley graph.

But the converse question is:

Conversely, suppose the line digraph $L(G)$ of a regular graph $G$ is a Cayley digraph of some group and generating set. Then is $G$ a Cayley graph of some group and symmetric generating set? What can we say about its group and generating set?

Would removing all digons from the line digraph (thus making it a non-backtracking digraph for the underlying graph) change the situation into a more tractable one?

Firstly I am not very clear on when a directed graph arises as a line digraph of a simple graph. As in, I know of the general results of Harary in this regard, but is there a simpler picture when the given digraph is a Cayley digraph?


It follows from Villar, Jorge Luis. "The underlying graph of a line digraph." Discrete Applied Mathematics 37 (1992): 525-538, that in general the automorphism group of the line digraph is isomorphic to the automorphism group of the graph. Since the line digraph has more vertices than the graph (when the letter is $k$-regular with $k\ge3$ say), it follows that the line digraph is not even vertex transitive, and hence cannot be a Cayley graph.

  • $\begingroup$ Thanks for the reference. What if we use the non-backtracking line digraph? That is, no directed edge of $G$ is connected to its inverse. In that case, would it make a difference? $\endgroup$ – BharatRam Oct 15 '17 at 14:40
  • $\begingroup$ @BharatRam: My guess is that in most cases it would make no difference. It may well follows from results in Villar’s paper. $\endgroup$ – Chris Godsil Oct 15 '17 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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