Havel-Hakimi algorithm

from Wikipedia, the free encyclopedia

The Havel-Hakimi algorithm (or the Havel-Hakimi method) is a method from graph theory with which the existence of a simple graph for a given valence sequence can be determined and constructed.

Surname

The Havel-Hakimi theorem was published in 1955 by the Czech mathematician Vàclav J. Havel. Because the theorem was initially only published in the Czech language with a German and Russian summary, it was initially hardly noticed in science. Another proof was published in 1962 independently of Seifollah Louis Hakimi (1932-2005) in the SIAM Journal on Applied Mathematics .

literature

  • Václav Havel: Poznámka o existenci konečných grafů. In: Časopis pro pěstování matematiky (Volume 80, No. 4). ISSN = 0528-2195, ( online ), (Czech, summary in Russian and German).
  • Antal Iványi u. a .: On Erdös-Gallai and Havel-Hakimi algorithms . In: Acta Universitatis Sapientiae. Informatica. Vol. 3, 2nd 2011. pp. 230-268

Individual evidence

  1. ↑ Matches for: MR = 148049 definition on mathscinet.ams.org. Retrieved September 10, 2018.