Olique graphs

Schreyer, Jens

Zusammenfassung 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.

The main issue of this work is to investigate asymmetric structures in graphs. While symmetry structures in graphs are well observed, the opposite question has not been investigated deeply so far. It is known from a theorem of Wright, that almost all graphs are asymmetric. The class of asymmetric graphs is restricted further by forbidding even local symmetries. The main question is to determine how many graphs do have this stronger so-called obliqueness property. On the one hand the superclass of asymmetric graphs is not only infinite, but contains almost all graphs. On the other hand many Ramsey type results indicate, that growing structures enforce at least local symmetries or regularities. In the first part of the work oblique structures in polyhedral graphs are investigated. Several type definitions for faces and edges of a polyhedral graph are introduced. A polyhedral graph is called oblique with respect to a type definition if it does not contain two faces or edges, respectively, which are of the same type. The main results of that part are theorems that show the finiteness of the class of such oblique polyhedral graphs. In some cases it is shown that a large enough polyhedral graph always contains more than z faces or edges of a common type, where z is an arbitrary positive integer. The finiteness results on oblique polyhedral graphs are generalized for maps on orientable surfaces. In the second part of the work oblique structures in arbitrary graphs are investigated. A graph is called vertex-oblique if any two vertices differ in the degree sequence of their neighbors. It is shown that even under additional restrictive properties for the considered graphs the set of vertex-oblique graphs is infinite. Moreover, it is proved, that the probability of a random graph to be vertex-oblique tends to 1 as the order of the graph tends to infinity if the probability p of an edge to belong to the edge set of the graph is within given bounds.

Zitieren

Zitierform:

Schreyer, Jens: Olique graphs. 2005.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Export