## 1. Einfiihrung Eine G-Struktur ist ein Paar (M, Fk), in dem M eine endliche, nichtleere Menge und Fk eine endliche Familie von Elementen ~U E N' ist. Die Isostrophie von G-Strukturen ist eine Aquivalenzrelation. Jeder G-Struktur liiljt siph ein schlichter Graph 60 zuordnen, dalj zu isostrophen G
Eine Beschreibung ven Graphen durch Isostrophieklassen spezieller algebraischer Strukturen, II
โ Scribed by Manfred Lesch; Lothar Stenzel
- Book ID
- 102489776
- Publisher
- John Wiley and Sons
- Year
- 1980
- Tongue
- English
- Weight
- 473 KB
- Volume
- 97
- Category
- Article
- ISSN
- 0025-584X
No coin nor oath required. For personal study only.
โฆ Synopsis
Wir betrachten G-Strukturen ( M , R:!) mit [MI =m> I , in denen R3 eine umkehrbare binare Operation auf M ist. ( M , R,) ist dann Quasigruppe, der zugehiirige Graph ist G=(R3, U ) . Diese Graphen haben fur m=-2 die Dimension 3 und fur m = 2 die Dimension 1 (vgl. [3]). Zwei verschiedene Tripel von R3 stimmen in hiichstens einer Koordinate uberein, und jedes Element von ill ist in genau m Tripeln als i-te Koordinate enthalten (,i= 1, 2 , 3). Satz 1. Fur jeden Graphen G = (R3, U ) gilt: a) C hat m 2 Knoten und ist regular ztom Grade 3 (m -1). b) J e zwei adjazente Knoten haben genau m gemeinsame Nachbarknoten. c ) Je zwei nicht adjazente Knoten haben genau 6 gemeinsame Nachbarknoten. Der von diesen ti Knoten aufgespannte Untergraph ist hamiltonsch und dreikreisfrei. d) Fur die Stabilitatszahl a(G) gilt a(G) srn. e) Jede maximale Clique von G wird von 3, 4 oder m Knoten aufgespannt. E8 gibt 3m pacwweise kantendisjunkte rn-Cliquen so, dap jede Kante in genau einer dieser Cliquen enthalten ist. Par die Dichte d(G) von G gilt d(G)=m fur m -2 und d ( G ) = 4 far m=2. f) Fur m * 3 , 4 enthalt G nur 3m m-Cliquen, und zwei verschiedene m-CEiquen hahen hochstens einen gemeinsamen Knoten. g) Jeder nicht in einer m-Clique C enthaltene Knoten ist z u genau 2 Knoten dieser Clique benachbart. Damit sind j e zwei knotendisjunkte m-Cliquen durch genau 2rn Kanten verbunden. Beweis. Zu a): Weil R:) umkehrbare Operation auf &I ist, gilt a). Zu L): (xi, xi, xi) und (xy, xy, x5') seien zwei adjazente Knoten, fur die ohne Beschrankung der Allgemeinheit x; = x;' gilt. Dann ist xi =+ xy und xi +z','. Alle weiteren m -2 Knoten ( x ~, x.,, x:&, fur die x1 =xi gilt, sindzu diesen beidenKnoten adja'zent. Die Knoten (iti, xi, xy) und (El, xy, xi) sind ebenfalls zu diesen beiden Knot'en adjazent. Weil R:) umkehrbare Operation ist, sind dies alle gemeinsamen Nachbarn. Zu c): (xi, xi, xi) und (xy, xi', xy) seien zwei nicht adjazenteKnoten. Dann ist m>2. Weil R3 umkehrbare Operation ist, sind (xi, xy, a ) , (xi, b,xy), ( G , x ~, x;),
๐ SIMILAR VOLUMES