Perpustakaan Digital ITB

Diberikan graf sederhana G dan k bilangan bulat positif, pangkat ke-k dari G, ditulis G^k, adalah graf yang diperoleh dari graf G dengan menambahkan sisi-sisi baru diantara sebarang pasangan titik yang memiliki jarak paling banyak k di G. Secara formal, G^k=(V (G),{xy?1 ?d_G (x,y)?k}). Graf lintasan P_m adalah barisan berganti antara titik dan sisi v_1,e_1,v_2,e_2,?,e_(m-1),v_m dengan tidak ada titik yang berulang dan elemen yang berdekatan berinsiden. Banyaknya sisi minimum dari graf n titik yang P_m^k -jenuh disebut bilangan jenuh, dinotasikan dengan sat(n,P_m^k). Dalam tesis ini disajikan beberapa syarat perlu dari graf-graf yang P_m^k-jenuh, dan juga disajikan nilai dari sat(n,P_m^k) untuk m = 4 dan m = 5.