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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .