Structural properties of signed - graphic matroids

Abstract

This doctoral thesis furnishes structural results for signed-graphic matroids focusing mainly on two subclasses binary and quaternary signed-graphic matroids. The class of quaternary signed-graphic matroids is decomposed and the classes of cographic signed-graphic matroids and binary signed-graphic matroids are characterized. More precisely, a characterization of the class of cographic signed-graphic matroids which is based on properties of cocircuits is provided. Furthermore, we present a characterization for binary signed-graphic matroids along with two algorithms. Regarding tangled signed graphs, we define an operation which preserves the number of negative cycles. As a consequence, we prove that negative cycles in tangled signed graphs are polynomially bounded by the number of negative cycles in signed graphs belonging to two well-defined classes. The class of quaternary signed-graphic matroids is characterized by a decomposition theorem which states that the existence of a non-graphic and bridge-separable cocircuit which decomposes a quaternary matroid into a graphic minor and a signed-graphic minor are necessary and sufficient conditions for the matroid to be signed-graphic. As a result, we determine the building blocks of quaternary signed-graphic matroids which are graphic matroids and signed-graphic matroids which become graphic upon the deletion of any cocircuit. The decomposition theorem, which is based on a new operation called star composition and the well-known k-sums, constitutes the theoretical background for a recognition algorithm. A survey of important results of Matroid Theory as well as conjectures and recent work on the field are also presented.

Η παρούσα διδακτορική διατριβή παρέχει δομικά αποτελέσματα για τα προσημασμένα-γραφικά μητροειδή εστιάζοντας κυρίως σε δύο υποκλάσεις τους τα δυαδικά και τα τετραδικά προσημασμένα-γραφικά μητροειδή. Η κλάση των τετραδικών προσημασμένων-γραφικών μητροειδών αποσυνθέτεται και οι κλάσεις των συγγραφικών προσημασμένων-γραφικών μητροειδών και των δυαδικών προσημασμένων-γραφικών μητροειδών χαρακτηρίζονται μέσω δομικών θεωρημάτων. Πιο συγκεκριμένα, παρουσιάζεται ένας χαρακτηρισμός για την κλάση των συγγραφικών προσημασμένων-γραφικών μητροειδών που βασίζεται σε ιδιότητες των συγκυκλωμάτων. Επιπλέον, παρουσιάζονται ένας χαρακτηρισμός των δυαδικών προσημασμένων-γραφικών μητροειδών και δύο αλγόριθμοι. Όσον αφορά τα περίπλοκα προσημασμένα γραφήματα, ορίζουμε μια πράξη που διατηρεί τον αριθμό των αρνητικών κύκλων. Ως συνέπεια, αποδεικνύουμε ότι το πλήθος των αρνητικών κύκλων στα περίπλοκα προσημασμένα γραφήματα είναι πολυωνυμικά φραγμένο από το πλήθος των αρνητικών κύκλων των προσημασμένων γραφημάτων που ανήκουν σε δύο καλά ορισμένες κλάσεις. Η κλάση των τετραδικών προσημασμένων-γραφικών μητροειδών χαρακτηρίζεται μέσω ενός θεωρήματος αποσύνθεσης σύμφωνα με το οποίο η ύπαρξη ενός μη-γραφικού συγκυκλώματος που διαχωρίζει τις γέφυρες και αποσυνθέτει το μητροειδές σε ένα γραφικό έλασσον και ένα προσημασμένο-γραφικό έλασσον είναι ικανές και αναγκαίες συνθήκες για να είναι το μητροειδές προσημασμένο-γραφικό. Ως αποτέλεσμα, προσδιορίζονται οι δομικοί λίθοι των τετραδικών προσημασμένων-γραφικών μητροειδών οι οποίοι είναι γραφικά μητροειδή και προσημασμένα-γραφικά μητροειδή τα οποία μετατρέπονται σε γραφικά μετά τη διαγραφή οποιουδήποτε συγκυκλώματος. Το θεώρημα αποσύνθεσης των τετραδικών προσημασμένων-γραφικών μητροειδών, το οποίο βασίζεται σε μια πράξη που ονομάζεται αστρική σύνθεση και στα γνωστά κ-αθροίσματα, αποτελεί το θεωρητικό υπόβαθρο για έναν αλγόριθμο αναγνώρισης. Τέλος παρουσιάζεται μια επισκόπηση των πιο σημαντικών αποτελεσμάτων και εικασιών της Θεωρίας Μητροειδών.