Sättigung von kanten-geordneten Graphen

Für einen kanten-geordneten Graphen G sagen wir, dass ein n-vertikaler kanten-ordneter Graph H G-saturiert ist, wenn er G-frei ist und das Hinzufügen einer neuen Kante mit einem neuen Label zu H eine Kopie von G einführt. Die Sättigungsfunktion beschreibt die minimale Anzahl von Kanten eines G-saturierten Graphen. Insbesondere untersuchen wir die Größenordnung dieser Funktionen. Für (ungeordnete) Graphen, 0-1-Matrizen und vertikal geordnete Graphen konnte gezeigt werden, dass die Sättigungsfunktionen entweder O(1) oder (n) sind. Wir zeigen, dass die Sättigungsfunktionen von kanten-geordneten Graphen ebenfalls entweder O(1) oder (n) sind. Durch das Finden von kanten-geordneten Graphen, deren Sättigungsfunktionen superlinear sind, zeigen wir jedoch, dass ein solches Dichotomierergebnis im Allgemeinen nicht gilt. Darüber hinaus betrachten wir das Semisaturationsproblem von kanten-geordneten Graphen, eine Variante des Sättigungsproblems, bei dem wir nicht verlangen, dass H G-frei ist. Wir zeigen eine allgemeine obere Grenze O(n n) und charakterisieren kanten-ordnete Graphen mit begrenzter Semisaturationsfunktion. Wir präsentieren auch verschiedene Klassen von Graphen mit begrenzten, linearen und superlinearen (semi) Sättigungsfunktionen. Unterwegs definieren wir eine natürliche Variante des obigen Problems, bei dem die neue Kante das kleinste Label erhalten muss. Das Verhalten der beiden Varianten weist viele Ähnlichkeiten auf, was uns motivierte, auch die zweite Variante eingehend zu untersuchen.