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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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).

Improve this answer
$\endgroup$
1
  • 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, 2018 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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