Pelabelan ajaib pada graph diperkenalkan pertama kali oleh Kotzig dan Rosa pada pertengahan tahun 1960 dengan nama magic valuation, yang merupakan pemetaan satu-satu yang membawa setiap elemen pada graph ke himpunan bilangan bulat positif. Pelabelan ajaib tersebut pada dasarnya merupakan pengembangan konsep bujur sangkar ajaib (magic square) dengan orde n yang didefinisikan sebagai matriks yang elemennya adalah bilangan bulat positif dari 1, 2, 3, ….., n2, sedemikian hingga jumlah bilangan bulat pada setiap baris, kolom dan diagonalnya adalah sama dengan k, dimana k disebut bilangan ajaib. Pelabelan ajaib pada graph sesungguhnya merupakan kajian pada keilmuan teori graph yang banyak diaplikasikan antara lain pada kristalografi, sinar x, radar, astronomi, sistem alat jaringan komunikasi, desain sirkuit dan teori koding. Dalam aplikasi teori koding, teori graph digunakan untuk mendesain kode nonperiodik, yang masalah ini berekuivalen dengan pelabelan ajaib graph.
Pelabelan ajaib pada graph sejauh ini memang belum banyak mendapat kajian, terutama pada jenis graph yang tidak terhubung, padahal topik ini menjadi keunikan sifat pelabelan graph karena mempunyai karakteristik tertentu, misalnya ditunjukkan dengan jumlah bilangan ajaib yang selalu sama untuk setiap rangkaian graph. Contohnya adalah pelabelan total sisi ajaib atau edge magic total labeling dan pelabelan super sisi ajaib atau super edge magic labeling pada graph mP2, dengan m bilangan asli ganjil.
Graph mP2, dengan m bilangan asli ganjil adalah graph tidak terhubung yang memiliki V(mP2) = {v1, v2, v3, ...., v2m-1, v2m} dan E(mP2) = {v1v2, v3 v4,...., v2m-1v2m}, maka pelabelan total sisi ajaib pada graph mP2, dengan m bilangan asli ganjil didefinisikan sebagai fungsi bijektif f dari V E ke {1, 2, 3, ....., }, sehingga untuk setiap sisi vivi+1 pada graph berlaku , dengan k konstanta. Sedangkan pelabelan super sisi ajaib pada graph mP2, dengan m bilangan asli ganjil didefinisikan sebagai edge magic total labeling yang memetakan V ke himpunan {1, 2, 3, …., }, sehingga untuk setiap sisi vivi+1 pada graph berlaku , dengan k konstanta. Sebagai suatu bentuk bagian dari keilmuan teori graph, kedua jenis pelabelan ini dapat dimaknai sebagai jumlah label sisi dan label titik yang terkait langsung dengan sisi adalah sama untuk setiap rangkaian graph.