A sufficient condition for a graph to be hamiltonian

descriptionPublicationkeyboard_double_arrow_right Article 01 Jun 1981 Germany English Publisher:Springer Science and Business Media LLCJournal:Monatshefte f�r Mathematik, volume 92, pages 105-116 (issn: 0026-9255, eissn: 1436-5081,

Copyright policy )

Authors: Köhler, Norbert;

doi: 10.1007/bf01303743

A sufficient condition for a graph to be hamiltonian

- Summary
- Subjects
- Metrics

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.

Country

Germany

Related Organizations

Keywords

Eulerian and Hamiltonian graphs, 510.mathematics, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Hamiltonian graphs, Structural characterization of families of graphs, Article

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average