# How to get the directed line graph of the complete digraph?

When we replace every edge of the complete graph $$K_N$$ by a pair of directed edges, we get a complete directed graph, the Complete DiGraph $$DK_N$$ . Let $$DL_{N}$$ be directed line graph of the complete digraph.

How to get the adjacency matrix $$L$$ of $$DL_N$$?

My attempt:

I setup a $$N\times N$$ matrix, like follows (e.g. $$N=4$$): $$\mathcal I=\pmatrix{ 0&(0,1)&(0,2)&(0,3)\\ (1,0)&0&(1,2)&(1,3)\\ (2,0)&(2,1)&0&(2,3)\\ (3,0)&(3,1)&(3,2)&0 }$$ so $$\mathcal I$$ is something like an index matrix, with $$\mathcal I_{x,y}=(x,y)$$. Then $$L_{a,b}=\mathcal \delta_{y_ax_b},$$ with $$a=x_aN+y_a$$ and $$b=x_bN+y_b$$. Where $$\delta_{y_ax_b}$$ means that we choose two non-diagonal elements of $$\mathcal I$$, namely $$\mathcal I_{x_a,y_a}$$ and $$\mathcal I_{x_b,y_b}$$. This is not symmetric because ingoing edges are only linked to outgoing ones.

Is this correct? Are there other ways to get $$L$$?

• It is not clear to me what does "directed line graph of the complete digraph" means, could you please explain it a little bit? Commented Mar 4, 2016 at 14:00
• @M.Badaoui you can boil it down to: Given the adjacency matrix of the complete digraph, how to you construct the adjacency matrix of the directed line graph. Commented Mar 4, 2016 at 14:33
• Can't you just index the matrix $L$ by the pairs of vertices, in which case you just have $L_{(x,y)(s,t)}$ is $1$ iff $y=s$? Commented Mar 7, 2016 at 21:13

The directed line graph matrix of a complete directed graph has $N^2$ entries. Let $r = (a-N) \mod (N-1)$ and $k = (a-N) / (N-1)$ (using integer division). Then we can write (indices start at $0$): $$L_{a,b} = \begin{cases} 1 & \text{if } a < N \text{ and } N+ a(N-1) \leq b < N+ (a+1)(N-1)\\ 1 & \text{if } a \geq N \text{ and } b < n \text{ and } ( (r<k \text{ and } b=r) \text{ or } (r \geq k \text{ and } b=r+1)) \\ 0 & \text{otherwise} \end{cases}$$ Any permutation on the vertices would also do, but this seems to be the most natural one (and is already quite a horrible expression).
To get this to work for a general (weigthed, directed) graph you can replace $1$ by the relevant $\mathcal I$ coefficient.