Kekuatan Tak Reguler Sisi Total, Titik Total dan Total pada Beberapa Kelas Graf

DIARI INDRIATI, Prof. Dr. rer. nat. Widodo, M.S. ; Dr. rer. nat. Indah Emilia Wijayanti, M.Si. ; Dr. Kiki Ariyanti Sugeng

2016 | Disertasi | S3 Matematika

Misal G(V,E) selanjutnya disingkat G adalah graf sederhana (tidak memuat loop dan sisi paralel). Pelabelan suatu graf didefinisikan sebagai pemetaan yang membawa elemen-elemen graf ke bilangan-bilangan bulat positif atau non-negatif. Jika domain pemetaan adalah himpunan titik (V), maka pelabelan disebut pelabelan titik (vertex labeling), yaitu fungsi f dari V ke himpunan bilangan bulat non negatif. Jika domainnya adalah himpunan sisi (E), maka pelabelan disebut pelabelan sisi (edge labeling), yaitu fungsi f dari E ke himpunan bilangan bulat non negatif. Jika domainnya adalah himpunan titik maupun sisi (V union E) maka pelabelan disebut pelabelan total (total labeling), yaitu fungsi f dari V union E ke himpunan bilangan bulat non negatif. Suatu pelabelan-k total adalah pelabelan total f dari V union E ke himpunan bilangan bulat dari 1 sampai k. Pelabelan graf dapat dilakukan dengan cara mengaitkan jumlah label dengan elemen-elemen graf. Jumlah label ini dikenal sebagai bobot (weight) dari elemen graf. Misal diketahui pelabelan total f. Bobot titik x pada pelabelan total f didefinisikan sebagai wt(x) = f(x) + Sigma f(xy) sedangkan bobot sisi xy adalah wt(xy) = f(x) + f(xy) + f(y). Pemetaan f dari V union E ke {1,2, ..., k} disebut pelabelan-k total tak reguler sisi/titik (edge/ vertex irregular total k-labeling) pada G, jika bobot setiap pasang sisi/titik yang berbeda pada G tidak sama, yaitu f(x) + f(xy) + f(y) tidak sama dengan f(u) + f(uv) + f(v) untuk setiap dua sisi xy dan uv yang berbeda pada G. Kekuatan tak reguler sisi/titik total (total edge/ vertex irregularity strength) dari graf G dinotasikan dengan tes(G)/ tvs(G), didefinisikan sebagai bilangan bulat positif terkecil k sehingga G mempunyai pelabelan-k total tak reguler sisi/titik. Penelitian disertasi ini dimotivasi oleh adanya hasil untuk kekuatan tak reguler total pada graf-graf pohon (yaitu graf-graf acyclic) dengan memperhatikan banyaknya sisi atau titik daun. Dari itu muncul pemikiran bagaimana jika kekuatan tak reguler total ditentukan pada graf-graf cyclic dan dengan memperhatikan banyaknya sisi atau titik daun pula. Pada perkembangannya, jika tiap pasang sisi atau titik mempunyai bobot sisi dan bobot titik yang berbeda secara simultan, maka pelabelannya di sebut pelabelan-k total tak reguler total (totally irregular total k-labeling) pada G. Jenis pelabelan ini belum banyak dikaji orang dan hasil-hasil untuk graf-graf pohon maupun graf cyclic belum diperoleh nilai eksaknya. Oleh karena itu, untuk jenis pelabelan total ini, penulis mengawali mengkaji untuk graf-graf pohon terlebih dahulu dan sebagai langkah awal diselidiki pada graf caterpillar. Penentuan nilai eksak kekuatan tak reguler sisi, titik atau total dilakukan dengan cara menunjukkan nilai batas bawah maupun batas atas yang keduanya dibuktikan bernilai sama. Beberapa peneliti telah memperoleh batas bawah kekuatan tak reguler sisi, titik atau total untuk graf-graf pohon dengan memperhatikan banyak sisi daun ataupun graf-graf sebarang dengan memperhatikan derajat titik pada graf. Batas atas ditentukan dengan cara mengkonstruksi suatu pelabelan total sehingga diperoleh label terbesar seminimum mungkin. Dengan kedua langkah tersebut, diperoleh nilai untuk kekuatan tak reguler sisi, titik atau total pada graf. Sebagai validasi, bukti-bukti diberikan dalam bentuk teorema ataupun lemma. Pada penelitian ini telah diperoleh hasil-hasil untuk kekuatan tak reguler sisi atau titik pada graf-graf cyclic dan memperhatikan titik daun, yaitu pada graf-graf helm diperumum, gir diperumum, web diperumum, prisma diperumum dan korona graf dengan titik-titik terisolasi. Sedangkan hasil-hasil untuk kekuatan tak reguler total diperoleh pada graf-graf pohon (acyclic), dalam hal ini adalah graf caterpillar.

