On the structure of linear graphs (Q2627011)

Es sei \(G(n;m)\) ein (nichtgerichteter) Graph mit \(n\) Knotenpunkten und \(m\) Kanten. Aus dem bekannten Satz von \textit{P.Turán} folgt die spezielle Behauptung, daß jeder Graph \(G(n;[n^2/4]+1)\) mindestens ein Dreieck enthält (\(n \geq 3)\). Der Verf. und \textit{G.A.Dirac} haben unabhängig einen Satz gefunden, daß jeder Graph \(G(n;[n^2/4]+1)\) für jede ganze Zahl \(k \in \langle 4;n\rangle\) einen Teilgraphen \(G(k;[k^2/4]+1)\) enthält. In der vorliegenden Arbeit wird die Struktur der Graphen \(G(n;[n^2/4]+1)\) und \(G(n;[tn^{3/2}])\) (für genügend großes \(t\)) ausführlich untersucht. Es werden z.B. die sogenannten vollständigen paaren Teilgraphen \(K_e (u_n, u_n)\) (mit einer weiteren Kante) und die im \(G(n;[n^2/4]+1)\) bzw. \(G(n;[tn^{3/2}])\) liegenden Kreise betrachtet. Einige Vermutungen, die in dieser Arbeit offen geblieben sind, bezeichnet der Verf. als schwierig.