A reminder: this is today.
------------------------------------------------------
On 2023-11-20 10:21, Mykhaylo Tyomkyn wrote:
Dear all,
There will be a noon seminar this Thursday, 23 November, given by Anna Limbach. Please find the talk details below.
Best regards, Misha Tyomkyn.
Anna Limbach Czech Academy of Sciences November 23, 2023, 12:20 in S6
Abstract We prove that the clique graph operator k is divergent on a (not necessarily finite) locally cyclic graph G with minimum degree δ ≥ 6 if and only if 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 G are non-isomorphic, the graph G is called k-divergent; otherwise, it is k-convergent.
While it has been shown for finite locally cyclic graphs that those with minimum degree δ ≥ 7 are k-convergent while the 6-regular ones are k-divergent, we obtain a full characterisation of k-convergent locally cyclic graphs with minimum degree δ ≥ 6.
We start by showing that a k-convergent connected graph has a k-convergent universal triangular cover. Conversely, we give a sufficient condition 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. On this class, clique convergence is characterised using an explicit construction of the iterated clique graphs and a finite yet divergent parameter for the k-divergent case. Furthermore, it is shown that locally cyclic graphs with minimum degree δ ≥ 6 are k-convergent if and only if their universal covers are k-convergent. This way, the characterisation is completed.
This is joint work with Markus Baumeister and Martin Winter.
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz