Existenz von Gerüsten mit vorgeschriebenem Maximalgrad in Graphen

  • Published on
    22-Aug-2016

  • View
    213

  • Download
    1

Embed Size (px)

Transcript

  • 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. hn 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 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

    Beweis : 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 benachbart ist. Es folgt dr(x)= k, da andernfalls T w xq ein grt~Berer /c-Baum als T ws T \ (x} hat also genau k Komponenten T1 . . . . . T k. Es sei n~= I Tlh und es sei t~ die zu x in T benachbarte 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 benachbart (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 benachbarten Ecken e Tj. Es sei Y1 die Menge aller y e E(T1), die zu wenigstens einem p~ mit 2 < i < k benachbart sind.

    Dann gilt:

    (1) Y1 - T(k).

    Denn existiert yeY~(OBdApzyeK(G) ) mit dr(y)- max dl(Pi) 2 dx(p~) . i=2 . . . . . k ~ 1

    k

    (p,)

  • Existenz von Gerfisten mit vorgeschriebenem Maximalgrad ir~ Graphen 265

    Analog folgt

    k

    (6) ~di(Pi)

  • 266 Sein Win

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

    xEs( ) xerO)

    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 T1 , . . . , 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,ye K(G), yze 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 ist gerade die Menge dieser z(y), d.h. man hat

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

    (4) P iSS 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 St=(n-2) /k fiir alle i= l . . . . . k, so f'tir jedes ze 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 teratur

    [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 ttamfltonian 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

Recommended

View more >