Lexikon der Mathematik: dreiecksfreier Graph
ein Graph, der keinen vollständigen Graphen K3 der Ordnung 3 – also ein „Dreieck“ – als Teilgraphen enthält.
Als Spezialfall des Satzes von Turán ergibt sich, daß ein dreiecksfreier Graph G der Ordnung n höchstens \(\lfloor \frac{{n}^{2}}{4}\rfloor \) Kanten besitzt.
Hat G tatsächlich die maximale Anzhal von \(\lfloor \frac{{n}^{2}}{4}\rfloor \) Kanten, dann ist G der vollständige bipartite Graph Kr,s mit \(r\,=\,\lfloor \frac{n}{2}\rfloor \) und \(s\,=\,\lfloor \frac{n}{2}\rfloor \).
Copyright Springer Verlag GmbH Deutschland 2017
Schreiben Sie uns!