Abstract

An important problem in graph theory is that of determining the maximum number of edges in a given graph $G$ that contains no specific subgraphs. This problem has attracted the attention of many researchers. An example of such a problem is the determination of an upper bound on the number of edges of a graph that has no triangles. In this paper, we let $\mathcal{G}(n,V_{r,3})$ denote the class of graphs on $n$ vertices containing no $r$-vertex-disjoint cycles of length $3$. We show that for large $n$, $\mathcal{E}(G)\les \lfloor \frac{(n-r+1)^2}{4} \rfloor +(r-1)(n-r+1)$ for every $G\in\mathcal{G}(n,V_{r,3})$. Furthermore, equality holds if and only if $G=\Omega(n,r)=K_{r-1,\lfloor \frac{n-r+1}2\rfloor,\lceil \frac{n-r+1}2\rceil}$ where $\Omega(n,r)$ is a tripartite graph on $n$ vertices.

This work is licensed under a Creative Commons Attribution 4.0 License.