Abzählbar-unendliche Graphen mit HAMILTONscher dritter Potenz

Math. Nachr. 82, 231-239 (1978)

Abzahlbar-unendliche Graphen rnit HARmTONsCher dritter Potenz

Von PETER HEINRICH in Freiberg

(Eingzgsngen am 8.1.1976)

Wir betrachten im folgenden nur schlichte und ungeriohtete Graphen. SEKA- NINA bewies in [3], d& Graphen rnit ausreichender Bindung eine HAMILToNsChe dritte Potenz besitzen. In dieser Arbeit kann, nachdem eine neue Charakteri- sierung der Graphen mit ausreichender Bindung vorgenommen wird, eine weitere Klasse abziihlbar-unendlicher Graphen mit HAMILTONsCher dritter Potenz angegeben werden. AuBerdem werden diejenigen abzahlbar-unendlichen Graphen mit nur Knoten endlichen Grades charakterisiert, deren dritte Potenz HAMIL-

ToNscli ist, Hinsichtljch der Terminologie halten wir uns an das Buch von SACHS [2] ; anstelle , ,abziihlbar-unendlich" sagen wir im weiteren stets nur ,,unendlich".

Zusiitzlich sei noch folgendes vereinbert : 1st G ein Graph, so sol1 die Knoten- menge von G auch mit G bezeichnet werden. 1st umgekehrt P eine Knotenmenge eines Graphen G, so bezeichnen wir den von P erzeugten Teilgraphen von G' ebenfalls mjt P . Wir sprechen dann auch beispielsweixe von einer ,,zusammen- hBngenden", Knotenmenge P ; gemeint ist damit naturlich, daB der von P er- zeugte Teilgraph zusammenhangend ist, usf.

I Sei G ein unendlicher zusammenhiingender Graph.

Definition 1. G heiBt HAMILToNsch genau dann, wenn gilt : Es gibt eine Knoten- folge f = (ai, a2, . . . , a,, . . .), die jeden Knoten von G genau einmal enthalt, wobei Nachbarknoten dieser Folge in G durch eine Kante mjteinander verbunden sind.

Definition 2. G3 heil3t die dritte Potenz von G genau dann, wenn gilt: 1. G3 ist ein Graph, dessen Knotenmenge mit der von G ubereinstimmt.

2. Zwei Knoten a, b von G3 sind genau dann durch eine Kante verbunden, wenn 1 s g ( a , b ) s 3 gilt; dabei ist g die Abstandsfunktion von G. (G3 ist offenbar ein unendlicher, zusammenhiingender, schlichter und ungerichteter Graph. )

Definition 3. (vgl. SEKANINA [3]) : G besitzt ausreichende Bindung genau h,

232 HEINRICH, Abzahlbar-unendliche Graphen

wenn zu jeder endlichen und nichtleeren Knotenmenge P von G ein Teilgraph von G mit folgenden Eigenschaften existiert : 1. G' ist zusammenhkngend

3. G-G' ist endlich. Nun gilt

Satz 1. (vgl. SEKANINA [3J) : Hat G ausreichende Bindung, so ist G3 HAMILTONsCh. Wir fuhren nun die Begriffe Typ, Zentralmenge und minimale Zentralmenge eines Graphen ein. Diese sowie die Folgerungen 1, 2 und Satz 2 stammen im wesentlichen aus [ 11. Sei P eine beliebige endliche, aber niohtleere Knotenmenge von G und I? = G - P. Offenbar kann fur I? nur genau einer der nachfolgenden vier Fklle eintreten: a) B besteht aus genau einer unendlichen und endlich vielen endlichen Kompo-

nenten. b) B besitzt keine unendlichen (und damit unendlich viele endliche) Kompo-

nenten . c) G besteht aus genau ejner unendlichen und unendlich vielen endlichen Kompo-

nenten. d)

Definition 4. Je nachdem, ob fur I? Fall a, b, c oder d eintritt, heiBt G beztiglich P vom T y p - 1 , 0, 1 , 2 . Hat G bezuglich P den Typ j , so schreiben wir T(G, P)=j , oftmals auch nur T ( P ) = j.

Definition 5. Eine nichtleere endliche Knotenmenge P von G he& eine Zentral- menge von G genau dann, wenn T ( G , P ) + - 1 ist. 1st P eine Zentralmenge und T(G, P ) =j (j€ (0, 1 ,2}) , so nennen wir P eine Zentralmenge des Typs j. Ejne Zentralmenge P heifit eine minimale Zentralmenge von G genau dann, wenn keine echte Teilmenge von P eine Zentralmenge von G ist.

Folgerung 1. Ist G ein unendlicher zusammenhangender Graph und P eine endliche nichtleere Knotenmenge von G, so ist P eine Zentralmenge von G , falls G - P aus unendlich vielen Komponenten besteht.

Da die leere Menge niemals Zentralmenge sein kann, ergibt sich sofort die

Folgerung 2. I s t P eine Zentralmenge von G und I PI = 1 , so ist P eine minimale

2. G ' S G - P

besitzt wenigstens zwei unendliche Komponenten.

Zentralmenge von G. Weiter gilt offenbar

Folgerung 3.Is t G ein Graph mit einer Zentralmenge P , so gibt es eine minimale Zentralmenge P' won G mit P'

Wie Bejspiele lehren, ist es nicht moglich, Folgerung 3 dahingehend zu ver- scharfen, da13 zu gegebener Zentralmenge P des T y p ~ j in G eine minimale Zentral- menge P'& P des gleichen Typs j in G existiert. Man betraohte beispielsweise den nachstehend abgebildeten Graphen G mit der Zentralmenge {a, b} ; dabei

P .

HEINRICH, Abziihlbar-unendliche Graphen 233

sollen die beiden mit a bzw. b in G verbundenen Komponentenscharen von G - - {a, b} jeweils aus unendlich vielen endlichen Graphen bestehen. Es ware dann T({a , b } ) = O , aber T({a})= T({b})= 1.

Der folgende Satz 2 liefert nun einen Zusammenhang zwischen den Graphen init Zentralrnenge und solchen mit ausreichender Bindung; der hier gegebene Beweis ist gegenuber dem in [I] angefuhrten leicht modifiziert.

Satz 2. Ein unendlicher zusammenhangender Graph besitzt genau dann eine Zentralmenge, wenn er keine ausreichende Bindung hat.

Beweis. A. Sei P eine Zentralmenge von G. Wir bilden G ' = G - P ; seien Ql, . . . , Q1, . . . die Komponenten von G' und G" ein beliebiger zusammenhiingender Teilgraph von G'. Dann gibt es (wegen des Zusammenhanges von G") genau eine Komponente Qi von G', die G" enthiilt. Damit folgt aber auf Grund der Struktur von G', daB G'-Qi und damit auch G-.Qi sowie G-G" unendliche Graphen sind. Wir erhalten, daB fur jeden zusarnmenhiingenden Teilgraphen G" von G' stets G -G" unendlich ist. Damit gibt es zu vorgegebener Zentralmenge P aber keinen zusammenhiingenden Teilgraphen G" von G mit G " S G - P , bei dem G-G" endlich ist. Somit ist G ohne ausreichende Bindung.

B. Sei G ein unendlicher Graph ohne ausreichende Bindung. Dann gibt es eine endliche und nichtleere Knotenqenge P von G derart, daB fur alle zusammenhangenden Teilgraphen G" von G mit G" S G - P gilt : G -G" ist nicht endlich.

Ware T ( G , P ) = - 1, so konnten wir als Q" die einzige unendliche Komponente von G - P wahlen und erhielten einen endlichen Teilgraphen G -G" im Wider- spruch zu unserer Voraussetzung. Damit muB fur unsere gewahlte Knotenmenge P stets T(G, P ) =I= - 1 gelten, also ist P eine Zentralmenge von G , q. e. d.

Folgerung 4. Ein unendlicher zusammenhlingender Graph G hat genau dann ausreichende Bindung, wenn far j ede endliche und nichtleere Knotenmenge P von G

I m Falle T ( G , P ) = - 1 fur eine Knotenteilmenge P kann im allgemeinen zunachst nicht entschieden werden, ob G ausreichende Bindung hat oder eine Zentralmenge besitzt. Falls aber die unendliche Komponente von G - P ausreichende Bindung hat, so ubertragt sich diese Eigenschaft auf G selbst, denn es gilt

Satz 3. Sei G ein unendlicher zusammenhiingender Graph, der eine endliche nichtleere Knotenmenge R mi€ T ( G , R) = - 1 besitzt. Hat dann die unendliche Komponente won G - R ausreichende Bindung, so hat auch G ausreichende Bindung.

Beweis. Die Komponenten von G - R seien &, Ql, . . . , Q,; dabei sol1 & die unendliche Komponente sein. 1st P eine beljebjge endliche nichtleere Knoten-

gilt: T(G, P ) = -1.

234 HEINRICH, Abzaldbar-unendliche Graphen

menge von G , so ist die Existenz eines Teilgraphen G' von G init den in Defi- nit,ion 3 angegebenen Eigenschaften 1. - 3. zu zeigen.

A. Sei Pn&=0. Wir wiihlen dann GI=&; offenbar sind 1-3 erfullt. B. Sei Pn&=D+0. D ist eine endliche Menge, denn P ist endlich; damit

ist D c Q . Da Q ausreichende Bindung hat, gibt es zu D in & einen zusammenhangenden Teilgraphen G' von & mit G' S Q - D und endlichem Q -GI; ferner ist G' Teilgraph von G. Dann aber gelten beziiglich G die Eigenschaften 1. - 3. Somit hat G ausreichende Bindung, q. e. d.

Man uberlegt sich leicht, daB Satz 3 in folgender Weise umkehrbar ist : Satz 4. Se i G ein unendlicher Graph m i t ausreichender Bindung und P eine

beliebige endliche nichtleere Knotenmenge won G. D a n n gilt: Die unendliche Kmh- ponente uon G - P hat ausreichende Bindung.

I1 Es liegt nun nahe zu untersuchen, wie sich eine Zentralmenge P eines Graphen

G verhalt, wenn sie um eine endliche Knotenmenge von G erweitert oder ver- mindert wird und wie sich Zentralmengen gegeniiber Durchschnitts- und Ver- einigungsbildung verhalten. Bei diesen Untersuchungen zeigte es sich, daB insbesondere die Zentralmengen des Typs 0 interessante Eigenschaften aufweisen. Es seien hier nur die beiden folgenden Slitze angegeben.

Satz 5. I s t P eine Zentralmenge won G , so ist auch PU P' eine Zentralmenge von G far jede endliche Knotenmenge P' von 0.

Beweis. Offenbar genugt es folgendes zu beweisen: 1st P eine Zentralmenge von G , dann gilt fur alle xEG : P = PU {x} ist eine Zentralmenge von G.

Man iiberlegt sich sofort, daB G - P hochstens eine Komponente weniger besitzt als G - P. Besteht nun G - P aus unendlich vielen Komponenten, so gilt dies auch fur G - P ; damit ist P eine Zentralmenge von G (Folgerung 1). Besteht G - P nur a u ~ endlich vielen Komponenten, so mu13 T ( G , P ) = 2 sein.

Wahlt man nun x als Knoten einer der endlichen Komponenten von G - P , so besitzt G - H mindestens zwei unendliche Komponenten (niimlich die von G - P ) ; also ist T ( G , P ) = 2. Wahlt man x als Knoten einer unendlichen Kompo- nente Q von G - P , so sind zwei Falle moglich: a) Q - { x } hat wenigstens eine unendliche Komponente; dann ist T(G, P ) = 2. b) Q - {x} besteht nur aus endlichen Komponenten; dies sind dann unendlich

viele. Es muB dann T ( G , P ) = 1 oder T(G, P ) = 2 gelten. In jedem Fall ergibt sich P als Zentralmenge von G , q. e. d. Sstz 6. Sei rxll die Gesamtheit aller Zentralmengen des T y p s 0 eines unendlichen

