# Clique Size in “Triangle Regular” Graphs

Let $$G(V,E)$$ be a connected, simple and undirected graph with the additional constraint, that each edge is contained in the same number $$k_T$$ of triangles; i.e. that $$G$$ is regular w.r.t. to that number of triangles.

Question:
what are non-trivial bounds on the size of the maximal clique of $$k_T$$-regular connected graphs with $$n$$ vertices as a function of $$k_T$$ and $$n$$?

for $$k_T=2$$ the minimal clique-size is $$4$$ iff $$n=4$$ and $$3$$ iff $$n>4$$ and the question amounts to whether triangle-regularity allows for sharper estimates of the maximal clique size.

Perhaps this is a little trivial, but for any $$k_T$$, we can construct a graph $$G$$ on $$3k_T$$ vertices with $$\omega (G)=3$$: take a balanced 3-partite graph on $$3k_T$$ vertices (the Turán graph).
• You can actually do a similar construction for infinitely values of $n$ (and $k_T$ fixed). Start with an arbitrary connected cubic triangle-free graph $G$, on $N$ vertices. For each edge $uv$ add a set $S_{uv}$ of $k_T$ vertices, and define the graph $H$ as follows: the vertex-set is the union of the sets $S_{uv}$ (so there are $3Nk_T/2$ vertices), and for each vertex $v$ of $G$, with neighbors $x,y,z$ in $G$ we add a Turan graph with partite sets $S_{ux}$, $S_{uy}$, $S_{uz}$. Since $G$ is triangle-free, it can be checked that each edge is in $k_T$ triangles and $H$ has clique-number 3. – Louis Esperet Nov 30 '18 at 9:05