PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
April 25, 2024Discrete Mathematics0 citationsOpen Access

On the number of edges in a K5-minor-free graph of given girth

View Full Paper
JBJános Barát

Key Points

Key points are not available for this paper at this time.

Abstract

We consider the following question: what is the maximum number of edges in a K5-minor-free graph with n vertices and girth g, where n≥4? With no restriction on the girth (g=3), it is well known that the answer is 3n−6. For g=4 and n≥5, the answer is known to be 3n−9. For g=5, we show there are two graphs with 9n−205 edges and every other graph contains at most 9n−215 edges and equality holds for infinitely many graphs. For g=8 and large n the answer is 3n−92. For g=4k, k≥2, we conjecture the answer is 3k3k−2(n−3).

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

János Barát (2024) studied this question.

synapsesocial.com/papers/68e6dabdb6db64358765728bhttps://doi.org/10.1016/j.disc.2024.114042
Ask AI
Helpful
Bookmark
Share
View Full Paper