Grafların numaralandırılması

Abstract

oz GRAFLARIN NUMARALANMASI Sevinç DÖNMEZ Balıkesir Üniversitesi, Fen Bilimleri Enstitüsü Matematik Eğitimi Anabilim Dalı (Yüksek Lisans Tezi/Tez Danışmanı :Prof. Dr. Mehmet ARISOY) Balıkesir, 2000 Buklesiz, katlı ayntsız, sonlu ve yönsüz tüm graflarm kümesi T olsun. Ayrıtlar kümesi, E={e1,e2,...,em}, m>2 ve tepeler kümesi de -.. V={vı,v2,...,vn}, n>3 olmak üzere T kümesine ait olan birleştirilmiş bir graf G=(V,E) sembolü ile gösterilsin. G=(V,E) grafının bir ayrıt numaralaması folsun. Eğer f fonksiyonu; Je->n ' le^f(e)şeklinde içine bir fonksiyon ve f ' in doğurduğu ; rV(G)->N lv->gf(v)= S f(e) eel(v) tepe numaralaması da içine bir fonksiyon ise bu durumda G=(V,E) grafi zayıf ters sihirlidir denir. G=(V,E) zayıf ters sihirli bir graf ve f(E)={l,2,...,m} şeklinde ise G grafı ters sihirlidir denir ve f fonksiyonuna da G grafinın ters sihirli numaralaması denir. Bu tezde bazı graflann ters sihirli, zayıf ters sihirli, asal sihirli, Mısırsal sihirli numaralamaları ve doğrusal Diophantine denklemler üzerinde durulmuştur. (a,d) ters sihirli graflann doğrusal Diophantine denklemleri çözümlenmiştir. Birinci bölümde tez içinde geçen bazı kavram ve tanımlar verilmiştir. İkinci bölümde zayıf ters sihirli, ters sihirli* Mısırsal sihirli graf tanımları ve bir G grafinın f ayrıt numaralamasının k-ile genişletilmişi sunulmuştur. Üçüncü bölümde bir G grafinın f ayrıt numaralamasının k-ile genişletilmişi ile ilgili bir takım teoremler ifade edilip, ispatlanmış ve örneklendirilmiştir. Dördüncü bölümde sihirli, süper sihirli, asal sihirli ve (a,d) ters sihirli graflar incelenmiş ve bu graflar örneklerle gösterilmiştir. Beşinci bölümde (a,d) ters sihirli graflann doğrusal Diophantine denklemleri ifade edilerek, bazı önerme ve teoremler ispat edilmiştir. Altıncı bölümde Pg,b paraşüt grafi sunularak, ters sihirli paraşüt graflar ile ilgili teoremler ifade ve ispat edilmiştir. Paraşüt graflann doğrusal Diophantine denklemleri üzerinde durulmuştur. Sonuç olarak graflann sihirli, ters sihirli, zayıf ters sihirli asal sihirli, süper sihirli, Mısırsal sihirli ve (a,d) ters sihirli numaralandınlmalan ifade edilmiş ve bunlara örnekler verilmiştir. Ayrıca (a,d) ters sihirli graflann ve bir Pg,b paraşüt grafinın doğrusal Diophantine denklemi açıklanmıştır. ANAHTAR SÖZCÜKLER : Graf/ Diophantine Denklem / Egyptian Graf. m

ABSTRACT LABELLINGS OF GRAPHS Sevinç DÖNMEZ Balıkesir University, Institute of Science, Department of Mathematics Education (M. Sc. Thesis/ Supervisor :Prof. Dr. Mehmet ARISOY) Balıkesir, TURKEY, 2000 Let T denote the set of all finite undirected graphs without loops and multiple edges. A connected graph which is belong to T has been shown as G=(V,E) with edge set E={ei,...,em},m>2. and vertex set, V={vi,...,vn},n>3. Let G=(V,E)er be a graph with edge labeling f. A connected graph G=(V,E)er is weakly antimagic iff there exists an injective mapping; `e->n, e->f(e), iv f -Asuch that the induced mapping gf by V(G)->N, gf = v->gf(v)= Zf(e) eel(v) is injective. A graph G=(V,E)er is antimagic iff G is weakly antimagic and f(E)={l,...,m}. In this case we call f an antimagic labeling of G. In this thesis, antimagic, weakly antimagic, prime magic, Egyptian magic, (a,d)-antimagic labelings and the linear Diophantine equations have been investigated. The linear Diophantine equations of (a,d)-antimagic graphs have been analysed. Some preliminary concepts and definitions to the thesis have been given in the first chapter. In second chapter, weakly antimagic, antimagic, Egyptian magic graphs have been defined and k-enlargement of the edge labeling f of G has been given. In the third chapter, after giving some theorems about k-enlargement of the edge labeling f of G, the theorems have been proved and shown by examples. In the fourth chapter, magic, super magic, prime magic and (a,d)-antimagic graphs have been investigated and this graphs have been shown by examples. In the fifth chapter, the linear Diophantine equations of (a,d)-antimagic graphs have been expressed, and some propositions and theorems have been proved. In the sixht chapter, a parachute Pg,b has been given and the theorems which are related to the parachute graphs have been exspressed and proved. As a result, magic, antimagic, weakly antimagic, prime magic, super magic, Egyptian magic and (a,d)-antimagic labelings have been expressed and shown by examples. Furthermore the linear Diophantine equations of (a,d)-antimagic graphs and a parachute P&b is explained. KEYWORDS: Graph / Diophantine Equation / Egyptian Graph.