Bemerkungen zu einem Isomorphie-Problem für Graphen, die speziellen Matrizen zugeordnet sind

✍ Scribed by R. Schmieder

• Publisher: John Wiley and Sons
• Year: 1979
• Tongue: English
• Weight: 619 KB
• Volume: 90
• Category: Article
• ISSN: 0025-584X
• DOI: 10.1002/mana.19790900117

✦ Synopsis

KALOUJNINE hat in [2] dargelegt, da13 es fur die Klassifikation endlicher metabelscher p-Gruppen vorteilhaft ist, die Struktur gewisser eineindeutig zugeordneter nilpotenter hEscher Ringe der Stufe 3 zu studieren. Fur eine spezielle Klasse der betrachteten hEschen Ringe gab KALOUJNINE eine Zuordnung zu endlichen, schlichten Graphen an, und er formulierte das Problem, ob die zugeordneten Graphen bis auf Isomorphie eindeutig bestimmt sind. Es ist ohne Schwierigkeiten nachweisbar, da13 dieses KmoUJNINEsche Problem einem Problem fur bestimmte Matrizen mit zugeordneten Graphenpaaren iiquivalent ist. Dieses Matrizenproblem sol1 in diesem Beitrag vorgestellt, behandelt und teilweise gelost werden. Ein Zusammenhang zum RC (Rekonstruktionsproblem) fur Graphen wird dabei aufgezeigt und auch ausgenutzt.

2. Zwei Relationen zwischen Graphenpaaren und Matrizen

Im folgenden sollen A = (aii) eine n-reihige, quadratische Matrix mit n 2 2 und G1, G2

zwei ungerichtete, endliche, schlichte Graphen mit den Knotenmengen V(Gi)

Definition 1. G, steht mit G, in der Relation K ( A ) , bezeichnet durch (GI, G,) K ( A ) ,

genau dann, wenn gilt:

r, p ) E E(Gz): dl: = Defairajpaipajr = 0.2) Definition 2. G1 steht nrit G, i n der Relation L ( A ) , bexeichnet durch (G,, Q,) L(A), genau dann, wenn unter der Vwaussetzung Vl = V , = (1, ...) n) gilt: 0) (81, G) K ( A ) , l) (n) bezeichnet den vollstindigen Graphen mit der Knotenmenge 11, . . ., n}. ") Vereinbarung: Eine Kante (2, y} wird kiinftig mit (5, y) bezeichnet; ob ein Term (2, y) eine Kante oder ein geordnetes Paar bedeutet, geht &us dem Zusammenhang hervor.