Article contents
On the Maximum Number of Triangles in Wheel-Free Graphs
Published online by Cambridge University Press: 12 September 2008
Abstract
Gallai [1] raised the question of determining t(n), the maximum number of triangles in graphs of n vertices with acyclic neighborhoods. Here we disprove his conjecture (t(n) ~ n2/8) by exhibiting graphs having n2/7.5 triangles. We improve the upper bound [11] of (n2 − n)/6 to t(n) ≤; n2/7.02 + O(n). For regular graphs, we further decrease this bound to n2/7.75 + O(n).
- Type
- Research Article
- Information
- Copyright
- Copyright © Cambridge University Press 1994
References
- 1
- Cited by