A sufficient condition for a graph to be hamiltonian |
| |
Authors: | Dr Norbert Köhler |
| |
Institution: | (1) Fach bereich Mathematik, Technische Universität Berlin, Straße des 17. Juni 135, D-1000 Berlin 12 |
| |
Abstract: | Those non-hamiltonian graphsG withn vertices are characterized, which satisfy the Ore-type degree-conditiond(x)+d(y) n–2 for each pairx,y M of different nonadjacent vertices whereM consists of two vertices ofG. As an application a theorem on hamiltonian connectivity of graphs is given. Furthermore, a condition is presented which is sufficient for the existence of a covering of a graph by two disjoint paths with prescribed set of startpoints and prescribed set of endpoints. A class of graphs is described which have no covering of this kind. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|