|
|||||
|
|
On the sum of the reciprocals of cycle lengths in sparse graphs |
|
| Authors: | A Gyárfás H J Prömel B Voigt E Szemerédi |
| Institution: | 1. Computer and Automation Institute of the Hungarian Academy of Sciences, Kende u. 13-17, 1111, Hungary 2. Fakult?t für Mathematik, Universit?t Bielefeld, 4800, Bielefeld 1, West Germany 3. Mathematical Institute of the Hungarian Academy of Sciences, P.O.B. 127, 1364, Budapest, Hungary |
| Abstract: | For a graphG let ℒ(G)=Σ{1/k contains a cycle of lengthk}. Erdős and Hajnal 1] introduced the real functionf(α)=inf {ℒ (G)|E(G)|/|V(G)|≧α} and suggested to study its properties. Obviouslyf(1)=0. We provef (k+1/k)≧(300k logk)−1 for all sufficiently largek, showing that sparse graphs of large girth must contain many cycles of different lengths. |
| Keywords: | 05 C 38 05 C 05 |
| 本文献已被 SpringerLink 等数据库收录！ | |