Çizgelerde Baskınlık ve Total Baskınlık

Abstract

Bu projede, çizge teorisinde baskınlık, total baskınlık ve eşli baskınlıkla ilgili araştırma problemleri ele alınmış ve birçok yeni sonuç elde edilmiştir. Öncelikle, baskınlık sayısı ve üst baskınlık sayısı arasındaki farkın bir olduğu çizgeler anlamına gelen neredeyse iyi baskınlanmış çizgeleri ele aldık. Minimum derecesi iki olan iki parçalı neredeyse iyi baskınlanmış çizgeleri karakterize ettik. Ayrıca, 3,4,5 ve 7 boyunda döngülerin olmadığı neredeyse iyi-baskınlanmış çizgelerin karakterizasyonunu yaptık. İyi-baskınlanmış çizgelerin bir alt kümesi olan k-birörnek çizgeler konusunda ise total k-birörnek çizgelerle ilgili önemli sonuçlar elde ettik. Total baskınlanmış çizgeler konusunda ise tüm minimal total baskın kümelerinin boyu aynı olan çizgeler anlamına gelen iyi-total-baskınlanmış çizgeleri ele aldık ve bu çizgelerle ilgili çeşitli yapısal sonuçlar elde ettik. Ayrıca, total baskınlık ile minimum maksimal eşleme arasındaki ilişkiyi inceleyerek bazı sonuçlar elde ettik. Bir çizgede total baskınlık sayısı ile baskınlık sayısının iki katının eşit olup olmadığını kontrol eden bir algoritma tasarladık. Çizgelerde üst baskınlık sayısıyla ilgili olarak ise üst eşli baskınlık sayısı ile üst baskınlık sayısı arasındaki ilişkiyi inceledik. Üst eşli baskınlık sayısının üst baskınlık sayısının iki katıyla sınırlı olduğunu gösterdik ve bu eşitsizliğin eşitlikle sağlandığı çizgeleri özel çizge sınıflarında inceledik. Ayrıca, eşli baskınlık sayısının baskınlık sayısı ve paketleme sayısı ile olan ilişkileriyle ilgili çalışmalar yaptık. Savunucu baskınlık probleminin karmaşıklığını düzgün interval çizgelerde inceledik ve iki adet açgözlü algoritma önererek karmaşıklıklarını analiz ettik. Bu projede, eşit-eşlenebilir iki parçalı çizgeler konusunda da çalıştık ve bazı yapısal karakterizasyonlar elde ettik. Kenar-kritik eşit-eşlemeli iki parçalı çizgelerin tam bir karakterizasyonunu vererek eşit-eşlemeli iki parçalı çizgelerin bu çizgelerden elde edilebileceğini gösterdik.