Publikationen

Schreyer, Jens;
Oblique graphs, 2005. - Online-Ressource (PDF-Datei: 69 S., 470 KB) : Ilmenau, Techn. Univ., Diss., 2005
Parallel als Druckausg. erschienen

Gegenstand der Arbeit ist die Untersuchung asymmetrischer Strukturen in Graphen. Dabei wird insbesondere betrachtet, inwieweit solche Strukturen in Graphen beliebiger Größe auftreten können. Nach einem Satz von Wright sind fast alle Graphen asymmetrisch. Auf der anderen Seite zeigen viele Resultate der Ramsey-Theorie, dass bei wachsenden Strukturen gewisse Regularitäten oder Ähnlichkeiten oft unvermeidlich sind. Der Begriff der Asymmetrie wird dahingehend erweitert, dass auch lokale Ähnlichkeiten ausgeschlossen werden. Graphen mit dieser hochgradigen Asymmetrieeigenschaft werden schräge Graphen (oblique graphs) genannt. Im ersten Teil der Arbeit werden asymmetrische Strukturen in Polyedergraphen untersucht. Für diese Graphenklasse sind Symmetrieeigenschaften in der Vergangenheit bereits oft untersucht worden. In dieser Arbeit werden verschiedene Typdefinitionen für die Flächen und Kanten eines Polyedergraphen vorgestellt. Ein Polyedergraph ist schräg bezüglich einer solchen Definition, wenn keine zwei Flächen beziehungsweise Kanten den gleichen Typ haben. Die Hauptresultate dieses Teils der Arbeit sind Sätze, die die Endlichkeit der Menge solcher schräger Graphen zeigen. Darüber hinaus kann in manchen Fällen gezeigt werden, dass jeder hinreichend große Polyedergraph mehr als z Kanten oder Flächen eines gemeinsamen Typs enthalten muss, wobei z eine beliebige natürliche Zahl ist. Im weiteren Verlauf werden die Endlichkeitsresultate über schräge Polyedergraphen auf Landkarten auf Flächen höheren Geschlechts übertragen. Im zweiten Teil der Arbeit werden schließlich asymmetrische Strukturen in allgemeinen Graphen untersucht. Ein schlichter Graph wird eckenschräg genannt, wenn sich je zwei Ecken in der Gradfolge ihrer Nachbarecken unterscheiden. Es wird gezeigt, dass es selbst unter verschiedenen zusätzlichen einschränkenden Bedingungen unendlich viele solche Graphen gibt. Im letzten Abschnitt der Arbeit werden schließlich Zufallsgraphen betrachtet. Es wird gezeigt, dass mit wachsender Eckenzahl die Wahrscheinlichkeit eines Zufallsgraphen, eckenschräg zu sein, gegen 1 konvergiert. Das heißt, fast jeder Graph ist eckenschräg, falls sich die Wahrscheinlichkeit dafür, dass eine bestimmte Kante im Zufallsgraphen auftritt, innerhalb gewisser, vorgegebener Grenzen bewegt.

http://www.db-thueringen.de/servlets/DocumentServlet?id=3604

Göring, Frank; Harant, Jochen; Hexel, Erhard; Tuza, Zsolt
On short cycles through prescribed vertices of a graph. - In: Discrete mathematics, Bd. 286 (2004), 1/2, S. 67-74

http://dx.doi.org/10.1016/j.disc.2003.11.047

Pruchnewski, Anja;
Das graphentheoretische Dominanzproblem als stetiges Optimierungsproblem, 2004. - Online-Ressource (PDF-Datei: 79 S., 395 KB) : Ilmenau, Techn. Univ., Diss., 2004
Parallel als Druckausg. erschienen

Unter dem Dominanzproblem verstehen wir die Bestimmung der Dominanzzahl eines Graphen. Das zugehörige Entscheidungsproblem ist NP-vollständig. Somit ist man sowohl an guten oberen Schranken für die Dominanzzahl als auch an (möglichst effizienten) Algorithmen interessiert, die eine dominierende Menge liefern, deren Kardinalität diese Schranke nicht übersteigt.- In dieser Arbeit gelingt es, mit Mitteln der wahrscheinlichkeitstheoretischen Methode stetige Optimierungsprobleme für die Dominanzzahl, die Vektordominanzzahl, die totale Dominanzzahl bzw. die totale Vektordominanzzahl sowie die Überdeckungszahl (und damit auch für die Unabhängigkeitszahl) aufzustellen. Davon ausgehend werden Methoden zur Gewinnung oberer Schranken für die Dominanzzahlen der untersuchten Konzepte angegeben. Es werden Algorithmen vorgestellt, die für eine vorgegebene Schranke eine Knotenmenge berechnen, deren Kardinalität diese Schranke nicht übersteigt und die im entsprechenden Sinn dominierend ist. Die Algorithmen erweisen sich als polynomial für die Dominanz und die totale Dominanz, im Falle beschränkter Maximalvalenz auch für die Vektordominanz und die totale Vektordominanz. - Eine geeignete Einschränkung des zulässigen Bereiches liefert für paare Graphen explizit berechenbare Schranken in Abhängigkeit von den Minimalvalenzen in den Partitionsklassen. Diese Schranken sind gegenüber den aus der Literatur bekannten Schranken verbessert. Die Betrachtung verallgemeinerter Bipartitionen für nicht notwendig paare Graphen ermöglicht ebenfalls die Berechnung verbesserter Schranken und zudem die Berücksichtigung weiterer Graphenparameter bei der Schrankenberechnung.

http://www.db-thueringen.de/servlets/DocumentServlet?id=2608

Dobrynin, Andrey A.; Melnikov, Leonid S.; Schreyer, Jens; Walther, Hansjoachim
Some news about oblique graphs. - In: Discussiones mathematicae, ISSN 2083-5892, Bd. 22 (2002), 1, S. 39-50

A k-gon alpha of a polyhedral graph G(V,E,F) is of type <b1,b2,...,bk> if the vertices incident with alpha in cyclic order have degrees b1, b2,...,bk and <b1,b2,...,bk>$ is the lexicographic minimum of all such sequences available for alpha. A polyhedral graph G is oblique if it has no two faces of the same type. Among others it is shown that an oblique graph contains vertices of degree 3.

https://doi.org/10.7151/dmgt.1157

Voigt, Margit; Walther, Hansjoachim
Polyhedral graphs with restricted number of faces of the same type. - In: Discrete mathematics, Bd. 244 (2002), 1/3, S. 473-478

http://dx.doi.org/10.1016/S0012-365X(01)00103-0