๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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


Eine Beschreibung von Graphen durch Isos
โœ Manfred Lesch; Lothar Stenzel ๐Ÿ“‚ Article ๐Ÿ“… 1980 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 345 KB

## 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