Bilangan Kromatik graf commuting dan noncommuting grup dihedral

INDONESIA:

Misal G grup berhingga dan X adalah subset dari G. Graf commuting C(G,X) adalah graf yang memiliki himpunan titik X dan dua titik berbeda akan terhubung langsung jika saling komutatif di G. Misal G grup non abelian dan Z(G) adalah center dari G. Graf noncommuting Γ_G adalah suatu graf yang mana titik-titiknya merupakan himpunan dari G\Z(G) dan dua titik x dan y terhubung langsung jika dan hanya jika xy≠yx.

Pewarnaan titik pada graf G adalah pemberian sebanyak k warna pada titik sehingga dua titik yang saling terhubung langsung tidak diberi warna yang sama. Sedangkan pewarnaan sisi pada graf G adalah dua sisi yang berasal dari titik yang sama diberi warna yang berbeda. Adapun bilangan terkecil k sehingga suatu graf dapat diberi k warna pada titik dan sisi inilah yang dinamakan bilangan kromatik.

Metode penelitian yang digunakan adalah studi kepustakaan dengan tahapan analisis yang diawali dengan menentukan elemen-elemen grup dihedral (D_2n) dengan 3≤n≤5 untuk graf commuting dan 3≤n≤8 untuk graf noncommuting, menggambarkan tabel Cayley dari grup dihedral, mencari elemen-elemen komutatif dan tidak komutatif, menggambarkan graf commuting (C(D_2n)) dan graf noncommuting (Γ(D_2n)) dari grup dihedral, mencari pola bilangan kromatik dari pewarnaan titik dan sisi, membangun konjektur, dan membuktikannya sebagai teorema. Adapun hasil penelitian ini sebagai berikut:

1.Bilangan kromatik dari pewarnaan titik graf commuting grup dihedral ...

2.Bilangan kromatik dari pewarnaan sisi graf commuting grup dihedral ...

3.Bilangan kromatik dari pewarnaan titik graf noncommuting grup dihedral ...

4.Bilangan kromatik dari pewarnaan sisi graf noncommuting grup dihedral ...

ENGLISH:

Let G finite group and X is a subset of G. Commuting graph C(G,X) is a graph that has a set of points X and two different vertices to be connected directly if each commutative in G. Let G non abelian group and Z(G) is a center of G. Noncommuting graph Γ(G,X) is a graph which the the vertex is a set of G∖Z(G) and two vertices x and y are adjacent if and only if xy≠yx.

The vertex colouring of G is giving k colour at the vertex, two vertices that are adjacent not given the same colour. Edge colouring of G is two edges that have common vertex are coloured with different colour. The smallest number k so that a graph can be coloured by assigning k colours to the vertex and edge called chromatic number.

The research method used in this research is literature study with analysis begins with determine the elements of the dihedral group 3≤n≤5 for commuting graph and 3≤n≤8 for noncommuting graph, create the Cayle’s table, determine commutative and noncommutative elements, draw commuting graph (C(D_2n )) and noncommuting graph (Γ(D_2n )) from dihedral group, determine the patterns of chromatic number from vertex and edge colouring, write the conjecture, and proof it to be theorem. The result of this research are:

1.Chromatic number from vertex colouring commuting graph of dihedral group ...

2.Chromatic number from edge colouring commuting graph of dihedral group ...

3.Chromatic number from vertex colouring noncommuting graph of dihedral group ...

4.Chromatic number from edge colouring noncommuting graph of dihedral group...