zusammenhangenden Graphen G. I s t rrn ;t; 0, so bildet 9.R einen unendlichen Mengen- uerband mit kleinstem Element.

1. 1st P eine Zentralmenge von G mit T(P)=O und P' eine endliche Knoten- Beweis. Wir fuhren den Beweis in drei Schritten:


menge von G, so ist T(G, PUP') = O . (Damit gilt dann insbesondere, daB die Vereinigung zweier Zentralmengen des Typs 0 von G wieder eine Zentral- menge des Typs 0 von G liefert.)

2 . Sind P und P' Zentralmengen von G mit T(P)=T(P')=O, so ist P n P ' e 0 . 3. Sind P und P' Zentralmengen von G mit T ( P ) = T ( P ' ) = 0, so ist T (G, P n P')

= 0. Beweis. Zu 1: Es geniigt, die Behauptung fur P'={x}'mit xEG zu zeigen.

Da x stets nur als Knoten von P oder einer endlichen Komponente von G - P gewahlt werden kann, ergibt sich die Behauptung aber unmittelbar.

Zu 2: Angenommen, es giibe Zentralmengen P , P' von G des Typs 0 rnit

Seien Qi, . . . , Q,, . . . die Komponenten von G - P. Diese sind alle endlich, ihre Anzahl daher nicht endlich. Jeder Knoten aus P' muB dann zu einer der Komponenten Qi gehoren; da P' endlich ist, durfen wir annehmen, daB P ' & Q I U . . .UQ, gilt. Es sei Pi= P'nQi, i= 1 , . . . , n. Nun gilt fur jedes Pi: Qi- Pi zerftillt in endlich viele endliche Kom- ponenten. Hochstens endlich viele dieser Komponenten sind in G nur mit Pi verbunden; die restlichen (endlich vielen) sind in G sowohl mit Pi als auch mit P verbunden. 1st dann P zusammenhangend, so besteht G - P'aus endlich vielen endlichen und genau einer unendlichen Komponente, es ware also T(G, P') = - 1 und P' damit keine Zentralmenge von G . (Wir haben bisher die Tatsache, daB T(P')=O ist, nicht benotigt. Man kann also in 2 . die Voraussetzung T(P')=O durch ,,P ist zusammenhangend" ersetzen ; dies ergibt dann die untenstehende Bernerkung 1 .)

1st P nicht zusammenhangend, so hat G-P' wenigstens eine unendliche Komponente (man beachte, daB es wenigstens einen Knoten von P geben muB, der in G mit unendlich vielen Komponenten von G- P verbunden ist); damit konnte T ( P') = 0 nicht eintreten, ini Widerspruch zur Voraussetzung.

Zu 3: Nach 3. ist D = P n P' += 0. Angenomnien, es ist T(G, D) + 0. Dann besitzt G - D wenigstens eine unendliche Komponente Q. Sei Q n P = Pi, Q n P' = Pa. Es niuB P,+0 gelten (i= 1 , 2); insbesondere mu13 Q beim Streichen von P, bzw. P2 jeweils in unendlich viele endliche Komponenten zerfallen. Damit istT(Q,P,) = = T(Q, P2) = O . Da D der Durchschnitt von P mit P' in G ist, mu13 P i n P2= 0 sein. Das widerspricht aber 2., angewendet auf Q. DaB '2Jl ein kleinstes Element besitzt, ist unmittelbar klar; q. e. d.

Bemerkungen. 1. Aus dem Beweis zu 2. von Satz 6 ergibt sich: 1st G ein unendlicher zusammenhangender Graph und P eine zusammenhangende Zentral- menge von G mit T(P)=O, so gilt fur jede beliebige Zentralmenge P' von G :

2. Es sei darauf hingewiesen, da13 das kleinste Element von '%31 nicht unbedingt eine minimale Zentralmenge von G sein muB. Es wird nur ausgesagt, daB unter allen Zentralmengen des Typs 0 von G genau eine rnit minimaler Knotenzahl

P ~ P ~ = o .

P ~ P W .

236 HEINRICH, Abziihlbar-unendliche Graphen

