Return to Answer

As Gerhard Paseman mentions, this may be as hard as enumerating all graphs. If that is indeed the case, you may want to check out this paper by Alon, Yuster and Zwick. In it, they mention that given a graph $G=(V,E)$, it is easy to count the number of triangles in $G$ in $O(V^\omega)$-time, where $\omega<2.376$ is the exponent of matrix multiplication. They generalize this by presenting an $O(V^\omega)$ algorithm for counting the number of $k$-cycles in a graph for $k \leq 7$. An elegant technique in this area is the so-called colour-coding method.

Edit 1. A partial answer to unknown's question is that, $k \in T_n$ for all $k \leq n^{3/2}$ ($n$ large). To see this choose $j$ maximal such that $\binom{j}{3} \leq k$. By making a clique on $j$ vertices, and then taking a disjoint union of triangles on the remaining vertices, we can make a graph with exactly $k$ triangles provided $k-\binom{j}{3} \leq \frac{n-j}{3}$. After some number crunching, this is possible provided $k \leq n^{3/2}$.

Edit 2. Here is a some information for $k$ which are not in $T_n$. As Gerhard mentions, removing an edge from $K_n$ destroys exactly $n-2$ triangles. Thus, $\binom{n}{3} - t \notin T_n$ for all $t=1, \dots, n-3$. The next triangle-densest graph is obtained by removing two incident edges, which destroys $2n-5$ triangles. Thus, $\binom{n}{3} - t \notin T_n$, for $t=n-1, n, \dots, 2n-6$. The next two densest triangle-densest graph are obtained by removing a matching of size 2, which destroys $2n-4$ triangles, or the edges of a triangle, which destroys $3n-8$ triangles. Thus, $\binom{n}{3}-t \notin T_n$ for $t=2n-3, 2n-2, \dots, 3n-9$.

As Gerhard Paseman mentions, this may be as hard as enumerating all graphs. If that is indeed the case, you may want to check out this paper by Alon, Yuster and Zwick. In it, they mention that given a graph $G=(V,E)$, it is easy to count the number of triangles in $G$ in $O(V^\omega)$-time, where $\omega<2.376$ is the exponent of matrix multiplication. They generalize this by presenting an $O(V^\omega)$ algorithm for counting the number of $k$-cycles in a graph for $k \leq 7$. An elegant technique in this area is the so-called colour-coding method.

Edit 1. A partial answer to unknown's question is that, $k \in T_n$ for all $k \leq n^{3/2}$ ($n$ large). To see this choose $j$ maximal such that $\binom{j}{3} \leq k$. By making a clique on $j$ vertices, and then taking a disjoint union of triangles on the remaining vertices, we can make a graph with exactly $k$ triangles provided $k-\binom{j}{3} \leq \frac{n-j}{3}$. After some number crunching, this is possible provided $k \leq n^{3/2}$.

Edit 2. Here is some information for $k$ which are not in $T_n$. As Gerhard notes, removing an edge from $K_n$ destroys exactly $n-2$ triangles. Thus, $\binom{n}{3} - t \notin T_n$ for all $t=1, \dots, n-3$. The next triangle-densest graph is obtained by removing two incident edges, which destroys $2n-5$ triangles. Thus, $\binom{n}{3} - t \notin T_n$, for $t=n-1, n, \dots, 2n-6$. The next two triangle-densest graphs are obtained by removing a matching of size 2, which destroys $2n-4$ triangles, or the edges of a triangle, which destroys $3n-8$ triangles. Thus, $\binom{n}{3}-t \notin T_n$ for $t=2n-3, 2n-2, \dots, 3n-9$.

As Gerhard Paseman mentions, this may be as hard as enumerating all graphs. If that is indeed the case, you may want to check out this paper by Alon, Yuster and Zwick. In it, they mention that given a graph $G=(V,E)$, it is easy to count the number of triangles in $G$ in $O(V^\omega)$-time, where $\omega<2.376$ is the exponent of matrix multiplication. They generalize this by presenting an $O(V^\omega)$ algorithm for counting the number of $k$-cycles in a graph for $k \leq 7$. An elegant technique in this area is the so-called colour-coding method.

Edit. A partial answer to unknown's question is that, $k \in T_n$ for all $k \leq n^{3/2}$ ($n$ large). To see this choose $j$ maximal such that $\binom{j}{3} \leq k$. By making a clique on $j$ vertices, and then taking a disjoint union of triangles on the remaining vertices, we can make a graph with exactly $k$ triangles provided $k-\binom{j}{3} \leq \frac{n-j}{3}$. After some number crunching, this is possible provided $k \leq n^{3/2}$.

As Gerhard Paseman mentions, this may be as hard as enumerating all graphs. If that is indeed the case, you may want to check out this paper by Alon, Yuster and Zwick. In it, they mention that given a graph $G=(V,E)$, it is easy to count the number of triangles in $G$ in $O(V^\omega)$-time, where $\omega<2.376$ is the exponent of matrix multiplication. They generalize this by presenting an $O(V^\omega)$ algorithm for counting the number of $k$-cycles in a graph for $k \leq 7$. An elegant technique in this area is the so-called colour-coding method.

Edit 1. A partial answer to unknown's question is that, $k \in T_n$ for all $k \leq n^{3/2}$ ($n$ large). To see this choose $j$ maximal such that $\binom{j}{3} \leq k$. By making a clique on $j$ vertices, and then taking a disjoint union of triangles on the remaining vertices, we can make a graph with exactly $k$ triangles provided $k-\binom{j}{3} \leq \frac{n-j}{3}$. After some number crunching, this is possible provided $k \leq n^{3/2}$.

Edit 2. Here is a some information for $k$ which are not in $T_n$. As Gerhard mentions, removing an edge from $K_n$ destroys exactly $n-2$ triangles. Thus, $\binom{n}{3} - t \notin T_n$ for all $t=1, \dots, n-3$. The next triangle-densest graph is obtained by removing two incident edges, which destroys $2n-5$ triangles. Thus, $\binom{n}{3} - t \notin T_n$, for $t=n-1, n, \dots, 2n-6$. The next two densest triangle-densest graph are obtained by removing a matching of size 2, which destroys $2n-4$ triangles, or the edges of a triangle, which destroys $3n-8$ triangles. Thus, $\binom{n}{3}-t \notin T_n$ for $t=2n-3, 2n-2, \dots, 3n-9$.

As Gerhard Paseman mentions, this may be as hard as enumerating all graphs. If that is indeed the case, you may want to check out this paper by Alon, Yuster and Zwick. In it, they mention that given a graph $G=(V,E)$, it is easy to count the number of triangles in $G$ in $O(V^\omega)$-time, where $\omega<2.376$ is the exponent of matrix multiplication. They generalize this by presenting an $O(V^\omega)$ algorithm for counting the number of $k$-cycles in a graph for $k \leq 7$. An elegant technique in this area is the so-called colour-coding method.

As Gerhard Paseman mentions, this may be as hard as enumerating all graphs. If that is indeed the case, you may want to check out this paper by Alon, Yuster and Zwick. In it, they mention that given a graph $G=(V,E)$, it is easy to count the number of triangles in $G$ in $O(V^\omega)$-time, where $\omega<2.376$ is the exponent of matrix multiplication. They generalize this by presenting an $O(V^\omega)$ algorithm for counting the number of $k$-cycles in a graph for $k \leq 7$. An elegant technique in this area is the so-called colour-coding method.

Edit. A partial answer to unknown's question is that, $k \in T_n$ for all $k \leq n^{3/2}$ ($n$ large). To see this choose $j$ maximal such that $\binom{j}{3} \leq k$. By making a clique on $j$ vertices, and then taking a disjoint union of triangles on the remaining vertices, we can make a graph with exactly $k$ triangles provided $k-\binom{j}{3} \leq \frac{n-j}{3}$. After some number crunching, this is possible provided $k \leq n^{3/2}$.