Abstract
In this paper we give a lower bound of the circumference of a graph in terms of girth and the number of edges. It is shown that a graph of girth at least g ≥ 4 with n vertices and at least m ≥ n edges contains a cycle of length at least (g - 2)m/(n - 2). In particular, for the case g = 4, an analogous result for 2-edge-connected weighted graphs is given. Moreover, the extremal case is characterized in both results.
Original language | English |
---|---|
Pages (from-to) | 427-438 |
Number of pages | 12 |
Journal | SUT Journal of Mathematics |
Volume | 50 |
Issue number | 2 |
Publication status | Published - 2014 |
Keywords
- Circumference
- Cycle
- Heavy cycle
- Weighted graph
ASJC Scopus subject areas
- Mathematics(all)