existiert ; aus dieser entstehen alle anderen Zentralmengen dieses Typs durch Hinzunehmen von endlich vielen Knoten.

3. Unter Verwendung von Definition 5 und Satz 5 zeigt man: Eine Zentral- menge P von G jst minimal genau dann, wenn fur jeden Knoten a € P gilt : P - {a} ist keine Zentralmenge von G.

I11 In diesem Abschnitt sollen minimale Zentralmengen eines Graphen charakteri-

siert werden. Wir zeigen zuniichst

Satz 7. Sei G ein unendlicher zusammenhangender Graph, der eine Zentralmenge P derart besitzt, da/3 G - P aus unendlich vielen Komponenten besteht. I s t d a n n P minimal , so gilt far jeden Knoten a C P 1 N u r endlich viele Komponenten von G - P sind in G nicht mit a adjazent .

Bew eis. Beim Streichen der minimalen Zentralmenge P zerfdlt G in unendlich viele Komponenten. Fur I PI = 1 ergibt sich die Behauptung unmittelbar. Sei \PI z 2 . Angenommen, es gibt einen Knoten a aus P derart, daB unendlich viele Komponenten von G - P in G nicht mit a adjazent sind. Dann sind diese Kompo- nenten aber mit gewissen Knoten von P’ = P - {a} adjazent (und nur mit diesen). Jede dieser Komponenten ist also auch eine Komponente von G’ =G - P‘. Damit besitzt G’ nicht nur endlich vide Komponenten, also ist P’ eine Zentralmenge von G, was der Minimalitiit von P widerspricht; g . e. d.

Hiermit liil3t sich nun der folgende Struktursatz beweisen.

Satz 8. Sei G ein unendlicher zusammenhangender Graph und P eine Zentral- menge von G. P ist genau dann eine minimale Zentralmenge von G , wenn bis auf endlich viele endliche Kornponenten samtliche Komponenten von G - P in G mit jedem Knoten von P adjazent sind.

Beweis. I. Zuniichst bestehe G - P aus unendlich vielen Komponenten. Fur I PI = 1 ist nichts zu beweisen. Sei I PI =n z 2.

A. Sei P eine minimale Zentralmenge von G. Angenommen, unendlich viele Komponenten von G - P sind in G nicht mit jedem Knoten von P adjazent ; es seien dies die Komponenten Q1, . . . , Qk, . . . Weiter seien Ai, . . . , A, die n aus (n - 1 ) Elementen bestehenden Teilmengen von P. Wir bilden nun Funktionen f undg:

f : & i ~ f i = { a I a ~ P u n d & i i s t i n G n i i t a a d j a z e n t } ; i = l , 2 , . . .; g : Aj-gi={Qi I f ( Q i ) = f i s A i } ; j=1,. . . , n .

Die Menge f i besteht auf Grund der Wahl der Qi aus hochstens n- 1 Knoten von P , ist also sicher Teilmenge von wenigstens einem Aj. Die Menge gi enthdt gerade diejenigen Komponenten Qi, die in G nur mit Knoten aus Ai adjazent sind. Offenbar ist {Ql, . . . , Qk, . . .} = g i U , . .Us,; ohne Beschriinkung der All- gemeinheit durfen wir damit gi als unendliche Menge voraussetzen. Damit gilt fur den Knoten a,, falls P= {al, . . . , a,} und Ai={ul, . . . , a,,-i} gesetzt wird:


a, ist in G mit unendlich vielen Komponenten von G - P - namlich gerade rnit denen aus gl - nicht adjazent. Das widerspricht Satz 7. *

Angenommen, G - P besitzt eine unendliche Komponente Q, die in G nur rnit Knoten aus einer echten Teilmenge P'c P adjazent ist. Ohne Beschrankung der Allgemeinheit durfen wir P'=A, setzen. Streichen wir jetzt Ai in G, so ist Q sicher eine Komponente von G-Ai . Wie vorher gezeigt, gibt es hochstens endlich viele Komponenten von G- P, die in G nur mit Knoten aus A , adjazent sind (eine von diesen ist gerade Q ) ; die restlicben Komponenten von G - P (und dies sind unendlich viele), sind mit dem Knoten an adjazent. Damit enthilt G - A , wenigstens zwei unendliche Komponenten, es ist also T(G, A,) =t= - 1, d. h. A, ist Zentralmengc, was der Minimalitlt von P widerspricht.

