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

Mohammad Hailat

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.

Full Text: PDF

How to Cite this Article:

Mohammad Hailat, An Upper Bound on the Number of Edges of Graphs containing No r Vertex-Disjoint Odd Cycles, Journal of Mathematical and Computational Science, Vol 8, No 6 (2018), 644-653

Copyright © 2018 Mohammad Hailat. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

J. Math. Comput. Sci.

ISSN: 1927-5307

Editorial Office: jmcs@scik.org

 

Copyright ©2018 JMCS