Ικανές συνθήκες για την ύπαρξη υπογραφημάτων με καθορισμένη δομή σε ειδικές κατηγορίες γραφημάτων

Abstract

The purpose of this thesis is to establish sufficient conditions for the existence of factors with prescribed properties in special classes of graphs; mainly in terms of the graph invariants of connectivity and minimum degree. The thesis starts by examining the relation between the minimum degree of a claw-free graph and the existence of a 2-factor which includes or excludes a given pair of edges. Chapter 2 examines the relation between the edge-connectivity of a regular graph and the existence of a 2-factor which again includes and excludes respectively two given sets of edges. Finally in chapter 3, we obtain a sufficient condition for the square of a graph G to have a k-factor. This sufficient condition is expressed in terms of the minimum degree of G and generalizes an already known result.

Παράγοντα ενός γραφήματος G ονομάζουμε κάθε υπογράφημα του, που έχει το ίδιο σύνολο κορυφών με το G, στο οποίο περιέχεται. Εάν ένας παράγοντας είναι k-κανονικό γράφημα τότε αυτός ονομάζεται k-παράγοντας. Ο κύριος σκοπός αυτής της διδακτορικής διατριβής είναι η απόδειξη ικανών συνθηκών για την ύπαρξη παραγόντων με καθορισμένη δομή σε κάποιες ειδικές κατηγορίες γραφημάτων. Αυτές οι ικανές συνθήκες εκφράζονται συναρτήσει των γραφοθεωρητικών παραμέτρων της συνεκτικότητας και του ελάχιστου βαθμού. Στο Κεφάλαιο 1 της διατριβής εξετάζεται η σχέση μεταξύ του ελάχιστου βαθμού κορυφής σε ένα Κ1,3-ελεύθερο γράφημα και της ύπαρξης ενός 2-παράγοντα σε αυτό, ο οποίος περιέχει ή "αποφεύγει" ένα δοσμένο ζευγάρι ακμών. Στο Κεφάλαιο 2 εξετάζεται η σχέση μεταξύ της συνεκτικότητας ακμών ενός κανονικού γραφήματος και της ύπαρξης σε αυτό ενός 2-παράγοντα, ο οποίος πάλι περιέχει και "αποφεύγει" αντίστοιχα ένα δοσμένο ζευγάρι συνόλων ακμών. Στο Κεφάλαιο 3, αποδεικνύεται μια ικανή συνθήκη για την ύπαρξη ενός Κ-παράγοντα στο τετράγωνο ενός γραφήματος G. Η συνθήκη αυτή εκφράζεται συναρτήσει του ελάχιστου βαθμού στο G και γενικεύει κάποιο ήδη γνωστό θεώρημα.