Beberapa Syarat Graf Tidak Bersahabat

Abstract

Misalkan G sebuah graf dengan himpunan titik G dilambangkan dengan V(G). Misalkan v sebuah titik di G. Persekitaran titik v di G, dilambangkan dengan N(v), adalah himpunan semua titik G yang berhubungan langsung dititik v. Misalkan S?V(G). Sebuah titik v?S dikatakan tidak bersahabat jika banyak titik persekitaran v di V(G)\S lebih dari atau sama dengan banyak titik perekitaran v di S. Dengan kata lain, |N(v)?V(G)\S|?|N(v)?S|. Sedangkan titik v dikatakan sangat tidak bersahabat apabila banyak titik persekitaran v di V(G)\S lebih besar dari banyaknya titik persekitaran v di S. Dengan kata lain, |N(v)?V(G)\S|>|N(v)?S|. Jika setiap titik v?S dan setiap titik u?V(G)\S adalah titik-titik yang tidak bersahabat maka (S,V(G)\S) dinamakan sebuah bipartisi tidak bersahabat dari graf G, dan G dikatakan graf tidak bersahabat. Begitu juga untuk setiap titik v?S dan setiap titik u?V(G)\S) dinamakan sebuah bipartisi sangat tidak bersahabat dari graf G, dan G dikatakan graf sangat tidak bersahabat.