B. Von den unendlich vielen Komponenten, aus denen G - P besteht, sollen jetzt nur endlich viele endliche Komponenten in G nicht mit jedem Knoten von P adjazent sein. Wir wahlen A , , . . . , A, wie oben. Da es jetzt nur endlich viele Komponenten von G - P gibt, die in G nur init Ai adjazent sind (i = 1 , . . . , n) und diese Komponenten endlich sind, gilt fur jedes Ai: T ( G , A i ) = -1. Das bedeutet, daB P eine minimale Zentralmenge von G ist.

11. G- P sol1 jetzt aus nur endlich vielen Komponenten bestehen. Es ist damit T( P) = 2. Fur I PI = 1 ist nichts zu beweisen. Sei I PI 2 2 .

A. Sei P minimal. Angenommen, es gibt eine unendliche Komponente Q von G - P , &e in G nur mit Knoten aus einer echten Teilmenge P'c P adjazent ist. Dann enthalt G - P' sicher wenigstens zwei unendliche Komponenten - es ist also T ( G , P') = 2. Dies widerspricht der Minimalitat von P.

B. Sei P' eine beliebige (n- 1)-elementige Teilmenge von P. Dann besteht G - P' aus genau einer unendlichen und endlich vielen endlichen Komponenten; also ist P minimale Zentralmenge ; g . e. d.

Aus dem vorstehenden Struktursatz ergibt sich die

Folgerung 5. Sei G ein unendlicher zusammenhangender Graph und P eine Zentralmenge von G mit T (G, P ) = 0. Dann sind die folgenden Bedingungen aqui- valent: 1. P ist eine minimale Zentralmenge von G. 2. Faat alle Komponenten von G - P sind mit jedem Knoten von P in G adjazent.

IV Wir konnen uns nun unserer Ausgangsproblematik zuwenden und das in

Satz 1 formulierte Resultat von SEKANINA auf eine Klasse von Graphen ohne ausreichende Bindung ubertragen.

Satz 9. Sei G ein unendlicher zusamrnenhangender Graph, dcr eine minimale Zentralmenge P des Typs 0 besitzt. Dann ist G3 HAMILToNsch.

(Bemerkung. Unter der zu&itzlichen Voraussetzung IPI = 1 wurde dieser Satz bereits von HOHNE in [l] bewiesen.)

238 HEINRICH, Abzahlbar-unendliche Graphen

Beweis. Sei P = {a,, . . . , a*&} die (nach Satz 6 eindeutjg bestimmte) minimale Zentralmenge von G mit T ( P ) = 0. Nach Satz 8 sind dann nur endlich viele Kom- ponenten von G - P in G nicht mit allen Knoten von P adjazent ; wjr nennen sie Qi, . . . , Q,. Weiter sei Qo eine der Komponenten, die in G mit jedem Knoten von P verbunden ist ; die restlichen Komponenten von G - P seien Ri, . . . , R,, . . . Der Graph G’ =G - {Xi, . . . , R,, . . .} ist endlich und zusammenhangend. Dann existiert inG’3 ein a, mit a: verbindender ILAMILToNscher Weg wo (siehe [3]), wobej a: ein Nachbarknoten von a, in G’ sein soll.

Weiter seien gewiihlt :

biCRi mit g ( b , , a , ) = l , i = l , 2 , . . . , k,. . . (g (b , , bi) = 1 fur I RJ 2 2 \bi=b: fur I R i l = l ,

b’e Ri mit

und wi sei ein bi rnit bi verbindender HAMILToNsCher Weg in R:. Dann ist offenbar

w=wo(a:b,) w,(b’,b,) w,(b;b3) w3 . . . ein HAMnTONRCher Weg in G3; q. e. d.

V. In diesem Abschnitt sollen speziell unendliche Graphen betrachtet werden,

die nur Knoten endlichen Grades besitzen. Wir benotigen dazu die

Definition 6. Sei G ein unendlicher zusammenhiingender Graph und P eine beliebige endliche nichtleere Knotenmenge von G . Weiter sei Q eine beliebige Knotenmenge von G mit Pfl Q = 0. Dann verstehen wir unter der 2- Umgebung won P in Q (bzw. in einem Teilgraphen von G mit der Knotenmenge Q ) die folgende Menge U(P, Q) :

dabei ist g die Abatandsfunktion von G. Nun gilt

Satz 10. Sei G ein unendlicher zusammenhangender Graph, der eine Zentral- menge P mit T ( G , P ) = 1 oder T ( G , P ) = 2 besitzt. Ist dann G3 m m T o N s c h und Q eine unendliche Komponente won G - P , so mup die Menge U(P, Q) unendlich viele Elemente besitzen.

Beweis. Da G3 HAENLToNsch ist, existiert eine Knotenfolge

f= (ai , a,, a3, . . .) , die jeden Knoten von G genau einmal enthiilt, wobei 1 s g ( a i , ai+i) 5 3 gilt. Sei Q eine unendliche Komponente von G - P und ai der Knoten von f mit kleinstem Index, der aus Q stammt. Wir betrachten nun die mit ai beginnende Q-Folge von f (d. i. die liingste Teilfolge der Form ai, ai+i, . . . , ai+, von f , die nur Knoten BUS

Q enthalt). Diese ist sicher endlich, was sich dmaua ergibt, daB fur T ( G , 2’) = 1 der Graph G - P unendlich viele Komponenten und daB fiir T(G, P ) = 2 der Graph


G - P wenigstens zwei unendliche Komponenten besitzt. Da nun jede Q-Folge von f endlich ist, Q aber unendlich viele Knoten besitzt, muB es unendlich viele Knoten von Q geben, die von einem nicht zu Q gehorenden Knoten einen Abstand s 3 in G haben. Das zieht aber die in unserem Satz aufgestellte Behauptung nach sich, wenn man noch die Endlichkeit von P beachtet, g . e. d.

Damit sind die Voraussetzungen geschaffen, uni solche unendlichen Graphen G niit HAMILTONSCher dritter Potenz zu charakterisieren, die nur Knoten endlichen Grades besitzen.

Satz 11. Sei G ein unendlicher zusammenhangender Graph, der nur Knoten endlichen Grades besitzt. Dann gilt: G3 ist RAMILTONsch genau dann, wenn G azcs- reichende Bindung besitzt.

Beweis. A. Die Hinliinglichkeit folgt aus Satz 1 . B. Sei G3 HAMILTONsCh, aber G kein Graph mit ausreichender Bindung. Dann

besitzt G eine Zentralmenge P. Da jeder Knoten von G nur endlichen Grad hat, mu13 T(G, P ) = 2 sein, wobei G - P dann nur aus endlich vielen Komponenten besteht. Sei Q eine der unendlichen Komponenten von G - P. Da P endlich ist und jeder Knoten von G nur endlichen Grad besitzt, mu13 U ( P , Q) endlich sein, was Satz 10 und damit unserer Voraussetzung, daS G3 HAMILToNsCh ist , w iderspricht , g . e. d.

Literatur

[ 11 M. HOHNE, Verallgemeinerte Hamiltonsche Wege in p-ten Potenzen abziihlbarer zusammenhiingender Graphen ( p 53) ; Diplomarbeit, Bergakademie Freiberg, 1974.

[2] H. SACHS, Einfiihrung in die Theorie der endlichen Graphen; Leipzig 1970. [3] M. SERANINA, On an Ordering of the Set of Vertices of a Connected Graph; Publ. Fac. Sc.

Univ. Brno, No. 412, 137 - 142 (1960).

Bergakademie Freiberg Sektion Mathematik DDR - 92 Freiberg

Documents

Abzählbar-unendliche Graphen mit HAMILTONscher dritter Potenz