Die Maximalzahl von kreuzungsfreien Kanten in Darstellungen von vollständigen n-geteilten Graphen
✍ Scribed by Ingrid Mengersen
- Publisher
- John Wiley and Sons
- Year
- 1978
- Tongue
- English
- Weight
- 420 KB
- Volume
- 85
- Category
- Article
- ISSN
- 0025-584X
No coin nor oath required. For personal study only.
✦ Synopsis
Farirht man xi von x, -+ . . . +x, paarweise versehiedenen Punkten (Knoten) der Eummischen Ebene mit einer Farbe i (i= 1, . . . , n ) und verbindet je zwei verschiedenfarbige Knoten durch einen JORDANSChen Kurvenhogen (Kante), so erhalt man eine Zeichnung des vollstandigen n-geteilten oder auch n-flrbbaren Graphen K(x,, . . . , x,). Eine solche Zeichnung nennen wir Darstellung und bezeichnen sie init D(x,, . . . , xn), wenn je zwei Kanten hochstens einen gemeinsamen Punkt besitzen , der entweder gemeineamer Endknoten oder Kreuzungspunkt ist.
G. RINGEL bewies in
[5], daB eine Darstellung des K ( z i , . . . , x,) mit xL= = . . . =ql = 1, d. h. eine Darstellung des vollstandigen Graphen K,, fur n z 4 maximal 2n -2 kreuzungsfreie Kanten enthalt, in [3] wurden alle Ubrigen Anzahlen von kreuzungsfreien Kanten mgegeben, die in Darstellungen des K,, auftreten. Hier wird nun die maximale Anzahl von kreuzungsfreien Kanten, H ( x i , . . . ,z,), in einer Darstellung eines beliebigen Graphen K(xl, . . . , 5 , ) bestimmt. Die hierbei verwendeten Regriffe findet man etwa in [2].
&(xi, , . . , x,) wurde hereits in [4] auf andere Weise ermittelt, dort ist auch die minimale Anzahl von kreuzungsfreien Kanten in einer Darstellung des K(x,, . . . , xn) bis auf drei Busnahmefiille ttngegeben.
📜 SIMILAR VOLUMES