×

A problem in graph theory. (English) Zbl 0126.39401

Ein endlicher ungerichteter schlingenloser Graph ohne mehrfache Kanten wird \((n,k)\)-Graph genannt, wenn er \(n\) Knotenpunkte besitzt und die Zahl seiner vollständigen Teilgraphen mit \(k\) Knotenpunkten \((2\leq k\leq n)\) bei Hinzufügen einer beliebigen weiteren Kante wächst. Die Verff. erkennen den Graphen, der genau alle die Kanten enthält, die mit einem oder zwei von \(k-2\) festen Knotenpunkten inzidieren, als den einzigen minimalen, d. h. die Minimalzahl an Kanten besitzenden \((n,k)\)-Graphen.
Sie benutzen dieses schöne Ergebnis zum Beweis einer Vermutung von P. Erdős und T. Gallai (Zbl 0101.41001) bezüglich der Maximalzahl der Kanten eines kanten-\(p\)-kritischen (edge \(p\)-critical) Graphen (zur Definition vgl. die Arbeit) und weisen darauf hin, daß es — nur für \((n,k)\)-Graphen formuliert, die ursprünglich keinen vollständigen Teilgraphen mit \(k\) Knotenpunkten besitzen — das duale Problem zu dem von P. Turán (Zbl 0055.17004); vgl. auch B. Andrásfai, Zbl 0114.40001) behandelten beantwortet.
Schließlich formulieren sie als Vermutung einen entsprechenden Satz für paare (bipartite) Graphen, den der Ref. bewiesen hat [Wiss. Z. Tech. Hochsch. Ilmenau 12, 253-256 (1966; Zbl 0148.18004)].
Reviewer: W.H.L.Wessel

MSC:

05C35 Extremal problems in graph theory

Keywords:

topology
PDFBibTeX XMLCite
Full Text: DOI Link