PELABELAN TOTAL SISI AJAIB SUPER (TSAS) PADA GABUNGAN GRAF BINTANG GANDA DAN LINTASAN ABSTRACT

Online Jurnal of Natural Science, Vol. 2 (1): 1-10 Maret 2013

ISSN: 2338-0950

PELABELAN TOTAL SISI AJAIB SUPER (TSAS) PADA GABUNGAN GRAF BINTANG GANDA DAN LINTASAN I W. Sudarsana1, Noviana2, S. Musdalifah3 dan A. A. Kasim4 Combinatorial and Applied Mathematics Research Group, Tadulako University Jalan Sukarno-Hatta Km. 9 Palu 94118, Indonesia

ABSTRACT An edge-magic total (EMT) labeling on a graph G(V,E) with the vertex set V and the edge set E, where |V| = p and |E| = q, is a bijective function λ: V ∪ E → {1, 2, 3, ..., p + q} with the property that for each edge (xy) of G, λ(x) + λ(xy) + λ(y) = k, for a fixed positive integer k. The labeling λ is called a super edge magic total (SEMT) if it has the property that for each vertex obtain the smallest label, 𝜆(V) = {1, 2, ..., p}. A graph G(V,E) is called EMT (SEMT) if there exists an EMT (SEMT) labeling on G. Study on SEMT labeling for the union of stars and paths initiated by Figueroa-Centeno et al. [2] with graph form S𝑛 + 1 ∪ P𝑛 . Furthermore, an investigation will be conducted on SEMT labeling of double stars and path, that are 2P𝑛 ∪ S𝑛 + 1, 𝑛 − 1 ; 2P𝑛 ∪ S𝑛 +3, 𝑛 −3 ; P𝑛 ∪ 2S𝑛 + 1, 𝑛 − 1 and P𝑛 ∪2S𝑛 +3, 𝑛 −3 . We 2

2

2

2

2

2

2

2

obtain that the graphs presented above are SEMT with the magic constants k 15𝑛 15𝑛+5 15𝑛 15𝑛+7 = 2 + 1, 2 , 2 + 2, and 2 , respectively. Keywords and Phrases: Double Stars, EMT, Path, SEMT.

ABSTRAK Pelabelan total-sisi ajaib (TSA) pada graf G(V,E) dengan himpunan titik V(G), notasi singkat V, dan himpunan sisi E(G), notasi singkat E, dengan |V| = p dan |E| = q adalah pemetaan bijektif 𝜆: V ∪ E →{1, 2, 3, …, p + q} yang mempunyai sifat bahwa untuk setiap sisi (xy) di G berlaku, λ(x) + λ(xy) + λ(y) = k, untuk suatu bilangan bulat positif k. Pelabelan λ dikatakan total sisi ajaib super (TSAS) jika mempunyai sifat bahwa setiap titik memperoleh label terkecil, λ(V) = {1,2,....,p}. Sebuah graf G(V,E) dikatakan TSA (TSAS) jika terdapat pelabelan TSA (TSAS) pada graf tersebut. Studi tentang pelabelan TSAS untuk gabungan graf bintang dan lintasan di awali oleh FigueroaCenteno et al. [2] dengan bentuk graf S𝑛 + 1 ∪ P𝑛 . Selanjutnya, akan dilakukan investigasi pelabelan TSAS pada gabungan graf bintang ganda dan lintasan, yaitu 2P𝑛 ∪ S𝑛 + 1, 𝑛 − 1 , 2P𝑛 ∪ S𝑛 +3, 𝑛 −3 , P𝑛 ∪2S𝑛 + 1, 𝑛 − 1 , dan 2

1

2

2

2

2

2

2

coresponding author : [email protected], [email protected], 3 [email protected], [email protected]


P𝑛 ∪2S𝑛 +3, 2

𝑛 −3 2

ISSN: 2338-0950

. Hasil yang diperoleh adalah semua graf tersebut di atas

merupakan TSAS dengan masing-masing memiliki konstanta ajaib k = 15𝑛 15𝑛+5 15𝑛 15𝑛+7 + 1, 2 , 2 + 2, dan 2 . 2 Kata Kunci : Bintang Ganda, Lintasan, TSA, TSAS. dan pelabelan total titik ajaib super. Sedangkan

