An Upper Bound on the Number of Edges of Graphs containing No r Vertex-Disjoint Odd Cycles

Abstract

In [5], we found an upper bound on the number of edges, $\mathcal{E}(G)$, of a graph $G$ containing no $r$ vertex-disjoint cycles of length 3. In this paper we generalize this result to graphs containing no $r$ vertex-disjoint cycles of length $2k+1$. We showed that $\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,2k+1})$, the class of all graphs on $n$ vertices containing no $r$ vertex-disjoint cycles of length $2k+1$. Determination of the maximum number of edges in a given graph that contains no specific subgraphs is one of the important problems in graph theory. Solving such problems has attracted the attention of many researchers in graph theory.