The authors give several upper bounds on the number of edges \(q\) in a graph, in terms of its order \(p\) and girth \(g\) (and, in certain cases, minimum degree is also involved). In particular, one upper bound has the asymptotic order \(p^{1+2/(g-1)}\) for \(g\) odd; the conjectured correct asymptotic value is \(p^{1+2/g}\). Another interesting example is the inequality \(g\leq 2+2\log_ k(p/4)\) where \(k=\lfloor q/p\rfloor\geq 2\). Asymptotic and numerical comparisons are included.
Cites work
Cited in
(18)- Edges in graphs with large girth
- Can we create large \(k\)-cores by adding few edges?
- Some further results on the eccentric distance sum
- Density of balanced 3-partite graphs without 3-cycles or 4-cycles
- On the price of stability of some simple graph-based hedonic games
- PROPERTY A AND GRAPHS WITH LARGE GIRTH
- Approximability Distance in the Space of H-Colourability Problems
- Recherche à voisinage variable de graphes extrémaux 26. Nouveaux résultats sur la maille
- scientific article; zbMATH DE number 5642607 (Why is no real title available?)
- Girth of sparse graphs
- scientific article; zbMATH DE number 147630 (Why is no real title available?)
- scientific article; zbMATH DE number 2058910 (Why is no real title available?)
- scientific article; zbMATH DE number 4114669 (Why is no real title available?)
- Nonpositive sectional curvature for (𝑝,𝑞,𝑟)-complexes
- Higher dimensional Moore bounds
- Faces in girth-saturated graphs on surfaces
- Distance hedonic games
- The NIP graph of a social welfare function
This page was built for publication: Edges in graphs with large girth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1180673)
