On the construction of certain graphs

From MaRDI portal





Es bezeichne \(G = G(n)\) einen Graphen mit \(n\) Punkten. \textit{Turán} (Zbl 0055.17004) bestimmte die Maximalzahl \(f(n)\) der Kanten eines Graphen \(G(n)\), der kein Dreieck (als Teilgraphen) enthält, als \(f(n) = [{1 \over 4}n^2]\). Ist \(I(G)\) die Kardinalzahl der größten unabhängigen Punktmenge des Graphen \(G\) (unabhängig heißt, daß keine zwei Punkte durch eine Kante verbunden sind), so gilt für den (eindeutig bestimmten) Turánschen Extremalgraphen \(G_{ex}: I(G_{ex} = [{1 \over 2}(n+1)]\). \textit{B.Andrásfai} (Zbl 0125.11802) verschärfte das Turánsche Problem durch die zweite Bedingung: \(I(G) \leq u\) mit \(u \leq I(G_{ex})\) und löste es für \(u \geq [2n/5]\). Für die Andrásfaische Maximalzahl \(f(n,u)\) gilt generell \((^*) f(n,u) \leq {1 \over 2}un\). Der erste Teil der vorliegenen Arbeit ist der Konstruktion von Graphen gewidmet, welche die Andrásfaischen Bedingungen erfüllen und für die in \((^*)\) das Gleichheitszeichen gilt. (Das sind genau die Graphen, bei denen die Menge der Nachbarpunkte jedes beliebigen Punktes eine größte unabhängige Punktmenge mit \(u\) Punkten ist.) Für \(u\geq [2n/5]\) wurden diese Graphen vollständig von \textit{Andrásfai} (loc. cit.) angegeben. Mit Hilfe eines Satzes von \textit{D.J.Kleitman} (Zbl 0141.00801) konstruiert der Verf. in vorliegender Arbeit derartige Graphen für \[ u = I(G) = n^{1-c+c(1)}, \text{ wo } n\equiv 1(\mod 3), \quad 4^c = 32/27. \] Unter der Voraussetzung, daß eine Vermutung von \textit{Czipszer} und dem Verf. richtig ist, konstruiert der Verf. im zweiten Teil der Arbeit für jede unendliche Kardinalzahl \(m\) Beispiele von \(m\)-chromatischen dreiecksfreien Graphen mit \(m\) Punkten. Die Existenz solcher Graphen wurde vom Verf. und \textit{R.Rado} (Zbl 0097.16402) bewiesen. Vermutungen, Problemstellungen (und Druckfehler) würzen die Arbeit.











This page was built for publication: On the construction of certain graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5521322)