Salah satu permasalahan dalam genetika adalah pencarian barisan lengkap DNA dari potongan – potongan pendek barisan DNA yang diberikan. Metode yang dapat digunakan untuk masalah ini adalah metode Sequencing by Hybridization yang mencari barisan lengkap DNA dengan memodelkannya menjadi masalah pencarian lintasan Hamilton pada graf DNA. Graf DNA adalah graf yang dibentuk dari potongan – potongan pendek barisan DNA dengan aturan tertentu. Pencarian lintasan Hamiton pada suatu graf membutuhkan waktu eksponensial sehingga pencarian barisan lengkap DNA dengan lintasan Hamilton juga membutuhkan waktu eksponensial. Untuk mengurangi waktu komputasi menjadi polinomial, graf DNA diubah menjadi graf baru yang disebut graf asal. Hal ini mengakibatkan pencarian lintasan Hamilton pada graf DNA berubah menjadi pencarian lintasan Euler pada graf asal. Graf DNA yang dibentuk dari spektrum DNA termasuk line digraph, yaitu adjoint dari suatu graf asal yang tidak memiliki busur sejajar. Dalam skripsi ini akan dibahas karakteristik sifat – sifat dari line digraph yaitu hubungan antara line digraph dan graf asalnya, termasuk di dalamnya sifat ketetanggaan pada adjoint, serta dari pelabelan pada suatu graf. Dari sisi pelabelan, ditunjukan bahwa line digraph termasuk dalam kelas ∞2 L yang nantinya akan digunakan dalam pembentukan algoritma pengenalan line digraph yang sekaligus dapat digunakan untuk membentuk graf asal dari suatu line digraph.