Let G(V, E) or G be a simple undirected graph (that is a graph without loops or parallel edges). A graph labeling is defined as a mapping that brings elements of the graph to the set of positive or non-negative integers. If the domain of the mapping is a vertex set (V), then a function is called vertex labeling. If the domain is an edge set (E), then the labeling is called edge labeling, and if the domain is the union of vertex and edge set (V union E) then the labeling is called total labeling. A total k-labeling is the total labeling f from V union E into {1,2,...,k} with k is an integer. Labeling of graph can be done by assigning numbers to the elements of the graph. The total of labels is known as a weight of graph elements. For example, in the total k-labeling f, the weights of vertex x is defined as wt(x) = f (x) + Sigma f(xy), while the weight of edge xy is defined as wt(xy) = f(x) + f(xy) + f(y). A mapping f from V union E into {1, 2, ..., k} is called edge (or vertex) irregular total k-labeling on G, if the weight of each pair of edges (or vertices) are distinct. Namely f (x) + f(xy) + f(y) not equal to f(u) + f(uv) + f(v) for any two different edges xy and uv on G, or f(x) + Sigma f(xy) not equal to f(u) + Sigma f(uv) for any two different vertices x and u in G. A total edge / vertex irregularity strength of a graph G, denoted by tes(G) / tvs(G)) is defined as the smallest positive integer k such that G has an edge / a vertex irregular total k -labeling. This research is motivated by the results of the total irregularity strength of tree (that is acyclic graph) by considering the number of leaves. From these facts, arose the idea how is the total irregularity strength can be obtained for cyclic graph by considering the number of leaves too. Furthermore, if each pair of both edges and vertices has a distinct weight simultaneously, then the labeling is called a totally irregular total k-labeling. A minimum k for which the labeling has a totally irregular total k-labeling is called a total irregularity strength and denoted by ts(G). This type of labeling has not been widely studied by researcher and the results for ts of tree or acyclic graph has not been obtained. Therefore, for this type of total labeling, the authors start doing research for tree graphs and as the initial step is for \emph{caterpillar} graphs. The determination of the exact value of total edge, vertex or total irregularity strength is by showing its lower bound and upper bound which are proven have the same value. Some researchers have obtained the lower bound of the total edge, total vertex or total irregularity strength for both tree (by considering the number of leaves) and any graphs (by observing the degree of any vertex on the graph). The upper bound is determined by constructing a labeling in order to obtain the minimum of the biggest labels. With these two steps, the exact value for total edge, total vertex, or total irregularity strength of the graph can be obtained. As a validation, the proof of these results are given in the form of theorems or lemmas. This research results consist of both total edge and total vertex irregularity strength of cyclic graph and also by considering the number of its leaves, such as generalized helm, generalized gear, generalized web, generalized prisma and corona of graph with isolated vertices. Other results for total irregularity strength of trees (in this type we have done for caterpillar).

Kata Kunci : graf cyclic, pelabelan tak reguler sisi/ titik/ total tak reguler, kekuatan tak reguler sisi/ titik/ total,