PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
April 4, 20260 citationsOpen Access

Maximal cycles in graphs of large girth

View Full Paper
JFJun FujisawaKOKatsuhiro Ota

Key Points

  • To establish a lower bound for the circumference of a graph based on its girth and edge count.
  • Develop mathematical bounds for graph circumference based on girth and edge relationships.
  • Examine the case for 2-edge-connected weighted graphs specifically when girth is 4.
  • Characterize the extremal conditions for the main results.
  • Demonstrates a cycle length of at least (g - 2)m/(n - 2) for graphs with girth at least g.
  • For graphs with girth of 4, analogous results confirm the findings for weighted graphs.
  • Identifies conditions for extremal cases relevant to defined bounds.

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.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Fujisawa et al. (2014) studied this question.

synapsesocial.com/papers/69d0a9c8659487ece0fa4184https://doi.org/10.20604/00000835
Ask AI
Helpful
Bookmark
Share
View Full Paper

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

  1. 1On extremal numbers of the triangle plus the four-cycle2025
  2. 2Edges In Graphs With Large Girth1991
  3. 3Laplacian eigenvalue distribution and girth of graphs2026
  4. 4The Extremal Number of Cycles with All Diagonals2024 · 4 citations
  5. 5On the number of edges in a K5-minor-free graph of given girth2024