Omega invaryantı

Abstract

Bu çalışmada, verilen çizilebilir bir derece dizisinin mümkün olan çizimlerinin graf teorik, topolojik ve kombinatorik özellikleri hakkında bilgi veren ve adına omega invaryantı denilen bir graf invaryantı tanımlanmış ve çeşitli uygulamaları ve özellikleri incelenmiştir. Topolojide 250 yılı aşkın bir süredir bilinen ve yüzeylerle ilgili çok sayıda uygulamalara sahip olan Euler karakteristiği ile ve grafın devir sayısı ile de ilgili olan bu invaryantın bir çok özelliğin çalışılmasında faydalı olduğu gözlenmiştir. Bu tez 6 bölümden oluşmaktadır. Birinci bölüm giriş bölümü olup bu bölümde graflarla ilgili temel kavramlar hatırlatılmış ve tezin ilerleyen bölümlerinde kullanılacak olan bazı sonuçlar verilmiştir. Ayrıca sık kullanılan graf türleri ve temel özellikleri hatırlatılmıştır. İkinci bölümde omega invaryantının tanımına temel oluşturan derece dizisi kavramı hatırlatılacaktır. Ayrıca bazı graf sınıflarının derece dizileri ifade edilecektir. Üçüncü bölümde omega invaryantı tanımlanacaktır. Bu tanım için nelerden esinlenildiği açıklanarak temel bazı özellikleri incelenmiştir. Bazı özel graf sınıfları için omega invaryantının aldığı değerler formülleştirilmiş ve tüm omega değerlerinin bir çok açıdan üç farklı kümeye ayrılabildiği gösterilmiştir. Ayrıca omega invaryantı ile Euler karakteristiği arasındaki ilişki ortaya konmuştur. Dördüncü bölümde derece dizilerinin çok sayıda olası çizimi arasında özel bir yere sahip olan temel çizimler; beşinci bölümde bir graftan kenar ve köşe silmenin omega invaryantına etkisi ele alınmıştır. Altıncı ve son bölümde graflarla ilgili bazı uç problemler ele alınmıştır.

In this thesis, omega invariant which gives information about the graph theoretical, topological and combinatorial properties of all realizations of a given degree sequence is defined and several applications and properties of it are studied. It is observed that this invariant which is related to the Euler characteristics known in topology for more than 250 years and has many applications related to surfaces and also to the cyclomatic number of graphs, is useful in the study of many properties. This thesis consists of 6 chapters. The first chapter is the introductory chapter and the fundamental notions are recalled here together with the results which will be needed in later chapters. Also some frequently used graph classes and their fundamental properties are given. In the second chapter, the notion of degree sequence which forms the basis of the definition of the omega invariant is studied. Also the degree sequences of some graph classes will be given. In the third chapter, omega invariant will be defined. The motivation for defining it and some main properties will be given. It will be calculated for some graph classes and it is shown that the values of omega invariant can be grouped into three sets which appears to be very useful. Also the relation between omega invariant and Euler characteristic is established. In the fourth chapter, the fundamental realizations which have an important place amongst all realizations of a given degree sequence; in the fifth chapter, the effect of edge and vertex deletion from a graph on omega are studied. In the sixth and last chapter, some extremal problems are studied.