4
$\begingroup$

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$?

$\endgroup$
3
  • $\begingroup$ It is not clear to me what does "directed line graph of the complete digraph" means, could you please explain it a little bit? $\endgroup$
    – M.Badaoui
    Commented Mar 4, 2016 at 14:00
  • $\begingroup$ @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. $\endgroup$
    – draks ...
    Commented Mar 4, 2016 at 14:33
  • $\begingroup$ 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$? $\endgroup$
    – Graffitics
    Commented Mar 7, 2016 at 21:13

1 Answer 1

0
+50
$\begingroup$

I'm really not sure to understand what your question is, but this would be too long for a comment, so I will update this in case it's a blatant misunderstanding.

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.

$\endgroup$
2
  • $\begingroup$ Thanks for your time not really what I was looking for but since you were the only one participating you'll get the bounty... $\endgroup$
    – draks ...
    Commented Mar 7, 2016 at 17:23
  • $\begingroup$ @draks... Oh hell, I understand now, I understood "line graph" as incidence graph, hence the confusion... I'll look soon at your proper question, sorry about that. $\endgroup$
    – Graffitics
    Commented Mar 7, 2016 at 17:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .