Graf izomorfizmi ve ko-spektral graflar

Abstract

Bu çalışmada, grafların komşuluk spektrumları ile belirlenebilirliği problemi üzerinde durulmuştur. Döngü graf esas alınarak oluşturulan bazı özel grafların (lolipop graf, güneş graf, kırık güneş graf ve turp graf) spektral belirlenebilirliklerine dair yapılmış olan çalışmalardan hareketle, tam graf esas alınarak oluşturulan uçurtma graf, deniz kestanesi graf, kırık deniz kestanesi graf ve ananas grafın komşuluk spektrumları ile belirlenebilirlikleri araştırılmıştır. Literatürde sıklıkla kullanılan ve spektral yarıçap için ekstremum değerler sağlayan önemli bir graf türü olan uçurtma grafın komşuluk spektrumu ile belirlenebilir olduğu bu çalışmada iddia ve ispat edilmiştir. Deniz kestanesi ve kırık deniz kestanesi grafların komşuluk spektrumları ile belirlenebilir olduklarının ispatı ise yeniden ve daha kısa bir şekilde yapılmıştır. Ananas graf ile ilgili yapılan literatür taraması sonucunda, bu grafın komşuluk spektrumu ile belirlenebilir olduğunun daha önce söylenmiş olduğu fakat bu hipotezin ve hipoteze dair yapılmış olan ispatın doğru olmadığı bu tez çalışmasında tespit edilmiştir. Bu bağlamda, bu graf türünün aslında iddia edilenin aksine komşuluk spektrumu ile her zaman belirlenebilir olmadığını gösteren, yani literatürde var olan teoreme ters örnek teşkil eden graf aileleri üretilmiştir. Bunun yanısıra, bir ananas grafta sarkıt kenar sayısının 3 ten küçük olduğu durumda iddia edilen hipotezin doğru olduğunun ispatı da verilmiştir. Böylece, ananas grafın komşuluk matrisine göre tam bir spektral karakterizasyonunun yapılabilmesine yönelik açık problemler de üretilmiştir.

This study is based on the determinability problem of the graphs by using their adjacency spectrum. By the motivation of the foundations from the literature about some special graphs that are containing a cycle as a main part (such as lollipop graph, sun graph, broken sun graph and turnip graph); the determinability of the some special graphs that are containing a complete graph as a main part (kite graph, urchin graph, broken urchin graph and pineapple graph) by using their adjacency spectrum is investigated in this work. Kite graph has been appeared many times in the literature since they provide extremum values for the spectral radius of some graph matrices. The property of the kite graph, that is this graph is determined by its adjacency spectrum, is claimed and proved in this thesis. For the urchin and broken urchin graphs, it is seen that these graphs are already proved to be determined by their adjacency spectrum. But for this situation, a shorter different proof is also given here. Pineapple graph is already said to be determined by its adjacency spectrum in the literature. But, during this work, it is detected that the theorem and the proof about this situation is actually not true. Hence, the counter examples are obtained by generating the families of graphs which show that the pineapple graph is not determined by its adjacency spectrum in general. Moreover, if the number of the pendant edges in the pineapple graph is less than 3, then it is proved that the pineapple graph is determined by its adjacency spectrum. Thus, some open problems about the whole adjacency spectral characterization of pineapple graph are also given here.