For a digraph D, let L (D) and S (D) denote its line digraph and subdivision digraph, respectively. The motivation of this paper is to solve the digraph equation L (S (D)) = S (L (D)). We show that L (S (D)) and S (L (D)) are cospectral if and only if D and L (D) have the same number of arcs. Further, we characterize the situation that L (S (D)) and S (L (D)) are isomorphic. Our approach introduces the new notion, the proper image D* of a digraph D, and a new type of connectedness for digraphs. The concept D* plays an important role in the main result of this paper. It is also useful in other aspects of the study of line digraphs. For example, L (D) is connected if and only if D* is connected; L (D) is functional (contrafunctional) if and only if D* is functional (contrafunctional). Some related results are also presented.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics