Tianying Xie

For a fixed graph H $H$ , we say that an edge-colored graph G $G$ is weakly H $H$ -rainbow saturated if there exists an ordering e 1 , e 2 , … , e m ${e}_{1},{e}_{2},\ldots ,{e}_{m}$ of E ( G ¯ ) $E(\bar{G})$ such that, for any list c 1 , c 2 , … , c m ${c}_{1},{c}_{2},\ldots ,{c}_{m}$ of pairwise distinct colors from N ${\mathbb{N}}$ , the nonedges e i ${e}_{i}$ in color c i ${c}_{i}$ can be added to G $G$ , one at a time, so that every added edge creates a new rainbow copy of H $H$ .

1 INTRODUCTION We investigate the number of triangles guaranteed in regular graphs with edge density below one-half. To be precise, for positive integers n $n$ and k $k$ , we define t ( n , k ) $t(n,k)$ to be the minimum number of triangles over all k $k$ -regular graphs on n $n$ vertices.