On equimatchable graphs and well-indumatched graphs
Eşiteşlenebilir çizgeler ve iyi-indüklenmiş çizgeler üzerine
- Tez No: 767355
- Danışmanlar: PROF. DR. SİBEL ÖZKAN, PROF. DR. DİDEM GÖZÜPEK KOCAMAN
- Tez Türü: Doktora
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Gebze Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 122
Özet
Bu tez, çizge teorisindeki sorunları, çoğunlukla bir grafiğin eşleşmesini araştırır. Grafikteki her maksimum eşleşme bir maksimum eşleşme ise, bir grafiğe {eşiteşleştirilebilir} denir. Birçok araştırmacı eşiteşleştirilebilir çizgeler üzerinde bazı yapısal ve algoritmik sonuçlar sağladılar. Özellikle, üçgensiz eşiteşleştirilebilir çizgelerde bazı kısmi sonuçlar elde ettiler. Bu tezde, ilk önce üçgensiz eşiteşleştirilebilir çizgelerdeki sonuçları, bu tür çizge ailelerinin yapısını tanımlayarak, eşiteşleştirilebilir üçgensiz çizgelerin tam karakterizasyonunu sağlayacak şekilde genişletiyoruz. Bu karakterizasyon, verilen iki parçalı olmayan bir çizgenin eşiteşleştirilebilir ve üçgensiz olup olmadığını tanıyan doğrusal bir zaman algoritması verir. Ayrıca, literatürde eşiteşleştirilebilir iki parçalı çizgeler için yapısal olarak çok fazla bilgi sağlamayan ya da sadece bazı kısmi spnuçlar sağlayan karakterizasyonlar vardır. Kenarlarından birinin çıkarılmasıyla elde edilen her çizgenin eşiteşleştirilemez olması durumunda, eşiteşleştirilebilir bir çizge {kenar-kritik} olarak adlandırılır. Bu tezde, öncelikle, genel eşiteşleştirilebilir iki parçalı çizgeler yerine, kenar-kritik eşeşleştirilebilir iki parçalı çizgelerin yapısına odaklanmanın yeterli olduğunu gösteriyoruz. Daha sonra, kenar-kritik eşiteşleştirilebilir iki parçalı çizgeler için yapısal bir karakterizasyon sağlıyoruz. Çizgedeki her maksimum indüklenmiş eşleşme bir maksimum indüklenmiş eşleşme ise, bu çizgeye iyi-indüklenmiş denir. Literatürde iyi-indüklenmiş asiklik çizgelerin bir karakterizasyonunu ve iyi-indüklenmiş tek döngülü çizgeler üzerinde de bazı kısmi sonuçlar vardır. Sözde orman, her bağlı bileşenin en fazla bir döngü içerdiği, yani her bağlı bileşenin tek döngülü bir çizge veya bir ağaç olduğu bir çizgedir. Bu tezde, son olarak tek döngülü iyi-indüklenmiş çizgelerle ilgili sonuçları, çizge ailelerinin yapısının belirleyerek, iyi-indüklenmiş sahte ormanların tam bir karakterizasyonunu sağlayarak genişletiyoruz.
Özet (Çeviri)
This thesis investigates problems in graph theory, mostly matchings of a graph. A graph is called {equimatchable} if every maximal matching in the graph is a maximum matching. Many researchers provided some structural and algorithmic results on equimatchable graphs; particularly, some authors provided some partial results on equimatchable graphs with no triangle, in other words, equimatchable triangle-free graphs. In this thesis, we first extend these particular results by providing a full characterization of equimatchable triangle‐free graphs by identifying the structure of such graph families. This characterization yields a linear time algorithm that recognizes whether a given non-bipartite graph is equimatchable and triangle-free. Furthermore, some authors characterized equimatchable bipartite graphs, which does not provide a structural insight, whereas some authors provided only a partial characterization for equimatchable bipartite graphs. An equimatchable graph is called {edge-critical} if every graph obtained by the removal of one of its edges is not equimatchable. We first point out that it is sufficient to focus on the structure of edge-critical equimatchable bipartite graphs instead of the general equimatchable bipartite graphs. Hence, in this thesis, we provide a structural characterization for edge-critical equimatchable bipartite graphs. A graph is called {well-indumatched} if every maximal induced matching in the graph is a maximum induced matching. In the literature, some authors provided a characterization of well-indumatched acyclic graphs and some partial results on well-indumatched unicyclic graphs. A {pseudoforest} is a graph in which every connected component contains at most one cycle, that is, each connected component is a unicyclic graph or a tree. In this thesis, we finally extend the result in the literature about well-indumatched unicyclic graphs by providing a complete characterization of well-indumatched pseudoforests by identifying the structure of such graph families.
Benzer Tezler
- Minkowski 3-uzayında helikoidal yüzeyler üzerindeki loksodromlar
Loxodromes on helicoidal surfaces in Minkowski 3-space
MUSTAFA KAYACIK
Yüksek Lisans
Türkçe
2015
MatematikBozok ÜniversitesiMatematik Ana Bilim Dalı
YRD. DOÇ. DR. MURAT BABAARSLAN
- Ahlaki ilke ve ahlaki değer problemi üzerine
On the problem of moral principle and moral value
HASAN YÖNDEN
- Özbek cedit edebiyatı eserlerinde 'cedit – kadim' görüş çatışmalarının yansımaları: Mahmud Hoca Behbudi, Abdürrauf Fıtrat ve Abdülhamid Çolpan eserleri örneğinde
On new Uzbek literature work (jadid - ancient) view, conflict of perfections: Prof Mahmud Behbudi, Abdürrauf Fıtrat ve Abdülhamid Çolpan works examples
ABDUL FATAH RASOOLY
Yüksek Lisans
Türkçe
2015
Türk Dili ve EdebiyatıMuğla Sıtkı Koçman ÜniversitesiÇağdaş Türk Lehçeleri ve Edebiyatları Ana Bilim Dalı
YRD. DOÇ. DR. ALİ ABBAS ÇINAR
- Hiperbolik ve parabolik denklemlerin çözümünde fourier metodunun uygulanması üzerine
On the implementation of thefouriermethodfor the solution ofhyperbolicand parabolic equations
GÖKHAN DOĞAN
Yüksek Lisans
Türkçe
2015
MatematikBozok ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. MAMMAD MUSTAFAYEV
- Genelleştirilmiş Quasi-Nörlund toplanabilme üzerine
On generalised quasi-nörlund summability
KADRİYE BAŞAR
Yüksek Lisans
Türkçe
2015
MatematikBozok ÜniversitesiMatematik Ana Bilim Dalı
YRD. DOÇ. ABDULLAH SÖNMEZOĞLU