Maximale systeme unabhängiger Kanten

Gallai, T. (1964) Maximale systeme unabhängiger Kanten. A MAGYAR TUDOMÁNYOS AKADÉMIA MATEMATIKAI KUTATÓ INTÉZETÉNEK KÖZLEMÉNYEI, 9 (3). pp. 401-413.

Preview

Text cut_MATKUTINT_1964_3_pp401_-_413.pdf - Published Version Download (7MB) | Preview

Abstract

In de r vorliegenden Arbeit komme n nur solche endliche Graphen vor, die weder Schlingen, noch mehrfache Kante n enthalten. Besteht ein System E aus solchen Kanten des Graphen G, die paarweise keine gemeinsamen Punkte besitzen, so sagen wir, daß die Kante n des Systems E unabhängig sind. Die maximal e Anzahl der unabhängigen Kanten von G bezeichnen wir mit E(G) un d nennen ein System E, da s aus E(G) unabhängigen Kante n von G besteht, ein e-System von G. Besteht das System E aus unabhängigen Kanten vo n G, und ist zu dem Punk t x vo n G eine Я-Kant e (d. h. eine zu E gehörige Kante ) Inzident, so heißt x ein durc h E saturierter Punkt. Ist mi t x keine Я-Kant e inzident, so sagen wir, da ß E den Punk t x unsaturiert läßt. Ist jeder Punk t von G durch E saturiert, so ist E ein 1 -Faktor von G (s. [12], [3]). Bezeichnet n(G) die Anzahl der Punkt e von G, so gibt n(G) — 2 e(G) die „minimale Anzahl der unsaturierten Punkte " von G an. Ist л (G) — 2 e(G) = 0, so bildet jedes e-System vo n G einen 1 -Fakto r von G. Gilt n(G) — 2 e(G) > 0, so besitzt G keinen 1-Faktor. Man nenn t dan n G einen primen Graphen. Den leeren Graphe n (der weder Kante n noch Punkt e enthält) betrachten wir als nicht-prim, mit dem 1 -Fakto r E = 0 . W ir nennen einen primen Graphen G kritisch-prim, wenn für jeden Punk t x von G der Graph G — x nicht-prim ist.

Actions (login required)

Edit Item