Existenz yon Geriisten mit vorgeschriebenem Maximalgrad in Graphen

Von Stun WI~ in Hamburg

Die Graphen, die wir betrachten woUen, sind ungerichtet, besitzen weder Sehlingen noch Mehrfachk~nten. ]G I bezeichnet die Anzahl der Ecken des Graphen G und E(G) bzw. K(G) die Eckenmenge bzw. die Kantenmenge yon G. Mit da(x) bezeiehnen wir den Eckengrad yon x in G. Ein k-Baum ist ein Baum B, in dem fiir jede Ecke e gilt d B (e) _< k. Ist G ein Graph, T ein Geriist yon G (vgl. D. KOl~IG [1]), in dem jede Komponente k-Baum ist, so nennen wir T ein k-Gertist yon G. Ist G zusammenh~ngend, so sind die Begriffe ,,Hamiltonscher Weg yon G" und ,,2-Gerfist yon G" identisch. Der Begriff k-Gerfist ist also eine Ver- allgemeinerung des Begriffes des Hamiltonschen Weges. h n folgenden leiten wir Kriterien ftir die Existenz von k-Geriisten ab, die die bekannten Kriterien yon DmAc, O~E und POSA fiir das Vorhandensein yon Hamil- tonschen Wegen im Spezialfall k = 2 enthalten.

Zur Vereinfachung der Darstellung sind folgende Bezeichnungen zweckm~i}ig. Ffir x eE(G) bezeichnen wit mit N~(x) die Menge der Nachbarn yon x in G. Mit G(h:) bezeichnen wir die Menge der Ecken des Grades/c in G. Ist T ein Baum, so existiert ftir je zwei Ecken x, y yon T genau ein x, y-Weg in T, den wit mit Wr (x, y) bezeichnen. Ist w eine feste Ecke des Baumes T, so ist durch

x < _ y ~ x e WT(W, y)

eine partielle Ordnung definiert. Ffir y 4: w bezeichnen wit die zu y auf Wr(w , y) benachbarte Ecke x als unmittelbaren Vorg~nger y - yon y beziiglich w. Eine Kante mit den Endpunkten x, y wird durch xy be- zeichnet. Ffir T ~ G , x y e K(G) bezeichnen wir durch T w xy den Gra- phen mit der Eckenmenge E(T) u (x ,y} und der Kantenmenge K (T) w (xy}. Ist xy e K (G), so G \ xy der Graph, der dutch Streichung dieser Kante (unter Beibehaltung ihrer Endpunkte) entsteht.

Satz 1. G sei ein zusammenh~ngender Graph mit n Ecken. k sei eine der Zahlen 2, . . . , n - 1. Es gelte

k

(*) ~ dG (xi) > n - 1 i = l

ffir je ]c paarweise nicht benachbarte Ecken xl . . . . , x k yon G. Dann besitzt G ein k-Gerfist.

264 Sein Win

B e w e i s : Nehmen wir an, in G gs es kein k-Gerfist. T sei ein k-Baum in G mit maximaler Eckenzahl. Wegen des Zusammenhanges yon G existiert dann ein x e E (T ) , das zu einer Ecke q ~ E ( T ) in G benachbar t ist. Es folgt dr(x)= k, da andernfalls T w xq ein grt~Berer /c-Baum als T ws T \ (x} ha t also genau k Komponen ten T1 . . . . . T k. Es sei n~= I T lh und es sei t~ die zu x in T benachbar te Ecke aus T~ ( i= 1, . . . , k). In jedem T~ w~h|e man eine Ecke p~ mit dr(p~)= 1. Keine zwei Pi, Pl sind in G benachbar t (dann w~re (T u P~Pl w xq) \ tix ja ein gr(~Berer k-Baum in G). Mit dj(e) bezeichnen wir die Zahl der zu e e E(G) in G benachbar ten Ecken e Tj. Es sei Y1 die Menge aller y e E(T1), die zu wenigstens einem p~ mit 2 < i < k benachbar t sind.

Dann gilt:

(1) Y1 - T(k).

Denn existiert y e Y ~ ( O B d A p z y e K ( G ) ) mit d r ( y ) < k , so w~re (T u P2Y u xq) - t~x ein grOl3erer ]c-Baum in G als T.

(2) I s t y e Y~ und y - der unmit te lbare Vorg~nger yon y beztiglich Pl (in T), so ist Pl zu keiner Ecke z e N r (y) - {y-} in G benachbar t .

(Denn andernfaUs w~re, fails e twa P2Y e K (G) gilt, (T u P2Y u plz u u xq) - zy - tlx ein k-Baum in G mit grt~Berer Eckenzahl als T.)

(3) Es seien YI~:Y2 Ecken aus Y1. I s t z e E ( T ) mit ylz, y 2 z e K ( T ) , so liegt z au f Wr(pl, Yl) oder Wr(pl, Y2).

(Andernfalls w~ren Wr(pl, Yl) u ylz und Wr(pl, Y2) u y2z zwei ver- schiedene Pl, z-Wege im Baum T.)

(4) IYII>- max dl(Pi) 2 dx(p~) . i = 2 . . . . . k ~ 1

k

(p,) <_ 1 + 1 = 1

mit Gleichheit genau dann, wenn pix in K(G) liegt.

Aufgrund yon (3) sind ftir y ~ . yz aus Y~ die beiden (k - 1)-elementigen Mengen Nr(y~) \ (y-} (i = 1, 2) dis junkt . Also gilt wegen (1), (2) und (4)

dl (p~) < (nx - 1) - (1r 1). I Y~I k

_< ( n l - 1) - (p,) t = 2

oder k

d~ (pi) < nl - 1.

Existenz von Gerfisten mit vorgeschriebenem Maximalgrad ir~ Graphen 265

Analog folgt

k

(6) ~di(Pi) < n j - 1 f/Jr j = l . . . . . k. i = 1

Durch Addition der Ungleichungen (5) folgt wegen (6)

k k k

(7) ~ dr <_ k + ~ ~ d i(p,) i=1 i=1 j = 1

k

<_ ~ nj<n--1, j = l

was der Voraussetzung (.) widerspricht.

B e m e r k u n g : Wir stellen fest, dab wir die Ungleichung (7) allein aus der Annahme, dab G kein k-Gerfist besitzt, ohne Benutzung der Voraus- setzung (*) bewiesen haben.

Als unmittelbare Folgerung aus Satz 1 erh/ilt man den folgenden Satz vom ,,Dirac-Typ" :

Satz 2. Ist G ein zusammenh/~ngender Graph mit n Ecken und gilt d G (x) ~ (n - 1)/k fiir jede Ecke x yon G, so besitzt G ein k-Gerfist.

Weiter gilt der folgende Satz vom ,,Posa-Typ" :

Satz 3. Es sei G ein zusammenh/~ngender Graph mit n Ecken. In G gelte: (a) Ffir jede natiirliche Zahl m < (n- 2)/k sei die Zahl der Ecken x mit

d o (x) < m kleiner als m. (fl) Die Anzahl der Ecken x in G mit d6(x)<_(n-2)/k sei h6chstens

gleich (n- 2)]k. Dann besitzt G ein k-Gertist.

Bewe i s : ~ sei die Menge aller k-B/mine EG mit maximaler Ecken- zahl. ~ sei die Menge derjenigen T e ~, die eine minimale Zahl von Endpunkten hat (d.h. fiir T e ~ ist t Ttl) I minimal). T �9 ~ sei so ge- w/~hlt, dab x_~o)dG(x)~, maximal ist.

Es sei p �9 TO~ und y 4 p eine beliebige zu p in G (aber nicht in T) be- nachbarte Ecke aus T. Es sei z Nachbar von y auf WT (p, y).

Dann gilt :

(1) aT(z) = 2

und

(2) d6(z) <_ d~(p).

266 Sein Win

