×

zbMATH — the first resource for mathematics

On a problem of graph theory. (English) Zbl 0144.23302
Die in vorliegender Arbeit behandelten Graphen sind ungerichtet und enthalten keine Schlingen. Betrachten wir jene \(n\) Punkte enthaltenden Graphen, in welchen die maximale Gradzahl \(k\) ist, und deren Durchmesser nicht größer als \(d\) ist. Die Kantenanzahl der Graphen minimaler Kantenanzahl unter diesen (der ”extremen Graphen”) soll mit \(F_d(n,k)\) bezeichnet werden. Die Verff. bestimmen im Fall \({1 \over 2} n \leq k \leq n-1\) den Wert der Funktion \(F_2(n,k)\); in sehr vielen Fällen bestimmen sie auch den Wert von \(F_3(n,k)\); ferner geben sie auch extreme Graphen an. Für den Fall \(d\geq 3\) erhalten sie gute Abschätzungen bezüglich \(F_d (n,k)\). Folgender Satz beantwortet ein seit langem bestehendes Problem: Falls ein \(n\) Punkte enthaltender Graph \(G_n\) keinen Kreis der Länge 4 enthält und je zwei seiner Punkte durch einen Weg der Länge 2 verbunden sind, dann ist \(n = 2m+1\) und \(G_n\) besteht aus \(m\) Dreiecken, die einen einzigen gemeinsamen Punkt enthalten. Es werden auch mehrere interessante ungelöste Probleme aufgeworfen.
Reviewer: B.Andrásfai

MSC:
05C35 Extremal problems in graph theory
05C38 Paths and cycles
Keywords:
topology
PDF BibTeX Cite