I. PENDAHULUAN Pelabelan

graf

pertama

untuk

pelabelan

yang

kali

berhubungan dengan magic value pertama

diperkenalkan oleh Sedláček [5] dan

kali diperkenalkan oleh Kotzig dan Rosa

Stewart [6]. Pelabelan graf merupakan

[4]. Sejak saat itu hingga kini penelitian

suatu topik dalam teori graf yang saat ini

mengenai pelabelan sisi ajaib (edge magic

mendapat

banyak

labeling) masih hangat untuk diteliti.

memiliki

aplikasi

perhatian dalam

karena

kriptografi.

Penelitian

mengenai

pelabelan

Pelabelan merupakan fungsi atau pemetaan

ajaib pada graf terus berkembang, yang

dari unsur-unsur pada suatu graf yang

kemudian Enomoto et al. [1] mengkaji dan

berupa titik, sisi, atau titik dan sisi ke

memperkenalkan istilah pelabelan total sisi

bilangan bulat positif. Pada prinsipnya,

ajaib super (TSAS). Pada paper Enomoto

pelabelan graf merupakan pemberian nilai

et al. [1] tersebut dipaparkan dugaan

(label) pada titik, sisi, atau titik dan sisi.

bahwa semua graf pohon adalah TSAS.

Pelabelan yang sering digunakan yaitu

Dugaan ini belum terjawab kebenarannya

pelabelan

dan

hingga sekarang dan merupakan motivasi

palabelan total (titik dan sisi). Selanjutnya

terbesar bagi ilmuwan di bidang teori graf

suatu

sebagai

untuk menjawab dugaan tersebut. Dugaan

pelabelan ajaib jika ada fungsi bijektif dari

ini berusaha dijawab oleh Sudarsana et al.

unsur-unsur pada graf yang berupa titik,

[8], namun masih berupa hasil yang

sisi, atau titik dan sisi sehingga dapat

parsial. Pada penelitian ini, akan dikaji

menghasilkan suatu konstanta k yang

pelabelan TSAS pada gabungan graf

disebut dengan nilai ajaib (magic value).

bintang ganda dan lintasan. Walaupun

Pelabelan ajaib yang ada diantaranya

penelitian ini tidak berkaitan langsung

pelabelan total sisi-ajaib, pelabelan total

dengan dugaan tersebut tetapi memiliki

sisi-ajaib super, pelabelan total titik-ajaib,

nilai originalitas karena belum ada yang

titik,

pelabelan

pelabelan

dikatakan

sisi,

Pelabelan Total Sisi Ajaib Super (TSAS) Pada Gabungan Graf Bintang Ganda dan Lintasan (Sudarsana et al.) 2


ISSN: 2338-0950

mengerjakannya. Ini di dasari atas hasil

G(V,E) dengan konstanta ajaib k dan

survey dalam Gallian [3], bahwa gabungan

pelabelan λ′ di definisikan seperti berikut: λ′(𝑣𝑖 ) = p + 1 -

graf bintang ganda dan lintasan masih menjadi masalah terbuka.

λ(𝑣𝑖 ), ∀𝑣𝑖 ∈ V, dan λ′(x) = 2p + q +

II. HASIL TERDAHULU Sebelum disajikan hasil penelitian ini, terlebih dahulu diberikan teoremateorema penting yang telah ditemukan

1 - λ(x), ∀x ∈ E, maka λ′ adalah pelabelan TSAS dengan konstanta ajaib k′ = 4p + q + 3 – k. Pelabelan λ′ pada Teorema 2.2.

sebelumnya yang akan digunakan untuk membuktikan hasil baru dalam penelitian ini. Teorema-teorema tersebut adalah:

diatas dikatakan pelabelan dual super dari λ pada G dengan k′ = 4p + q + 3 – k (Sudarsana et al. [7]).

Teorema 2.1. Misalkan 𝜆 adalah pelabelan TSA pada graf G(V,E) dengan banyak titik

III. HASIL DAN PEMBAHASAN

adalah p dan banyak sisi adalah q.

Berikut adalah hasil-hasil baru

Pelabelan dual λ′ dari λ didefinisikan

yang diperoleh dalam penelitian ini. Hasil-

sebagai berikut:

hasil baru tersebut tersaji dalam sub-sub

λ′(𝑣𝑖 ) = M − λ(𝑣𝑖 ), ∀𝑣𝑖 ∈ V, dan λ′(x) = M − λ(x), ∀x ∈ E

bahasan berikut. 3.1. Graf 2𝐏𝒏 ∪ 𝐒𝒏+ 𝟏, 𝟐

dimana M = 𝑝 + 𝑞 + 1. Jika λ adalah pelabelan TSA dengan konstanta ajaib k, maka pelabelan λ′ adalah juga TSA dengan konstanta ajaib k′ = 3𝑀 − 𝑘. Pelabelan λ′ pada teorema diatas

Pada pelabelan S𝑛 + 1, 2

𝑛 −1 2

dan S𝑛 + 1,

dengan k′ = 3M – k (Wallis et al. [9]).

berikut.

2

𝑛 −1 2

bagian

ini,

TSAS

pada

akan graf

dibahas 2P𝑛 ∪

untuk n ≥ 4 genap. Notasi titik

sisi

dikatakan pelabelan dual dari λ pada G

𝒏 −𝟏 𝟐

pada

disajikan

graf pada

2P𝑛 ∪

Gambar

Teorema 2.2. Misalkan G(V,E) adalah graf yang memuat p titik dan q sisi adalah TSAS. Jika 𝜆 adalah pelabelan TSAS dari


1

Online Jurnal of Natural Science, Vol. 2 (1): 1-10 Maret 2013 v1,1

v2,1 e1,1

v1,2

v3,1

v2,2 e1,2

v6,1

e4,1

v3,2

v7,1 e6,1

e5,1 v5,2

v4,2 e3,2

e2,2

v5,1

v4,1 e3,1

e2,1

v6,2

e4,2

v8,1

v7,2 e6,2

e5,2

v8,2

v n  4 ,3

...e

 4 ,3

3.1.1.

Graf

S𝑛 + 1,

vn,2 n-1,2

2

𝑛 2

− 1 adalah

vn,3

15𝑛 2

2P𝑛

TSAS

+ 1, untuk n

…

≥ 4 genap.

en-1,3

2

 1,3

e6,3 e4,3 e5,3

Bukti:

v n  1,3

...

…

en

2

Pandang notasi titik dan sisi pada

v6,3

v3,3

v5,3

v4,3

Gambar 1: Penotasian titik dan sisi pada graf 2P𝑛 ∪ S𝑛 + 1, 𝑛 − 1 2

Berdasarkan Gambar 1 di atas, dapat

graf 2P𝑛 ∪ S𝑛 + 1, 2

𝑛 −1 2

dalam persamaan

(1). Berikan label pada titik dan sisinya dengan cara berikut:

dinotasikan himpunan titik dan sisi graf 2P𝑛 ∪ S𝑛 + 1, 2

𝑛 2

2

sebagai berikut :

−1

V(2P𝑛 ∪ S𝑛 + 1,

𝑛 2

= {𝑣𝑖,𝑗 | 1≤ j ≤ 3,

−1 )

1≤ i ≤ n} E(2P𝑛 ∪ S𝑛 + 1, 2

𝑛 2

−1 )

= {𝑒𝑖,𝑗 | 1≤ j ≤ 3, 1≤

i ≤ n - 1}, dimana 𝑒𝑖,1 = 𝑣𝑖,1 𝑣𝑖+1,1 , 1≤ i ≤ n - 1 𝑒𝑖,2 = 𝑣𝑖,2 𝑣𝑖+1,2 , 1≤ i ≤ n – 1 𝑛

𝑣𝑖,3 𝑣𝑛 + 2,3 , 1≤ i ≤ 2 + 1 2

𝑒𝑖,3 = 𝑣𝑛 + 1,3 𝑣𝑖+1,3 , 2

𝑛 2

+2 ≤ i ≤ n– 1

…………….................... (1) Pelabelan TSAS untuk graf 2P𝑛 ∪ S𝑛 + 1, 2

𝑛 2

∪

2

e2,3

2

Teorema

.

2

e n  2 ,3

v1,3

e3,3

v11,2 e10,2

vn,1 n-1,1

dengan k =

..

en

2

v2,3

v10,2 e9,2

...e

2

en  3 ,3

2

v9,2

v11,1 e10,1

v n  5 ,3

2

2

e1,3

v10,1 e9,1

e8,2

e7,2

v n  3 ,3

vn  2 ,3

v9,1 e8,1

e7,1

ISSN: 2338-0950

− 1 dengan

n ≥ 4 genap disajikan

dalam teorema berikut.



ISSN: 2338-0950

v2,1 e1,1

v1,2

S𝑛 + 1, 2

𝑛 −1 2

demikian,

graf

∪

2P𝑛 15n

adalah TSAS dengan k =

2

e3,1

e2,1 v2,2

e1,2

v5,1

v4,1

v3,2

e4,1

e3,2

e2,2

v7,1

v6,2

v7,2

e5,1 v5,2

v4,2

v6,1

e4,2

vn  3

2

2

S𝑛 + 1,

𝑛 −1 2

𝑘′ =

21𝑛 2

2

− 7, untuk n ≥ 4

Akibat

3.1.2. S𝑛 + 1, 2

Graf 𝑛 −1 2

adalah

dengan 𝑘 ′ =

15𝑛 2

2P𝑛 ∪ TSAS

− 1, untuk n ≥

e3,3

v2,3

3.2. Graf 2𝑷𝒏 ∪ 𝑺𝒏+𝟑, 𝟐

e6,3

bagian

ini,

2

𝑛 −3 2

untuk n ≥ 5 ganjil. Penotasian titik dan sisi pada graf 2P𝑛 ∪ S𝑛 +3, 2

𝑛 −3 2

3,3

vn,3

vn  3 2

,3

v7,3

Gambar 2: Penotasian titik dan sisi pada graf 2P𝑛 ∪ S𝑛 +3, 𝑛 −3 2

Berdasarkan gambar di atas, dapat dinotasikan himpunan titik dan sisi graf 2P𝑛 ∪ S𝑛 +3,

𝑛 −3 2

sebagai berikut :

𝑛 −3 2

) = {𝑣𝑖,𝑗 | 1≤ j ≤ 3, 1≤ i

≤ n}

dibahas

pelabelan TSAS pada graf 2P𝑛 ∪ S𝑛 +3,

2

v5,3

v4,3

2

akan

vn,2

n-1,2

v6,3

v3,3

V(2P𝑛 ∪ S𝑛 +3,

𝒏−𝟑 𝟐

...e

e4,3 e5,3

2

4 genap.

Pada

e7,3

2

genap.

e11,2

n-1,1

v12,2

en-1,3

e n  3 ,3 e2,3

adalah TSA dengan

e10,2

vn,1

 1,3

…

Teorema 2.2., diperoleh akibat berikut : 2P𝑛 ∪

 2,3

e9,2

e11,1 v11,2

...e

e1,3 v1,3

Graf

2

e10,1 v10,2

v12,1

…

vn  3  1,3 en  3

2

e9,1

v11,1

vn  3  4 , 3

 3 ,3

en3

en  3

Menggunakan Teorema 2.1. dan

2

2

 2 ,3

v10,1

v9,2 e8,2

e7,2

vn  3

+

2

3.1.1.

v8,2

e6,2

e5,2

v9,1 e8,1

e7,1

1, untuk n ≥ 4 genap.

Akibat

v8,1

…

Dengan

v3,1

…

v1,1

E(2P𝑛 ∪ S𝑛 +3, 2

𝑛 −3 2

) = {𝑒𝑖,𝑗 | 1≤ j ≤ 3, 1≤ i

≤ n - 1}, dimana

disajikan dalam

Gambar 2 berikut :



ISSN: 2338-0950

…………………………….(2) Pelabelan TSAS untuk graf 2P𝑛 ∪ S𝑛 +3, 2

𝑛 −3 2

dengan n ≥ 5 ganjil disajikan

dalam teorema berikut. Graf 2P𝑛 ∪ S𝑛 +3,

Teorema 3.2.1.

2

𝑛 −3 2

adalah TSAS dengan k = 15𝑛 +5 2

, untuk n ≥ 5 ganjil.

Bukti: Dengan

Pandang notasi titik dan sisi pada graf 2P𝑛 ∪ S𝑛 +3, 2

𝑛 −3 2

dalam persamaan (2).

Berikan label pada titik dan sisinya dengan

S𝑛 +3, 2

𝑛 −3 2

demikian,

2P𝑛 ∪

graf


15𝑛+5 2

,

untuk n ≥ 5 ganjil. Menggunakan Teorema 2.1. dan

cara :

Teorema 2.2., diperoleh akibat berikut : Akibat 3.2.1. Graf 2P𝑛 ∪ S𝑛 +3 , 2

21𝑛−17

TSA dengan 𝑘 ′ =

2

𝑛 −3 2

adalah

, untuk n ≥ 5

ganjil. Akibat 3.2.2. Graf 2P𝑛 ∪ S𝑛 +3 , 2

15𝑛− 5

TSAS dengan 𝑘 ′ =

2

𝑛 −3 2

adalah

, untuk n ≥ 5

ganjil. 3.3. Graf 𝐏𝒏 ∪ 𝟐𝐒𝒏+ 𝟏, 𝟐

Pada Dengan label tersebut diperoleh :

𝒏 −𝟏 𝟐

bagian

ini,

pelabelan

TSAS

pada

2S𝑛 + 1,

untuk n ≥ 4 genap. Gambar 2

2

𝑛 −1 2

akan graf

dibahas P𝑛 ∪

memperlihatkan penotasian titik dan sisi pada graf P𝑛 ∪ 2S𝑛 + 1, 2

𝑛 −1 2

.


Online Jurnal of Natural Science, Vol. 2 (1): 1-10 Maret 2013 vn

en 2

 2 ,1

2

en 2

e1,1

e6,1

e3,1

 3 ,1

vn vn 2

2

2

en

2

 4,2

2  3,2

 1, 2

e6,2 e5,2

e4,2

 5,2

… …

vn,2

en-1,2

vn 2

e3,2

vn 2

… …

en

e2,2 v2,2

 1 ,1

 2,2

2

v1,2

2

 3 ,2

en

e1,2

vn,1

en-1,1

 4 ,2

en

 2 ,2

…

v5,1

v4,1

2

2

…

v6,1

v3,1

vn

 4 ,1

vn

e5,1

e4,1

 5 ,1

 2 ,1

 1 ,1

2

e2,1

en

… …

en

v1,1

v2,1

2

 3 ,1

2

vn

vn

 4 ,1

2

vn

ISSN: 2338-0950

𝑒𝑖,3 = 𝑣𝑖,3 𝑣𝑖+1,3 , 1≤ i ≤ n - 1………… (3)  1,2

v6,2

v3,2

Pelabelan

v5,2

v4,2

2S𝑛 + 1, 2

v1,3

v2,3 e1,3

v3,3 e2,3

v5,3

v4,3 e3,3

e4,3

v6,3

v7,3 e6,3

e5,3

v8,3 e7,3

v9,3 e8,3

v10,3 e9,3

v11,3 e10,3

...e

vn,3

𝑛 2

TSAS −1

untuk

graf

dengan n ≥ 4 genap disajikan


n-1,3

Teorema 3.3.1. Graf P𝑛 ∪ 2S𝑛 + 1, 2

Gambar 3: Penotasian titik dan sisi pada graf P𝑛 ∪ 2S𝑛 + 1, 𝑛 − 1 2

15𝑛 2

Berdasarkan gambar di atas, dapat dinotasikan himpunan titik dan sisi dari 2

𝑛 2

−1

sebagai berikut :

2

𝑛 2

−1 )

−1

+ 2, untuk n ≥ 4 genap.

Bukti: Pandang notasi titik dan sisi pada graf 2P𝑛 ∪ S𝑛 + 1, 2

