2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Louis Esperet Nov 30 '18 at 9:05
2
$\begingroup$

I'd be a bit surprised if there are any much stronger bounds than for general graphs. As Puck points out, we can attain the trivial minimum. Or we can do the trivial maximum: a clique on k_T+2 vertices.

And furthermore a random graph will be very close to triangle-regular (though it's not actually regular) and it's likely that there are (for sensible values of the parameters) triangle-regular graphs which look like random graphs. These will presumably be extremal for the Ramsey version of your question.

In order for this to be interesting, I think you need to say a bit more about the graphs you're interested in; number of edges, or degrees, or structure.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.