Line digraph

Line digraph --- реберный орграф.

Given a digraph [math]\displaystyle{ G = (V,A) }[/math], the digraph [math]\displaystyle{ LG = (V(LG), A(LG)) }[/math] where each vertex represents an arc of [math]\displaystyle{ G }[/math], that is,

[math]\displaystyle{ V(LG) = \{uv|(u,v) \in A(G)\} }[/math]

is called a line digraph. A vertex [math]\displaystyle{ uv }[/math] is adjacent to a vertex [math]\displaystyle{ wz }[/math] if and only if [math]\displaystyle{ v = w }[/math], that is, whenever the arc [math]\displaystyle{ (u,v) }[/math] of [math]\displaystyle{ G }[/math] is adjacent to the arc [math]\displaystyle{ (w,z) }[/math]. The maximum and minimum out- and in-degrees of [math]\displaystyle{ LG }[/math] are equal to those of [math]\displaystyle{ G }[/math]. Therefore, if [math]\displaystyle{ G }[/math] is [math]\displaystyle{ d }[/math]-regular with the order [math]\displaystyle{ n }[/math], then [math]\displaystyle{ LG }[/math] is [math]\displaystyle{ d }[/math]-regular and has the order [math]\displaystyle{ dn }[/math]. If [math]\displaystyle{ G }[/math] is a strongly connected digraph different from a directed cycle, then the diameter of [math]\displaystyle{ LG }[/math] is the diameter of [math]\displaystyle{ G }[/math] plus one.