I am very interested in the maximum number of triangles could a connected graph with $n$ vertices and $m$ edges have. For example, if $m\leq n−1$, this number is $0$, if $m=n$, this number is $1$, if $m=n+1$, this number is $2$, and if $m=n+2$, this number is $4$.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ If we omit the restriction of connectedness, see this question: math.stackexchange.com/questions/823481/… Also note that we can achieve connectedness with a few number of edges, so the order of magnitude of the number of triangles is the same without your restriction. $\endgroup$– Daniel SoltészJun 22, 2015 at 10:55
-
$\begingroup$ @Soltész I want to get a good bound in terms of $m-n+1$. I believe this number could be bounded by $(m-n+1)^2$ roughly. $\endgroup$– Xueyi HuangJun 22, 2015 at 11:10
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
It is a bound and since it is very long, I wrote it an answer, may be it can be helpful.
Let $G$ be a connected graph with $n$ vertices and $m$ edges. Suppose the eigenvalues of this graph are $\lambda_1\geq \lambda_2\geq\ldots\geq\lambda_n$. We know that $\sum{\lambda_i^3}=6\Delta_G$, where $\Delta_G$ counts the total number of triangles of the graph $G$.
Also,we have:
$$\lambda_1\leq\sqrt{2m-\delta(n-1)+\Delta(\delta-1)}.$$
Since your graph is connected, we can set $\delta=1$ and obtain: $$\lambda_1\leq\sqrt{2m-n+1}.$$
So we have:
$$\Delta_G\leq\frac{n}{6}(2m-n+1)^{\frac{3}{2}},$$
as you wanted in your comments.
Actually, you can get more information from this method since we exactly know when the upper inequalities which I used are equality for which graphs. You can search for "SHARP UPPER BOUNDS OF SPECTRAL RADIUS OF GRAPHS" or similar keywords.
-
$\begingroup$ Thanks, this method is very helpful. This bound can be easily improved as $\Delta_G\leq\frac{n-1}{6}(2m-n+1)^{\frac{3}{2}}$. $\endgroup$ Jun 27, 2015 at 8:07
-
$\begingroup$ This can be further improved with $\Delta_G \leq m^{3/2}$. $\endgroup$– orezvaniFeb 16, 2017 at 2:58
$\begingroup$
$\endgroup$
1
This question (together with massive generalizations) is answered in I. Rivin's 2001 paper.
answered Apr 15, 2016 at 14:37
-
$\begingroup$ The paper seems interesting. It has some trivial results, but one up vote for the very nice style of writing. $\endgroup$– ShahroozApr 16, 2016 at 9:28