On maximal triangle-free graphs |
| |
Authors: | Paul Erds Ron Holzman |
| |
Institution: | Paul Erdős,Ron Holzman |
| |
Abstract: | A triangle-free graph is maximal if adding any edge will create a triangle. The minimal number of edges of a maximal triangle-free graph on n vertices having maximal degree at most D is denoted by F(n, D). We determine the value of limn-∞ F(n, cn)/n for 2/5 < c < 1/2. This investigation continues work done by Z. Füredi and Á. Seress. Our result is contrary to a conjecture of theirs. |
| |
Keywords: | |
|
|