Aristotle University Of Thessaloniki (AUTH)
Structural properties of signed - graphic matroids
Abstract
dc:descriptionThis 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.
Degree
thesis:*- Grantor dc:publisher
- Aristotle University Of Thessaloniki (AUTH)
- Year dc:date
- 2019
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Vretta, Eleni-Maria
- Βρεττά, Ελένη-Μαρία
Subjects
dc:subject × 14- Προσημασμένα - γραφικά μητροειδή
- Τετραδικά προσημασμένα - γραφικά μητροειδή
- Αποσύνθεση τετραδικών προσημασμένων - γραφικών μητροειδών
- Δυαδικά προσημασμένα - γραφικά μητροειδή
- Διαχωρισμός γεφυρών
- Signed - graphic matroids
- Guaternary signed - graphic matroids
- Decomposition of quaternary signed - graphic matroids
- Binary signed - graphic matroids
- Bridge - separability
- Φυσικές Επιστήμες
- Μαθηματικά
- Natural Sciences
- Mathematics
Rights
dc:rights- Statement dc:rights
-
- BY_NC_SA
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/45563