STUDI DEKOMPOSISI BINTANG LINIER GRAF LOBSTER

isalkan G=(V,E) sebuah graf terhubung sederhana dengan n titik dan m sisi. Jika G_1,G_2,…,G_p adalah graf bagian terhubung dari G yang saling lepas dengan E(G)=E(G_1 )∪E(G_2 )∪E(G_3 )…E(G_P ), maka G_1,G_2,…,G_p dikatakan sebuah dekomposisi dari G. Dekomposisi (G_1,G_2,…,G_p) dari G dikatakan dekomposisi linier (DL) atau dekomposisi Aritmatika jika |E(G_1 ) |=a+(i-1)d untuk setiap i=1,2,3,…,p dan a,d∈Z. Jelas m=p/2[2a+(p-1)d]. Jika a=1 dan d=1, maka m=(p(p+1))/2. Sehingga, Dekomposisi Linier merupakan sebuah Dekomposisi Monoton Kontinu (DMK) berupa barisan segitiga. Jika a=1 dan d=2 maka |E(G_i ) |=1+2(i-1)=2i-1,∀i,1≤i≤p. Sehingga, banyak sisi dari (G_1,G_2,…,G_p) adalah barisan p bilangan ganjil pertama. Akibatnya, |E(G_1 ) |=m=p^2. Dekomposisi Bintang Linier graf Lobster akan menghasilkan suatu graf bagian baru yakni graf bintang dengan beberapa teorema yang berdasarkan diameter graf lobster.