(W~re n~mlich dr(z ) > 2, so w~re S = (T u p y ) - y z ein k-Baum ~ G mit IS[ = [ T[ und l S(1) I < [ T(1) [. Damit folgt (1). Wiirde (2) nicht gelten, so erhielte man ~ d~ (x)< ~ d~ (x) fiir das gleiche S.)

xEs( ) x e r O )

Nehmen wir an, dal~ G kein k-Geriist besitze. Wie ira Beweis yon Satz 1 k6nnen wir dann x ~ E (T ) mit N~(x) CE(T) und also dr(x)= k ws T 1 , . . . , Tk seien die Komponenten yon T \ {x}, und Pt sei e E (Tt) mit d T (Pt) = 1 (i = 1, . . . , k). Si bezeichne die Menge aller Ecken z yon T, ftir die ein y existiert derart, daft p , y e K(G), y z e K ( T ) und z e Wr (P~, Y) gilt. Speziell hat man Pt e Si.

Es gilt NG(pt ) ~_ E ( T ) ftir alle i = 1 . . . . . k.

Ffir y e NG(pi ) sei z(y) die zu y auf Wr(pi, y) benachbarte Ecke. Dann hat man wegen (1) d r (z(y))= 2 fiir jedes y e NG(pt ) auBer in dem Fall, dal~ z(y)= Pt und PiY ~ K ( T ) gilt. Daraus folgt: Sind Yl * Y2 aus NG(Pt), so gilt z(yl)r S t i s t gerade die Menge dieser z(y), d.h. man hat

(3) [Stl=d~(p,) ( i= 1, . . . , k). Wir stellen weiter fest

(4) P i S S t fiir ]4=i.

(Denn dr(z)= 2 fiir jedes z e S,, . p, und dr(pj)= 1.)

Aufgrund yon (2) hat man

(5) d~(z) < dG(Pt) f'fir alle z e St.

Wegen Voraussetzung (~) muB also

(6) dG(Pt) = IS, I > ( n - - 2 ) / k

gelten. Es gibt ein i, so dai3 IStl > ( n - 2)/k gilt.

W~re n~mlich S t = ( n - 2 ) / k fiir alle i = l . . . . . k, so f'tir jedes z e R: = $ 1 w (P2)

d~(z)< ( n - 2)/k

und I RI = ISll + 1 = 1 + (n -2 ) / ] c wegen (6) mit Widerspruch zur Vor- aussetzung (fl).

Man schlieBt daraus

k ~ - - 2 (7) ~ d~ (p~) > 1 + k - - n - 1.

i=1 ]r

(Diese Ungleichung ist auch im Falle, dal~ ( n - 2 ) / k gebrochen ist, richtig, wie man sofort nachrechnet.)

Existenz yon Geriisten mit vorgeschriebenem Maximalgrad in Graphen 267

Die Beweisffihrung von Satz 1 (vgl. die Bemerkung vor Satz 2) ergibt k

aber ~ dG (Pi) < n - 1. Dieser Widersprueh beendet den Beweis. i=l

An dieser Stelle mOchte ich Herrn Professor 1~. H~LI~r meinen herz- lichen Dank aussprechen. Ihm verdanke ich wertvolle Anregungen und Vorschl/s zu dieser Arbeit.

L i t e r a t u r

[1] D. KONIO, Theorie der end]ichen und unendliehen Graphen. Akad. Verlag Leipzig 1936.

[2] G. A. DmAc, Some theorems on abstract graphs. Proc. London. Math. Soc. 2 (1952), 69--87.

[3] O. ORE, Note on Hamilton circuits. Amer. Math. Monthly. 67 (1960), 55. [4] O. O~E, Arc covering of Graphs. Ann. Mat. Pura Appl. 55 (1961), 315~321. [5] C. ST. J. A. NAsH-WIL~AMS, On t tamfltonian circuits in finite graphs. Proc.

Amer. Math. Soc. 17 (1966), 466~467. [6] L. P6sA, A theorem concerning Hamilton Lines. Publ. Math. Inst. Hung. Acad.

Sci. 7 (1962), 225--226. [7] D. BARNETT.E, Trees in Polyhedral Graphs. Canad. J. Math. 18 (1966), 731--736.

Eingegangen am 18. 12. 1973