SATURATION NUMBER FOR POWER OF PATHS

• Main Author: Nursyahida, Salwa
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/44540
• Institution: Institut Teknologi Bandung

Given a simple graph G and k a positive integer, the k-th power of G, denoted by G^k, is a graph obtained from G by adding new edges between any pair of vertices at distance at most k in G; formally, , G^k=(V (G),{xy?1 ?d_G (x,y)?k}). A path graph P_m is a non-empty graph of the form V (P_m) =?{v?_1,v_2,?,v_m} dan E(Pm)={v_1 v_2,v_2 v_3,?,v_(m-1) v_m} where the v_i are all distinct. The minimum size of a P_m^k-saturated graph on n vertices is called a saturation number forP_m^k, denoted sat(n,P_m^k). In this thesis we derived some necessary condition of P_m^k-saturated graphs, and we also determined the value of sat(n,P_m^k) for m = 4 and m = 5