zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Congruent graphs and the connectivity of graphs. (English) JFM 58.0609.01

Verf. betrachtet zunächst Graphen, in denen keine Schlingen auftreten und keine zwei Knotenpunkte durch mehr als eine Kante verbunden sind. Wenn zwischen den Kannten zweier solcher Graphen eine eineindeutige Zuordnung besteht, bei der zwei Kanten des einen Graphen dann und nur dann einen Knotenpunkt gemeinsam haben, wenn dasselbe für die entsprechenden Kanten des anderen gilt, so zeigt ein triviales Beispiel, daß zwei solche Graphen nicht notwendig kongruent, d. h. ihre Ecken und Kanten eineindeutig unter Erhaltung der Inzidenzbeziehnung aufeinander bezogen sind: Der aus drei Kanten mit genau einem gemeinsamen Knotenpunkt bestehende Graph ist dem aus den Ecken und Seiten eines Dreiecks bestehenden Graphen nicht kongruent. Das ist aber - so zeigt Verf. - der einzige Ausnahmefall: Wenn keiner der beiden Graphen der aus drei Kanten mit einer gemeinsamen Ecke bestehende Graph ist, so folgt aus dem Bestehen einer Kantenzuordung von der oben erwähnten Art die Kongruenz der beiden Graphen.

Weitere Aussagen ähnlicher Art kann man für dreifach zusammenhängende Graphen machen. Ein zusammenhängender Graph mit wenigstens n+1 Knotenpunkten heißt n-fach zusammenhängend, wenn es nicht möglich ist, aus ihm n-1 oder weniger Knotenpunkte samt den in ihnen endenden Kanten wegzulassen, derart daß der entstehende Graph nicht mehr zusammenhängend ist, ein Graph, der n-fach, aber nicht (n+1)-fach zusammenhängend ist, hat die Zusammenhangszahl (“connectivity”) n. Es wird bewiesen: Wenn zwischen den Kanten zweier dreifach zusammenhängender Graphen eine eineindeutige Zuordnung besteht, bei der Kreise oder auch Teilgraphen der Nullität 1 einander entsprechen, so sind die beiden Graphen einander kongruent.

Über die Struktur der n-fach zusammenhängenden Graphen (in denen jetzt zwei Ecken auch durch mehrere Kanten verbunden sein dürfen) werden folgende Aussagen gemacht: Dann und nur dann ist ein Graph n-fach zusammenhängend, wenn mann ihn für kein k<n aus zwei mehr als k Knotenpunkte enthaltenden Graphen durch Identifikation von k Knotenpunkten aufbauen kann. Ein Graph mit mindestens zwei Knotenpunkten, der durch Tilgen von weniger als n Kanten zerlegt werden kann, ist nicht n-fach zusammenhängend. Läßt man aus einem n-fach zusammenhängenden Graphen einen Knotenpunkt und die in ihm endenden Kanten weg, so entsteht ein (n-1)-fach zusammenhängender Graph. Dann und nur dann ist ein Graph, in dem zwei Knotenpunkte durch höchstens eine Kante verbunden sind, n-fach zusammenhängend, wenn je zwei Knotenpunkte durch n bis auf die gemeinsamen Endpunkte paarweise (kanten- und knotenpunkt- )fremde Kantenzüge verbunden werden können (vgl. hierzu Menger, Fundamenta 10 (1926), 96-115; F. d. M. 53, 561 (JFM 53.0561.*); N. Rutt, 1929; F. d. M. 55 I , 330; ferner D. König, 1933; F. d. M. 59 II , 1232).

Bei der Untersuchung dualer Graphen (siehe vorstehendes Referat) läßt man zweckmäßigerweise auch Graphen mit Schlingen und mehreren Verbindungen desselben Knotenpunktpaares zu. Zwischen den Zusammenhangseigenschaften zweier zusammenhängender zueinander dualer Graphen besteht folgende Beziehung: G sei nicht-separabel und zerfalle, wenn man die Ecken a 1 ,a 2 ,,a n mit den in ihnen endenden Kanten tilgt, in zwei Bestandteile H 1 und H 2 , während keine echte Teilmenge der a i mit den zugehörigen Kanten G zerlegt. Die Nullität von H 1 sei positiv, oder wenigstens ein a i sei mit H 1 durch wenigstens zwei Kanten verbunden; entsprechend für H 2 . Wenn dann G ' zu G dual ist, so kann G ' durch Tilgen einer den a i in bestimmter Weise zugeordneten Menge von n Kanten zerlegt werden. Für dreifach zusammenhängende Graphen ohne Schlingen und ohne mehrfache Verbindungen von Knotenpunktpaaren liefert dieser Satz: Jeder dazu duale Graph ist ebenfalls dreifach zusammenhängend, und - in Verbindung mit einem der obigen Kongruenzsätze -: Der duale Graph ist in diesem Fall eindeutig bestimmt.