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
- Özel ve resmi lise müdürlerinin toplam kalite yönetimi (TKY)'nin genel liselerde uygulanabilirliğine ilişkin görüşler
Public and private high schools directors view about applicability of the total quality management to high schools
NAMIK SÖNMEZ
Yüksek Lisans
Türkçe
1999
Eğitim ve ÖğretimHacettepe ÜniversitesiEğitim Bilimleri Ana Bilim Dalı
PROF. DR. YÜKSEL KAVAK
- İslamcılık bağlamında Türkiye'de siyasal İslamın gelişimi ve Refah Partisi 1980 - 1998
On the context of pan Islam the development of political Islam in Turkey and Welfare Party 1980 - 1998
YALÇIN AKDOĞAN
- On implementation theory
Uygulama teorisi üzerine
ÖMÜR CELMANBET
Yüksek Lisans
İngilizce
1999
MatematikOrta Doğu Teknik ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. MEHPARE BİLHAN
- On archelypol monumentality in architecture
Mimarlıkta arketipsel anıtsallık
ÖZLEM DENİZ
Yüksek Lisans
İngilizce
1999
MimarlıkOrta Doğu Teknik ÜniversitesiMimarlık Ana Bilim Dalı
DOÇ. DR. EMEL AKÖZER
- On solutions of semi-euclidean eikonal equations
Yarı-öklidyen ikon denklemlerin çözümleri üzerine
Z.BAŞAK GÜREL
Yüksek Lisans
İngilizce
1999
MatematikOrta Doğu Teknik ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. DEMİR N. KÜPELİ