Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 116.15002
Autor: Erdös, Pál; Sachs, Horst
Title: Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl. (Regular graphs with given girth and minimal number of knots.) (In German)
Source: Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe 12, 251-258 (1963).
Review: Teil I dieser Arbeit geht wesentlich auf Erdös, Teil II auf Sachs zurück. Es handelt sich um reguläre Graphen G ohne Schlingen und mehrfache Kanten (Ordnung n, Grad k). Unter der "Taillenweite" von G verstehen die Verff. die Länge eines kürzesten Kreises in G, unter f(k,l) die kleinste Ordnung n, für welche es einen solchen Graph der Taillenweite \geq l gibt. Es ist f(2,l) = l und f(k,3) = k+1. Die Bestimmung von f(k,l) für k > 2, l > 3 wird als schwieriges Problem bezeichnet, das bisher nur für spezielle Werte von k,l gelöst ist. H. Sachs [J. London Math. Soc. 38, 423-429 (1963; Zbl 117.17302)] hat eine obere Abschätzung für f(k,l) gegeben. Erdös beweist in I für k \geq 2, l \geq 3, m = [ 1/2 (l-3)] 1+k sumt = 0m (k-1)t \leq f(k,l) \leq 4 sumt = 1l-2 (k-1)t (1) und verbessert damit die obere Schranke. Er zeigt ferner, daß die untere Schranke für gerades l = 2q durch den größeren Wert
2[(k-1)q-1]/(k-2) (2) ersetzt werden kann, und gibt unter Heranziehung der Ergebnisse von A.J.Hoffman und R.R.Singleton (Zbl 096.38102), F.Karteszi (Zbl 099.15301; Zbl 104.39906), W.F.McGee (Zbl 091.37504), W.T.Tutte (Zbl 029.42401) einen Überblick über bereits bekannte Teilergebnisse. Dabei zeigt sich, daß überall (ausgenommen k = 3, l = 7) f(k,l) gleich der unteren Schranke (1) bzw. (2) ist, und daß dann die Graphen mit n = f(k,l) bei geradem l paare Graphen sind.
In II werden zunächst folgende Eigenschaften der "Minimalgraphen" G(n) (k,l) mit n = f(k,l) hergeleitet: Der Abstand zweier beliebiger Punkte ist \leq l; für gerades k = 2h ist die Anzahl derjenigen Kanten, deren Endpunkte von einem beliebigen Punkt den Abstand l haben, < h, und die Anzahl derjenigen Punkte, die von einem beliebigen Punkt den Abstand l haben, \leq (k-1)l-1; durch jede Kante gehen mindestens [ 1/2 (k+1)] Kreise mit Länge \leq l+1; es gibt keine Brücke und keine Artikulation; durch einen Punkt gehen mindestens [ 1/2 (k [{k+1 \over 2} ]+1 )] Kreise mit Länge \leq l+1 (eine Aussage, die für gerades und für ungerades k noch präzisiert wird); jeder G(n)(k,l) hat die Taillenweite l. Es folgt: Zu zwei beliebigen natürlichen Zahlen k \geq 2 und l \geq 3 gibt es stets reguläre Graphen k-ten Grades mit Taillenweite l.
Zum Schluß stellt Sachs noch die Ungleichung f(k,2q+2) \leq 2f(k,2q+1) auf, gelangt damit bei geradem l zu einer besseren oberen Schranke und verwendet dieselbe mit (1) und (2) zu folgender Zusammenstellung, in der g(k,e) = [(k-1)e-1)/(k-2)] ist: 1+k g(k,q) \leq f(k,2q+1) \leq 4 [g(k,2q)-1], 2g(k,q+1) \leq f(k,2q+2) \leq 8[g(k,2q)-1].
Reviewer: E.Schönhardt
Classif.: * 05C35 Extremal problems (graph theory)
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag