Suatu line digraph dari graf berarah adalah suatu graf berarah dengan simpul-simpul pada merupakan busur-busur berarah pada dan simpul bertetangga ke simpul pada jika dan hanya jika ujung dari busur merupakan pangkal dari busur pada . Menurut Wang dan Yuan (2005), suatu graf merupakan graf DNA jika dan hanya jika graf tersebut merupakan line digraph. Sehingga, jika diberikan sembarang graf, untuk mengetahui graf tersebut apakah merupakan graf DNA, dapat dilakukan dengan memeriksa apakah graf tersebut merupakan line digraph. Melalui penelitiannya, Syslo (1982) membuat suatu algoritma untuk mengidentifikasi apakah suatu graf merupakan line digraph dari suatu graf berarah. Beberapa tahun berikutnya, Blazewicz dkk. (1999) mendefinisikan pelabelan- dan mengidentifikasi bahwa suatu graf adalah line digraph jika dapat dilabel dengan pelabelan-. Dalam skripsi ini, dibahas mengenai modifikasi algoritma yang dibuat oleh Syslo sedemikian sehingga simpul graf yang dihasilkan algoritma tersebut memenuhi definisi pelabelan- untuk kemudian diterapkan dalam identifikasi line digraph jika diberikan sembarang graf berarah terhubung.

---

A line digraph of directed graph is a directed graph with the vertices in are the arcs in and vertex is adjacent to vertex in if and only if the head of the arc is the tail of the arc in . According to Wang and Yuan (2005), a graph is DNA graph if and only if the graph is a line digraph. So, if given an arbitrary graph, to find out whether the graph is DNA graph, can be done by checking whether the graph is a line digraph.

Syslo (1982) gave an algorithm to identify line digraph. The next few years, Blazewicz et al. (1999) defined an -labeling and identify that a graph is a line digraph if can be labeled by -labeling.

This reseacrh gives modification of the algorithm created by Syslo such that the algorithm satisfy the definition of -labeling and then be applied to identify line digraph, if given any connected directed graph.