An extremal problem for cycles in hamiltonian graphs |
| |
| Authors: | George R T Hendry Stephan Brandt |
| |
| Institution: | (1) Department of Mathematical Science, The Edward Wright Building, University of Aberdeen, Dunbar Street, AB9 2TY Aberdeen, Scotland;(2) Graduiertenkolleg  Algorithmishe Diskrete Mathematik , FB Mathematik, Freie Universität Berlin, Arnimallee 2-6, 14195 Berlin, Germany |
| |
| Abstract: | For integersp andr with 3  r p – 1, letf(p, r) denote the maximum number of edges in a hamiltonian graph of orderp which does not contain a cycle of lengthr. Results from literature on the determination off(p, r) are collected and a number of new lower bounds, many of which are conjectured to be best possible, are given. The main result presented is the proof thatf(p, 5) = (p – 3)2/4 + 5 for oddp  11.George Hendry died during the publication process.Supported by Deutsche Forschungsgemeinschaft (DFG), Grant We 1265. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