V (P𝑛 ∪ 2S𝑛 + 1,

𝑛 2


2

graf P𝑛 ∪ 2S𝑛 + 1,

P𝑛 ∪

𝑛 −1 2

dalam persamaan

(3). Berikan label pada titik dan sisinya dengan cara:

= {𝑣𝑖,𝑗 | 1≤ j ≤ 3, 1≤ i ≤ n} E (P𝑛 ∪ 2S𝑛 + 1,

−1 )

3𝑖 − 2, j = 1, 1≤ i ≤ n

= {𝑒𝑖,𝑗 | 1≤ j ≤ 3, 1≤ i ≤ n - 1}, dimana

3𝑖 − 1, j = 2, 1≤ i ≤ n

2

𝑛 2

λ (𝑣𝑖,𝑗 ) = 3𝑖− 1 2

+ 2, j = 3, 1≤ i ≤ n – 1; i ganjil

3𝑛+ 3𝑖 2

, j = 3, 1≤ i ≤ n; i genap


Online Jurnal of Natural Science, Vol. 2 (1): 1-10 Maret 2013 6n – 3i, j = 1, 1≤ i ≤ n – 1 λ (𝑒𝑖,𝑗 ) =

ISSN: 2338-0950

Akibat

3.3.2. 2S𝑛 + 1,

6n – 3𝑖 − 2, j = 2, 1≤ i ≤ n – 1

+ 1;

2

2

2

− 2, untuk n ≥

2

𝒏−𝟑 𝟐

𝟐

𝑛

λ (𝑣𝑖,1 ) + λ (𝑒𝑖,1 ) + λ (𝑣𝑛 + 2,1 ), 1≤ i ≤ 𝑛

TSAS

4 genap. 3.4. Graf 𝐏𝒏 ∪ 𝟐𝐒𝒏+𝟑,

2

15𝑛

dengan 𝑘 ′ =

Dengan label tersebut di atas diperoleh :

λ (𝑣𝑛 + 1,1 ) + λ (𝑒𝑖,1 ) + λ (𝑣𝑖+1,1 ),

∪

− 1 adalah

𝑛 2

2

6n – 3i − 1, j = 3, 1≤ i ≤ n – 1

P𝑛

Graf

+ 2≤i≤n−1

Pada

bagian

ini,

akan

dibahas

pelabelan TSAS pada graf P𝑛 ∪ 2S𝑛 +3,

𝑛 −3 2

2

λ (𝑣𝑛 + 1,2 ) + λ (𝑒𝑖,2 ) + λ (𝑣𝑖+1,2 ), 2

𝑛 2

+ 1;

2

+ 2≤i≤n−1

untuk

≥

n

5

𝑛 −3 2

2

2

2

 3  1 ,1 2

e1,1

+2

en  3 2

…

15𝑛

3( + 1) − 2 + 6n – 3i + 3(i + 1 ) – 2 =

2

vn

𝑛

v1,1

en

e2,1

𝑛

15𝑛

2

2

3𝑖 − 1 + 6n – 3i - 2 + 3( + 2 ) – 1 =

k=

+2

e3,1

v2,1

15𝑛

2

2

3( + 1 ) − 1 + 6n – 3i - 2 + 3(i + 1) – 1 =

2

+ 2 + 6n – 3i – 1 +

3𝑛+ 3(𝑖+1) 2

=

15𝑛 2

+2

2S𝑛 + 1, 2

15𝑛 2

𝑛 −1 2

en  3 2  1, 2

en

v1,2

en

Teorema 2.2. diperoleh akibat berikut: 3.3.1. 2S𝑛 + 1, 2

P𝑛

Graf 𝑛 2

− 1 adalah

dengan 𝑘 ′ =

21𝑛 2

∪

v2,3 e1,3

v3,3 e2,3

vn  3 2

,2

v7,2

v6,2

v5,3

v4,3 e3,3

vn,2

v5,2

v4,2

v1,3

 3,2

 4,2

e5,2

v3,2

dengan menggunakan Teorema 2.1. dan

2

 2,2

e6,2 e4,2

2

en3

 3 ,2 2

e7,2 e3,2

v2,2

vn  3

 3  3,2 2

en-1,2

e2,2


,1

 3  1, 2 2

…

∪

+ 2, untuk n ≥ 4 genap. Selanjutnya,

Akibat

 3  2 ,2 2

+2

P𝑛

3

v7,1

vn

2

graf

 2

v6,1

vn  3

demikian,

vn

 3 ,1 2

v5,1

v4,1

e1,2

Dengan

vn,1

e5,1

vn

3𝑖− 1

3,1

en-1,1

e6,1 e4,1

2

 2,1

 4 ,1

 1,1

e7,1

v3,1

𝑛

e n 3

en  3

…

2

+2

2

…

2

15𝑛

vn  3

 3  3 ,1 2

 3  2 ,1 2

…

𝑛

4

. vn

vn

3𝑖 − 2 + 6n – 3i + 3( + 2 ) – 2 =

Gambar

menampilkan penotasian titik dan sisi dari graf P𝑛 ∪ 2S𝑛 +3,

λ (𝑣𝑖,𝑗 ) + λ (𝑒𝑖,𝑗 ) + λ (𝑣𝑖+1,𝑗 ), j = 3, 1≤ i ≤ n – 1

ganjil.

…

𝑛

2

…

λ (𝑣𝑖,2 ) + λ (𝑒𝑖,2 ) + λ (𝑣𝑛 + 2,2 ), 1≤ i ≤

…

k=

e4,3

v6,3 e5,3

v7,3 e6,3

v8,3 e7,3

v9,3 e8,3

v10,3 e9,3

v11,3 e10,3

e11,3

v12,3

...e

Gambar 4: Penotasian titik dan sisi pada graf P𝑛 ∪ 2S𝑛 +3, 𝑛 −3 2

2

TSA

− 8, untuk n

≥ 4 genap. Pelabelan Total Sisi Ajaib Super (TSAS) Pada Gabungan Graf Bintang Ganda dan Lintasan (Sudarsana et al.) 8

vn,3

n-1,3


Berdasarkan gambar di atas, dapat dinotasikan himpunan titik dan sisi graf P𝑛 ∪ 2S𝑛 +3, 2

cara : 3𝑖 − 2, j = 1, 1≤ i ≤ n

𝑛 −3 2

) = {𝑣𝑖,𝑗 | 1≤ j ≤ 3, 1≤ i ≤ n}

E(P𝑛 ∪ 2S𝑛 +3,

𝑛 −3 2

) = {𝑒𝑖,𝑗 | 1≤ j ≤ 3, 1≤ i ≤ n - 1},

2

Berikan label pada titik dan sisinya dengan

sebagai berikut :

𝑛 −3 2

V(P𝑛 ∪ 2S𝑛 +3, 2

ISSN: 2338-0950

3𝑖 − 1, j = 2, 1≤ i ≤ n λ (𝑣𝑖,𝑗 ) = 3𝑖− 1

dimana :

2

𝑣𝑖,1 𝑣𝑛 +3 +1,1 , 1 ≤ i ≤ 2

𝑛+3 2

+ 2, j = 3, 1≤ i ≤ n; i ganjil

3𝑛+ 3𝑖+ 1 2

+ 1, j = 3, 1≤ i ≤ n-1; i genap

𝑒𝑖,1 = 𝑛+3 2

𝑣𝑛 +3,1 𝑣𝑖+1,1 , 2

+1≤i≤n– 1

𝑣𝑖,2 𝑣𝑛 +3+1,2 , 1 ≤ i ≤ 2

6n – 3i, j = 1, 1≤ i ≤ n – 1 λ (𝑒𝑖,𝑗 ) =

𝑛 +3

6n – 3𝑖 − 2, j = 2, 1≤ i ≤ n – 1

2

6n – 3i − 1, j = 3, 1≤ i ≤ n – 1

𝑒𝑖,2 = 𝑣𝑛 +3,2 𝑣𝑖+1,2 ,

𝑛+3

2

2

Dengan label tersebut diperoleh :

+1≤i≤n– 1

λ (𝑣𝑖,1 ) + λ (𝑒𝑖,1 ) + λ (𝑣𝑛 +3+ 1,1 ), 1≤ i ≤

𝑒𝑖,3 = 𝑣𝑖,3 𝑣𝑖+1,3 , 1≤ i ≤ n - 1……… (4)

λ (𝑣𝑛 +3,1 ) + λ (𝑒𝑖,1 ) + λ (𝑣𝑖+1,1 ),

𝑛+3 2

2

Pelabelan TSAS untuk graf P𝑛 ∪ 2S𝑛 +3,

𝑛 −3 2

2

k=

λ (𝑣𝑛 +3,2 ) + λ (𝑒𝑖,2 ) + λ (𝑣𝑖+1,2 ),

𝑛+3 2


𝑛 +3 2

Graf P𝑛 ∪ 2S𝑛 +3, 2

3(

𝑛 −3 2

adalah TSAS dengan k = , untuk n ≥ 5 ganjil.

Bukti:

k=

𝑛+3 2

+1≤i≤n−1

+1)–2=

15𝑛+7

) − 2 + 6n – 3i + 3(𝑖 + 1) – 2 =

15𝑛+7

𝑛 +3 2

3𝑖 − 1 + 6n – 3i - 2 + 3( 3(

𝑛+3 2

3𝑖− 1 2

𝑛+3 2

2

+1)–1=

) − 1 + 6𝑛 – 3𝑖 - 2 + 3(𝑖 + 1) – 1 =

+ 2 + 6n – 3i – 1 +

2

3𝑛+ 3 𝑖+1 +1 2

15𝑛+7 2

15𝑛 +7

+1=

2 15𝑛+7

Pandang notasi titik dan sisi pada graf P𝑛 ∪ 2S𝑛 +3, 2

𝑛 −3 2

;

λ (𝑣𝑖,𝑗 ) + λ (𝑒𝑖,𝑗 ) + λ (𝑣𝑖+1,𝑗 ), j = 3, 1≤ i ≤ n – 1

3𝑖 − 2 + 6n – 3i + 3(

2

;

+1≤i≤n−1

λ (𝑣𝑖,2 ) + λ (𝑒𝑖,2 ) + λ (𝑣𝑛 +3+ 1,2 ), 1≤ i ≤

2

15𝑛+7

2

2

dengan n ≥ 5 ganjil disajikan

Teorema 3.4.1.

𝑛+3

2

dalam persamaan (4).


2


Dengan 2S𝑛 +3, 2

𝑛 −3 2

demikian,

graf


P𝑛 ∪ 15𝑛+7 2

,

ISSN: 2338-0950

Kotzig, A., and Rosa, A., 1970, Magic Valuations of Finite Graphs, Canad. Math. Bull, Vol. 13 : 451-461. [Sedláček, J., 1963, In : Theory of Graphs and Its Applications, Proc. Symp. Smolenice, Problem 27 : 163-169.

untuk n ≥ 5 ganjil. Menggunakan Teorema 1 dan 2,

Stewart, B. M., 1966, Magic Graph , Canad. J. Math, Vol. 18 : 1031-1059.

diperoleh akibat berikut : Akibat 3.4.1. Graf P𝑛 ∪ 2S𝑛 +3, 2

′

TSA dengan 𝑘 =

21𝑛−19 2

𝑛 −3 2

adalah

, untuk n ≥ 5

ganjil. Akibat 3.4.2. Graf P𝑛 ∪ 2S𝑛 +3, 2

TSAS dengan 𝑘 ′ =

15𝑛− 7 2

𝑛 −3 2

adalah

, untuk n ≥ 5

ganjil. DAFTAR PUSTAKA Enomoto, H., Lladó, A. S., Nakamigawa, T., and Ringel, G., 1998, Super Edge-Magic Graphs, SUT J. Math., Vol. 34, No. 2 : 105-109, (http://web.thu.edu.tw/wang/www/S EM_98.pdf), diakses 14 Desember 2011.

Sudarsana, I W., Assiyatun, H., Baskoro, E. T., and Ismaimuza, D., 2005, Creating New Super Edge-Magic Total Labelings from Old Ones, J. Combin. Math. Combin. Comput, Vol. 55 : 83-90. Sudarsana, I W., Baskoro, E. T., Ismaimuza, D., and Uttunggadewa, S., 2009, An Expansion Technique on Super Edge-Magic Total Graphs, ARS Combinatoria, Vol. 91 : 231241. Wallis, W. D., Baskoro, E. T., Miller, M., and Slamin, 2000, Edge-Magic Total Labelings, Australasian J. Combin., Vol. 22 : 177-190.

Figueroa-Centeno, R. M., Ichishima, R., and Muntaner-Batle, F. A., 2005, On Edge-Magic Labelings of Certain Disjoint Unions of Graphs, Australasian J. Combin., Vol. 32 : 225–242. Gallian, J. A., 2012, A Dynamic Survey of Graph Labelling, Electronic Journal of Combinatorics, Vol. 18, (http://www.emis.ams.org/journals/E JC/Survey/ds6. pdf), diakses 14 November 2012.


PELABELAN TOTAL SISI AJAIB SUPER (TSAS) PADA GABUNGAN GRAF BINTANG GANDA DAN LINTASAN ABSTRACT

Recommend Documents