Geri Dön

Hipertam çizgeler ve genelleştirilmiş Kneser-Lovász teoremi

Hypercomplete graphs and generalized Kneser-Lovász theorem

PDF İndir

  1. Tez No: 234169
  2. Yazar: DEMET TAYLAN
  3. Danışmanlar: DOÇ. DR. YUSUF CİVAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Matematik, Mathematics
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2009
  8. Dil: Türkçe
  9. Üniversite: Süleyman Demirel Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Matematik Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 68

Özet

Altı bölümden oluşan bu tezde ilk önce çizge teori hakkında bazı ön bilgiler verilmiştir. Ardından yeni bir çizge operatörü tanıtılmış ve bu operatörün özellikleri araştırılmıştır. Verilen bir G çizgesi ve F çizgeler ailesi yardımıyla r-hipertam hiperçizgeler olarak adlandırdığımız yeni hiperçizgeler (bazen çizgeler) H_{r}(G;F) inşa edilmektedir. H_{r}(G;F) çizgesinin özel olarak alınan aileler için detaylı bir analizi yapılmıştır.Birinci bölümde, genel anlamda tezin içeriği hakkında bilgi verilmiştir.İkinci bölümde, gerekli ön bilgiler verilmiş ve notasyonumuz tanıtılmıştır.Üçüncü bölüm ve üçüncü bölümden sonra gelen diğer bölümlerde yapılan işler orijinal niteliktedir. Üçüncü bölümde, çizge operatörümüz tanımlanmıştır. H_{r}(G;F) hiperçizgesinin bir çizge olması için gerek ve yeter koşul verilmiştir. Bazı özel çizgeler ile bazı r-hipertam hiperçizgeler arasında izomorfizmalar verilmiştir. Daha sonra, her çizgenin bir r-hipertam çizge olarak ifade edilebileceği ispatlanmıştır.Dördüncü bölümde, H_{r}(G;K_{2r}) çizgesinin bağlantılı olması için yeter koşullar belirlenmiştir. Daha sonra, 2K? çizgesinin H_{r}(G;K_{2r}) çizgesinde bir indirgenmiş alt çizge olarak bulunmaması için gerek ve yeter koşul verilmiştir. G çizgesi için ?(G)=w(G) sağlandığında H_{r}(G;K_{2r}) çizgesinin kromatik sayısını veren ana teoremimiz genelleştirilmiş Kneser-Lovász teoremi ispatlanmıştır. Bu çizgelerin oransal kromatik sayısı ve tamsal sayısı da hesaplanmıştır. G çizgesinin tam m-çoklu bir çizgeye izomorfik olması halinde H_{r}(G;K_{2r}) çizgesinin Kneser çizgelerinin bir vektörle çarpımı olduğu ispatlanmıştır. Herhangi bir G çizgesi için H_{r}(G;K_{2r}) çizgesinin Kneser çizgelerinin bir indirgenmiş alt çizgesi olması için gerek ve yeter koşul verilmiştir.Beşinci bölümde, bazı r-hipertam çizgeler için kromatik sayı sınırları hesaplanmıştır.Altıncı bölümde, özel olarak alınan bir G ve F yardımıyla, G çizgesinin k-tam genişlemesi olarak adlandırdığımız yeni bir çizge Ekt_{k}(G) tanımlanmıştır. Ekt_{k}(G) çizgesinin köşe sayısı, bir köşesinin derecesi hesaplanmış ve birbirine izomorfik olan iki çizgenin k-tam genişlemelerinin de birbirine izomorfik olduğu gösterilmiştir. Daha sonra Ekt_{k}(G) çizgesinin çapının daima 3 veya 3 ten küçük olduğu gösterilmiştir. Ekt_{k}(G) çizgesinin kromatik sayısı, oransal kromatik sayısı ve tamsal sayısı hesaplanmış ve hepsinin G çizgesinin tamsal vektörünün k. bileşenine eşit olduğu görülmüştür. Daha sonra C? çizgesinin hangi durumlarda Ekt_{k}(G) çizgesinin bir indirgenmiş alt çizgesi olduğu belirlenmiş ve bilinen çizge sınıflarına yönelik bazı karakterizasyonlar yapılmıştır.

Özet (Çeviri)

In this thesis, which consists of six chapters, we first provide some preliminaries about graph theory. Then we introduce a new graph operation and investigate its properties. Given a (fixed) graph G and a graph family F, we construct a new hypergraph (or sometimes simple graph) H_{r}(G;F) that we call the“r-hypercomplete hypergraph”. We offer a detailed analyzes of such graphs for certain families.In the first chapter, we make an overall discussion of our works through this thesis.We provide necessary backround and introduce our notation in Chapter two.The results obtained within Chapter three and the rest of this thesis are author's own work. In Chapter three, we introduce our graph operator. We give the necessary and sufficient conditions for the hypergraph H_{r}(G;F) to be a graph. We give isomorphisms between some special graphs and some r-hypercomplete hypergraphs. Then we prove that every graph can be described as an r-hypercomplete graph.In Chapter four, we determine the sufficient condition on G for which H_{r}(G;F) is connected. Then we give the necessary and sufficient conditions for the graph H_{r}(G;F) to be 2K?-free. We prove our main theorem, the generalized Kneser-Lovász theorem, which determines the chromatic number of r-hypercomplete graphs H_{r}(G;K_{2r}) when ?(G)=w(G) is satisfied by G. We readily compute the fractional chromatic number and the clique number of H_{r}(G;K_{2r}). We prove that if G is isomorphic to a complete m-partite graph then the r-hypercomplete graph H_{r}(G;K_{2r}) is isomorphic to a multiplication of Kneser graphs with a vector. We give the necessary and sufficient conditions for the graph H_{r}(G;F) to be an induced subgraph of Kneser graphs.In Chapter five, we give bounds for the chromatic number of some r-hypercomplete graphs.In Chapter six, taking G as a special graph and considering F as a special family we define a new graph which we call k-complete extension of G denoted by Ekt_{k}(G). We calculate the order of Ekt_{k}(G), the degree of a vertex in Ekt_{k}(G), and show that the k-complete extensions of two isomorphic graphs are again isomorphic. Further we show that the diameter of Ekt_{k}(G) is always less than or equal to 3. We calculate the chromatic number, fractional chromatic number and the clique number of Ekt_{k}(G), conclude that they are all equal to the k. component of the clique vector of G. After that we determine when C? is an induced subgraph of Ekt_{k}(G), and deduce some characterizations in terms of known graph classes.

Geri Dön