On the construction of certain graphs
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.
- The Construction of Certain Graphs
- On construction of bound graphs
- Construction of graphs with special properties
- Some constructions of integral graphs
- scientific article; zbMATH DE number 5989950
- Construction of dominating sets of certain graphs
- scientific article; zbMATH DE number 4210187
- scientific article; zbMATH DE number 731845
- On constructions of hypotraceable graphs
- On Construction of Almost-Ramanujan Graphs
- Graphs whose every independent set has a common neighbour
- On small graphs with highly imperfect powers
- Greedy construction of nearly regular graphs
- Constructive bounds for a Ramsey-type problem
- Construction of r-regular singular graphs
- Tough Ramsey graphs without short cycles
- Cameron's construction of two-graphs
- scientific article; zbMATH DE number 5989950 (Why is no real title available?)
- A Construction of Graphs without Triangles having Pre-Assigned Order and Chromatic Number
- Lovász, vectors, graphs and codes
- scientific article; zbMATH DE number 4210187 (Why is no real title available?)
- scientific article; zbMATH DE number 54791 (Why is no real title available?)
- scientific article; zbMATH DE number 1205986 (Why is no real title available?)
- The graph constructions ofHaj�s and Ore
- On constructible graphs, locally Helly graphs, and convexity
- Construction of graphs with given circular flow numbers
- scientific article; zbMATH DE number 2165838 (Why is no real title available?)
- Constructions of bipartite graphs from finite geometries
- scientific article; zbMATH DE number 846100 (Why is no real title available?)
- Triply existentially complete triangle-free graphs
- Maximum number of colorings of (2k, k2)‐graphs
- The Construction of Certain Graphs
- scientific article; zbMATH DE number 2226732 (Why is no real title available?)
- An exponential improvement for Ramsey lower bounds
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)