Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 133.16701
Autor: Erdös, Pál; Pósa, L.
Title: On the maximal number of disjoint circuits of a graph (In English)
Source: Publ. Math. 9, 3-12 (1962).
Review: Les AA. notent par Gk(n) le graph avec n sommets et k arêtes dans lequel le circuit d'une seule arête n'est pas admis, et par \bar Gk(n) le graph qui l'admet. Un ensemble d'arêtes (resp. de circuits) est dit indépendant, s'il n'y en a pas deux d'entre elles (esp. deux d'entre eux) avec un sommet commun. Ces ensembles sont dits faiblement indépendants, s'ils n'ont pas deux de leurs éléments avec une arête commune. P.Erdös et T.Gallai (Zbl 090.39401) ont prouvé que le graph Gl+1(n) où l est le plus grand des entiers {2k-1 \choose 2} et (k-1)n-(k-1)2+{k-1 \choose 2}, contient k arêtes indépendantes. Dans le présent mémoire les AA. étudient la question: Combien d'arêtes sont nécessaires à un graph pour contenir k circuits indépendants ou faiblement indépendants? En posant f(n,k) = (2k-1)n-2k2+k leur principal résultat est: pour n \geq n0(k), k > 1, le graph Gf(n,k)(n) contient k circuits indépendants, excepté s'il contient 2k-1 sommets de valence n-1 (dans ce cas sa structure est univoquement déterminée). Si trivialement k = 1, chaque Gn(n) contient un circuit, mais il y a naturellement des graphs Gn-1(n), dont aucun sommet n'a la valence n-1 et néanmoins le graph ne contenant aucun circuit. Ainsi la restriction k > 1 est nécessaire. Evidemment n0(k) \geq 3k, puisque un circuit normal contient au moins trois arêtes. Pour k = 2 et k = 3, n0(k) = 3k, mains en général n0(k) > 3k. Ils prouvent n0(k) \leq 24k. Ils pensent valable le fait suivant, analogue à celui ci-dessus: le graph G(n)l+1, où l est le plus grand des entiers {3k-1 \choose 2}+n-3k+2 et (2k-1)n-2k2+k, contient k circuits indépendants. Ils notent g(k) le plus petit entier tel que chaque \bar Gn+g(k)(n) contienne k circuits faiblement indépendants et prouvent g(2) = 4 et pour chaque k: c1k log k < g(k) < c2k log k, où c1 et c2 sont deux constantes absolues appropriées. Ils donnent la valeur de g(3); par contre l'exacte détermination de g(k) leur parait un problème difficile. Ils terminent par la constatation que certains de leurs résultats étaient connus de G. Dirac, mais qui n'a rien publié à leur sujet.
Reviewer: S.Bays
Classif.: * 05C35 Extremal problems (graph theory)
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag