Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 122.24903
Autor: Dirac, G.; Erdös, Pál
Title: On the maximal number of independent circuits in a graph (In English)
Source: Acta Math. Acad. Sci. Hung. 14, 79-94 (1963).
Review: Es handelt sich um endliche Graphen G folgender Typen: A. Graphen ohne Schlingen und mehrfache Kanten (speziell auch planare, in welchem Fall die in [ ] gesetzten Zahlen bzw. Ausdrücke zu nehmen sind); B. mit Schlingen aber ohne mehrfache Kanten; C. planare Graphen.
k Kreise von G heißen "unabhängig", wenn keine zwei derselben einen Punkt von G gemein haben. Es bedeute: n die Ordnung von G und pi bzw. qi die Anzahl derjenigen Punkte von G, deren Grad \geq i bzw. \leq i ist. Die Hauptergebnisse sind dann:
(A1) Hinreichend dafür, daß G unabhängige Kreise enthält, ist jedes der folgenden drei Systeme von Bedingungen:
I. n \geq 6, q2 = 0, p4 \geq 4 [2];
II. n \geq 9[8], p4 \geq 1/2 (n+4) [ 1/2 (n+3)];
III. n \geq 9 [8], p4-q2 \geq 4[3].
(A2) Ist k \geq 3 und p2k-q2k-2 \geq k2+2k-4[5k-7], so gibt es k unabhängige Kreise in G.
(B) Es sei k \geq 2; hinreichend dafür, daß es k unabhängige Kreise in G gibt, sind, je nachdem k-1 oder l (\leq k-2) Punkte von G mit Schlingen behaftet sind, die Bedingungen n \geq k+1 und pk+2-qk \geq k-2 bzw. n \geq l+9 und p2k-l-q2k-l-2 \geq (k-l)2+2k-l-4. (Der Fall l = 0 liefert A2.) Nach K. Corradi und A. Hajnal (Zbl 118.19001) ist für beliebiges l hinreichend: n \geq 3k, q2k-1 = 0.
(C) Hat G mindestens drei Kanten mehr als Punkte, so gibt es in G zwei Kreise ohne gemeinsame Kante. Dies ist, für planare Graphen, das Analogon eines Satzes von P. Erdös und L. Pósa [Publ. Math., Debrecen 9, 3-12 (1962; Zbl 133.16701)] in welchem "vier" anstelle von "drei" steht.
Reviewer: E.Schönhardt
Classif.: * 05C35 Extremal problems (graph theory)
Index Words: combinatorics
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag