DEKOMPOSISI DARI GRAF LENGKAP  DENGAN

DECOMPOSITION OF COMPLETE GRAPH  WHERE

Graf  adalah graf sederhana. Dekomposisi graf  adalah koleksi subgraf takkosong dari , yang dinotasikan , sedemikian hingga  di mana suatu  subhimpunan dari  dan  merupakan partisi dari . Jika  adalah dekomposisi dari graf , maka  dapat dituliskan  di mana . Graf lengkap dengan  titik dengan , , dapat didekomposisi menjadi subgraf-subgraf yang masing-masing berupa  atau dapat dikatakan sebagai -dekomposisi. Selain itu, Graf lengkap dengan  titik dengan , , dapat didekomposisi menjadi subgraf lain yakni  atau dapat dikatakan dengan -dekomposisi. Graf lengkap dengan  titik dengan , , dapat didekomposisi menjadi subgraf-subgraf yang masing-masing berupa  atau dapat dikatakan sebagai -dekomposisi. Selain itu graf lengkap  juga dapat didekomposisi menjadi subgraf yang lain, yakni  atau dapat dikatakan sebagai -dekomposisi.

Kata kunci: Dekomposisi, Graf Lengkap.

Let  be a simple graph. A decomposition of a graph  is a collection of non-empty subgraphs of , denoted by ​, such that each , where  subset of , and ​ forms a partition of . That is, the edge sets are pairwise disjoint and their union equals . If  is a decomposition of , then  can be expressed as ​, where . Let ​ be the complete graph on  vertices, where . Then  admits a ​-decomposition is a decomposition into subgraphs isomorphic to the star  and it also admits a ​-decomposition is a decomposition into  pairwise disjoint edges (a perfect matching). Similarly, the complete graph on  vertices, ​, where , admits a ​-decomposition is a decomposition into subgraphs isomorphic to the star  and a ​-decomposition is decomposition into cycles of length .

Keywords: Decomposition, Complete Graph.