On the clique dynamics of locally cyclic graphs

Limbach, Anna Margarethe; Koster, Arie Marinus; Triesch, Eberhard

doi:43315

On the clique dynamics of locally cyclic graphs

Limbach, Anna Margarethe^RWTH*

2024

Verantwortlichkeitsangabevorgelegt von Anna Margarethe Limbach, M.Sc.

ImpressumAachen : RWTH Aachen University 2024

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2024

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Triesch, Eberhard (Thesis advisor)^RWTH* ; Koster, Arie Marinus (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2024-05-24

Online
DOI: 10.18154/RWTH-2024-05608
URL: https://publications.rwth-aachen.de/record/987344/files/987344.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
clique divergence (frei) ; clique dynamics (frei) ; hexagonal lattice (frei) ; infinite graphs (frei) ; iterated clique graphs (frei) ; locally cyclic graphs (frei) ; triangular graph covers (frei) ; triangulated surfaces (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
In dieser Arbeit wird bewiesen, dass der Cliquenoperator k auf einem (nichtnotwendigerweise endlichen) lokal zyklischen Graphen G mit Minimalgrad δ ≥ 6genau dann divergent ist, wenn seine universelle Dreiecks-Überlagerung beliebig große dreieckförmige Teilgraphen enthält. Für einen endlichen Graphen G ist dies äquivalent dazu, dass G 6-regulär ist. Ein Graph heißt lokal zyklisch, wenn die offene Nachbarschaft N G (v) jedes Knoten v einen Kreis induziert. Der Cliquengraph kG eines Graphen G hat die maximalen Cliquen von G als Knoten und seine Kanten sind durch Paare mit nicht-leeren Schnitten gegeben. Der (n + 1)-te iterierte Cliquengraph ist rekursiv als der Cliquengraph des n-ten iterierten Cliquengraphen definiert. Falls alle iterierten Cliquengraphen von G nicht-isomorph sind, wird der Graph als cliquen-divergent bezeichnet, anderenfalls als cliquen-konvergent. Während es für endliche lokal zyklische Graphen bereits bekannt ist, dass solche mit Minimalgrad δ ≥ 7 cliquen-konvergent und 6-reguläre cliquen-divergent sind, gibt diese Arbeit eine vollständige Charakterisierung der Cliquen-Konvergenz lokalzyklischen Graphen mit Minimalgrad δ ≥ 6.Zu Beginn wird gezeigt, dass ein cliquen-konvergenter, zusammenhängender Graph eine cliquen-konvergente universelle Dreiecks-Überlagerung hat. Umgekehrt wird eine hinreichende Bedingung angegeben, unter welcher die Konvergenz der universellen Dreiecks-Überlagerung die Konvergenz des Graphen selbst impliziert. Lokal zyklische Graphen mit Minimalgrad δ ≥ 6, welche einfach dreiecks-zusam-menhängend sind, sind ihre eigenen universellen Dreiecks-Überlagerungen. Für diese Graphenklasse wird Cliquen-Konvergenz mit Hilfe einer expliziten Konstruktion der iterierten Cliquengraphen sowie eines endlichen aber divergenten Graphenparameters für den cliquen-divergenten Fall charakterisiert. Darüber hinaus wird gezeigt, dass lokal zyklische Graphen mit Minimalgrad δ ≥ 6 genau dann cliquen-konvergent sind, wenn ihre universellen Dreiecks-Überlagerungen es auch sind. Auf diese Weise wird die Charakterisierung vervollständigt.

In this thesis, it is proven that the clique graph operator k is divergent on a (notnecessarily finite) locally cyclic graph G with minimum degree δ ≥ 6 if and onlyif the universal triangular cover of G contains arbitrarily large triangular-shaped subgraphs. For finite G, this is equivalent to G being 6-regular. A graph is called locally cyclic if the open neighbourhood N G (v) of each vertex v induces a cycle. The clique graph kG of a graph G has the maximal complete subgraphs of G as its vertices and its edges are those pairs with non-empty intersection. The (n + 1)-st iterated clique graph is recursively defined as the clique graph of the n-th iterated clique graph. If all iterated clique graphs of Gare non-isomorphic, the graph G is called clique divergent; otherwise, it is clique convergent. While it has been shown for finite locally cyclic graphs that those with minimum degree δ ≥ 7 are clique convergent while the 6-regular ones are clique divergent, this thesis gives a full characterisation of clique convergent locally cyclic graphs with minimum degree δ ≥ 6.In the beginning, it is shown that a clique convergent connected graph has a clique convergent universal triangular cover. Conversely, a sufficient condition is given under which the clique convergence of the universal triangular cover of a graph implies the clique convergence of the graph itself. Locally cyclic graphs with minimum degree δ ≥ 6 which are triangularly simply connected are their own universal covers and they are referred to as pikas throughout this thesis. On the class of pikas, clique convergence is characterise dusing an explicit construction of the iterated clique graphs and a finite yet divergent parameter for the clique divergent case. Furthermore, it is shown thatlocally cyclic graphs with minimum degree δ ≥ 6 are clique convergent if and only if their universal covers are clique convergent. This way, the characterisation is completed.

OpenAccess:
PDF
(additional files)