Pósa’s theorem in graph theory

E895558

result in extremal graph theory theorem in graph theory

Pósa’s theorem in graph theory is a result that gives a sufficient degree condition for a finite graph to contain a Hamiltonian cycle.

Try in SPARQL Jump to: Surface forms Statements Referenced by

Observed surface forms (1)

Surface form	Occurrences
Pósa’s theorem	0

Statements (41)

Predicate	Object
instanceOf	result in extremal graph theory ⓘ theorem in graph theory ⓘ
appearsIn	Bondy and Murty’s Graph Theory with Applications NERFINISHED ⓘ standard graduate texts on graph theory ⓘ
appliesTo	finite simple graphs ⓘ
assumes	graph has at least three vertices ⓘ
category	Hamiltonian graph theorems ⓘ degree sequence theorems in graph theory ⓘ
concerns	Hamiltonian cycle existence ⓘ
field	discrete mathematics ⓘ extremal graph theory ⓘ graph theory ⓘ
generalizes	Dirac’s degree condition for Hamiltonicity ⓘ
gives	sufficient condition for existence of Hamiltonian cycle ⓘ
hasConsequence	gives families of Hamiltonian graphs from degree sequences ⓘ provides extremal bounds for non-Hamiltonian graphs ⓘ
hasFormulation	If G is a graph on n ≥ 3 vertices with degree sequence d1 ≤ d2 ≤ … ≤ dn and for every integer k with 1 ≤ k < n/2, dk ≥ k+1 or d_{n−k} ≥ n−k, then G is Hamiltonian ⓘ
hasWeakerFormulation	If G is a graph on n ≥ 3 vertices with degree sequence d1 ≤ d2 ≤ … ≤ dn and for every integer k with 1 ≤ k < n/2, dk ≥ k+1 or dn−k ≥ n−k, then G has a Hamiltonian cycle ⓘ
implies	graph is Hamiltonian under its degree conditions ⓘ
isToolFor	proving Hamiltonicity of dense graphs ⓘ studying degree sequence characterizations of Hamiltonian graphs ⓘ
namedAfter	Lajos Pósa NERFINISHED ⓘ
namedEntity	true ⓘ
originalLanguage	Hungarian ⓘ
publishedIn	Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei NERFINISHED ⓘ
relatedConcept	Chvátal–Erdős theorem NERFINISHED ⓘ Hamiltonian path NERFINISHED ⓘ closure of a graph ⓘ
relatedTo	Chvátal’s theorem NERFINISHED ⓘ Ore’s theorem NERFINISHED ⓘ
strengthens	Dirac’s theorem NERFINISHED ⓘ
subject	Hamiltonian cycles ⓘ degree conditions in graphs ⓘ
typeOfCondition	degree sequence condition ⓘ
usedIn	graph theory textbooks ⓘ research on Hamiltonian properties of graphs ⓘ sufficient conditions for Hamiltonian cycles ⓘ
usesConcept	Hamiltonian graph ⓘ nondecreasing degree sequence ⓘ vertex degree ⓘ
yearProved	1962 ⓘ

Referenced by (1)

Full triples — surface form annotated when it differs from this entity's canonical label.

Lajos Pósa → knownFor → Pósa’s theorem in graph theory ⓘ