Theorem of Ghouila-Houri

In the theory of directed graphs , one of the branches of graph theory , Ghouila-Houri's theorem is the counterpart to Dirac's theorem in the theory of undirected graphs . The sentence goes back to a work by the French mathematician Alain Ghouila-Houri from 1960. Several authors emphasize that the proof of Ghouila-Houri 's theorem is a lot more difficult than that of Dirac' s.

Formulation of the sentence

The sentence can be summarized as follows:

Let a finite directed graph be given . ${\displaystyle D}$

${\displaystyle D}$is strongly connected and also has the property that at every node for the degree with respect to the number of nodes the inequality is consistently ${\displaystyle v}$ ${\displaystyle d_{G}(v)=d_{G}^{-}(v)+d_{G}^{+}(v)}$ ${\displaystyle n(D)}$

${\displaystyle {d_{G}}(v)\geq n(D)}$

is satisfied.

Then it has a Hamiltonian cycle , i.e. a cycle on which all nodes occur exactly once. ${\displaystyle D}$ ${\displaystyle D}$

In particular, this statement applies to the case that at each node the two inequalities with regard to the input degree and output degree ${\displaystyle v}$

${\displaystyle d_{G}^{-}(v)\geq {\frac {n(D)}{2}}}$

and

${\displaystyle d_{G}^{+}(v)\geq {\frac {n(D)}{2}}}$

are fulfilled.

Tightening

Ghouila-Houri's theorem has been tightened up by several authors; so in 1973 by M. Meyniel as follows:

Is a finite, strongly connected directed graph, the one for two different non- neighboring nodes and the inequality ${\displaystyle D}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$

${\displaystyle {d_{G}}(v_{1})+{d_{G}}(v_{2})\geq 2n(D)-1}$.

fulfilled, then has a Hamiltonian cycle. ${\displaystyle D}$

literature

• Alain Ghouila-Houri: Une condition suffisante d'existence d'un circuit hamiltonien . In: Comptes rendus de l'Académie des sciences Paris . tape 251 , 1960, pp. 495-497 ( MR0114771 ).
• Rudolf Halin : Graph Theory . 2nd, revised and expanded edition. Wissenschaftliche Buchgesellschaft , Darmstadt 1989, ISBN 3-534-10140-5 ( MR1068314 ).
• Frank Harary : Graph Theory . R. Oldenbourg Verlag , Munich, Vienna 1974, ISBN 3-486-34191-X .
• M. Meyniel: Une condition suffisante d'existence d'un circuit Hamiltonien dans un graphe oriente . In: Journal of Combinatorial Theory. Series B . tape 14 , 1973, p. 137-147 ( MR0317997 ).
• Robin J. Wilson : Introduction to Graph Theory . Translated from English by Gerd Wegner (=  modern mathematics in elementary representation . Volume 15 ). Vandenhoeck & Ruprecht , Göttingen 1976 ( MR0434854 - English template: Introduction to Graph Theory , Longman, London 1975).

Individual evidence

1. ^ Rudolf Halin: Graph theory. 1989, p. 110
2. ↑ Robin J. Wilson: Introduction to Graph Theory. 1976, pp. 111-112
3. ^ Frank Harary: Grape theory. 1974, p. 220
4. ↑ Halin, op.cit., Pp. 110, 304