Többszörösen összefügg gráfok pontszétszedései

Többszörösen összefügg® gráfok pontszétszedései

Szakdolgozat

Írta: Paholics Máté

Alkalmazott matematikus szak

Témavezet®:

Jordán Tibor, egyetemi tanár Operációkutatási Tanszék Eötvös Loránd Tudományegyetem, Természettudományi Kar

Eötvös Loránd Tudományegyetem Természettudományi Kar 2012

Tartalomjegyzék

1. Bevezet®

5

2. Összefügg® pontszétszedések

7

2.1. Irányítatlan gráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Irányított gráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. Gráfok el®írt fokszámokkal

7 8

12

3.1. Alsó és fels® korlátok . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2. Irányítások . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.3. Pontszétszedések . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

4. Fokszámsorozatok és gráfok éldiszjunkt feszít®fával

16

4.1. k éldiszjunkt feszít®fával rendelkez® gráfok tulajdonságai . . . . . . . 16 4.2. Realizációk k éldiszjunkt feszít®fával . . . . . . . . . . . . . . . . . . 20

5. Gráfok nem-szeparálható pontszétszedése

24

5.1. F® eredmények . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.2. Néhány következmény . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2

Ábrák jegyzéke

1.1. Egy gráf pontszétszedése . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.1. Az us és sv élek leemelése uv éllé . . . . . . . . . . . . . . . . . . . . 8 2.2. Az us, sv megengedett élpár . . . . . . . . . . . . . . . . . . . . . . . 9 2.3. A zs él fejét áttolhatjuk az y ponthoz . . . . . . . . . . . . . . . . . . 10 4.1. Pontösszehúzás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.1. Euler-sétát tartalmazó gráf . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2. Euler-sétát tartalmazó gráf egy pontszétszedése . . . . . . . . . . . . 30

3

ÁBRÁK JEGYZÉKE

4 Köszönetnyilvánítás

Szeretnék ezúton köszönetet mondani témavezet®mnek, Jordán Tibornak, aki rengeteg türelemmel, idejét nem sajnálva, sok segédanyaggal, észrevétellel és hasznos tanáccsal segített a szakdolgozat elkészítésében. Budapest, 2012 május 30.

Paholics Máté

1. fejezet Bevezet® Ebben a dolgozatban gráfok pontszétszedéseivel foglalkozunk. A pontszétszedés m¶velet a gráf valamely s pontját több új ponttal helyettesíti és minden, eddig az s-re illeszked® élt valamely új pontra illeszt. Ez tekinthet® az összehúzás m¶velet inverzének. Vegyük a G = (V, E) gráfot vagy irányított gráfot, amely tartalmazhat hurkokat és többszörös éleket. Legyen r : V → Z+ az a függvény, amely megmondja, hogy a gráf pontjait hány új ponttal helyettesítjük.

1.0.1. Deníció. A G gráf egy r-pontszétszedése (vagy r-szétszedése) a H gráf, amit úgy kapunk, hogy minden v ∈ V pontot r(v) darab pontra hasítunk. A v1 , ..., vr(v) pontok v részei H -ban. Minden uv ∈ E él megfelel egy H -beli élnek, amely u és v valamely részei között fut. 1.1. ábra. Egy gráf pontszétszedése

Ha az új részek fokát is meg akarjuk határozni, akkor be kell vezetnünk egy új függvényt a pontokon. Legyen ez az f .

1.0.2. Deníció. Egy r-fokszámel®írás egy olyan f függvény V -n, hogy minden v ∈ V pontra f (v) deg(v) egy partíciója r(v) pozitív egészre. Egy G gráf f -pontszét-

5

1. fejezet Bevezet®

6

szedése (vagy f -szétszedése) az az r-szétszedés, amiben a részek fokait az f (v) adja meg minden v ∈ V -re.

2. fejezet Összefügg® pontszétszedések Ebben a fejezetben megvizsgáljuk, hogy egy gráfnak mikor van többszörösen összefügg® r-pontszétszedése. 2.1.

Irányítatlan gráfok

X és Y ⊆ V részhalmazokra jelölje d(X, Y ) az X -b®l Y -ba men® éleket G-ben,

és legyen d(X) = d(X, V − X). Egy G = (V, E) gráf k -élösszefügg®, ha d(X) ≥ k , minden X ⊂ V -re. Legyen i(X) az X pontjai között futó élek száma, c(X) a G−X komponenseinek P száma és r(X) = x∈X r(x). v ∈ V -re deg(v) a v foka. Így i(v) a v -hez kapcsolódó hurkok száma és deg(v) = d(v) + 2(i(v). Nash-Williams a következ® szükséges és elégséges feltételeket fogalmazta meg ahhoz, hogy egy gráfnak legyen összefügg® r-szétszedése, vagy f -szétszedése.

2.1.1. Tétel ([5] Nash-Williams). Legyen G = (V, E) egy gráf és r : V → Z+ . Ekkor G-nek van összefügg® r-pontszétszedése, akkor és csak akkor, ha r(X) + c(X) ≤ i(X) + d(X, V − X) + 1 minden X ⊆ V -re. Továbbá, ha G-nek van összefügg® r-pontszétszedése, akkor van összefügg® f -pontszétszedése is minden f r-fokszámel®írásra. Az alábbi tétel pedig azokat a szükséges és elégséges feltételeket mondja ki, ami ahhoz kell, hogy egy gráfnak legyen k -élösszefügg® r-pontszétszedése.

2.1.2. Tétel ([5] Nash-Williams). Legyen G = (V, E) egy gráf, r : V → Z+ és k ≥ 2 egész. Ekkor G-nek van egy k -élösszefügg® r-pontszétszedése, akkor és csak

akkor, ha (a) G k -élösszefügg®, 7

2. fejezet Összefügg® pontszétszedések

8

(b) d(v) ≥ kr(v) minden v ∈ V -re, és az alábbiak közül egyik sem igaz: (c) k páratlan és G-nek van egy v elvágó pontja, melyre d(v) = 2k , i(v) = 0 és r(v) = 2, (d) k páratlan, |V | = 2, |E| = 2k , és r(v) = 2 és i(v) = 0 minden v ∈ V pontra. Továbbá, ha G-nek van k -élösszefügg® r-pontszétszedése, akkor G-nek van k -élösszefügg® f -pontszétszedése is minden f r-fokszámel®írásra, ahol dvi ≥ k minden v ∈ V -re és minden 1 ≤ i ≤ r(v)-re. 2.2.

Irányított gráfok

Ebben a részben szükséges és elégséges feltételeket adunk ahhoz, hogy egy irányított gráfban legyen k -élösszefügg® r-szétszedés vagy f -szétszedés. A bizonyításhoz használni fogjuk a leemelés m¶veletet, amely szoros kapcsolatban van a pontszétszedéssel. Egy us, sv élpár leemelésével az s pontról azt a m¶veletet értjük, hogy töröljük az us és sv éleket, és egy új uv élt adunk a gráfhoz. A kapott gráfot vagy irányított gráfot Gu,v -vel jelöljük. 2.1. ábra. Az us és sv élek leemelése uv éllé

Az us, sv élpár leemelése az s pontról megfeleltethet® annak a m¶veletnek, hogy az s pontot két részre szedjük, melyeknek fokszámai 2 és deg(s) − 2. Legyen D = (V, E) egy irányított gráf és s ∈ V . Legyen Du,v az us, sv élpár leemelésével kapott gráf. A kapott uv élt leemelt élnek nevezzük.

2.2.1. Deníció. Legyen D k-élösszefügg®. Ekkor az us, sv élpár megengedett Dben, ha Du,v k -élösszefügg®. X, Y ⊆ V diszjunkt részhalmazokra ρ(X, Y ) az Y -ból X -be tartó élek száma, ρ(X) = ρ(X, V − X). δ(X, Y ) = ρ(Y, X), δ(X) = ρ(V − X).

Egy D irányított gráf k -élösszefügg®, ha ρ(X) ≥ k minden X ⊂ V -re.


9

2.2. ábra. Az us, sv megengedett élpár

s s

u

v

u

v

Legyen d(X, Y ) = ρ(X, Y ) + δ(X, Y ), i(v) v hurokjainak száma, ρ∗ (v) = ρ(v) + i(v) v befokszáma, δ ∗ (v) = δ(v) + i(v) v kifokszáma.

2.2.2. Deníció. Az X ⊆ V − s részhalmaz be-kritikus ha ρ(X) = k és ki-kritikus ha δ(X) = k . Az X halmaz kritikus ha ρ(X) = k vagy δ(X) = k (vagy mindkett®). Egy us, sv élpár akkor és csak akkor nem megengedett, ha van olyan kritikus halmaz, amely u-t és v -t is tartalmazza. Vegyük észre, hogy egy ss hurok és sv él leemelésekor töröljük a hurkot és megtatrjuk az sv élt. Az sv élt ekkor is leemelt élnek nevezzük.

2.2.3. Lemma. Legyen D = (V, E) egy k-élösszefügg® irányított gráf és legyen s ∈ V egy pont, melyre ρ∗ (s) ≥ k + 1 és δ ∗ (s) ≥ k + 1. Ekkor minden adott sv élre

van egy megengedett us, sv élpár. A következ® lemma azt mondja ki, hogyha egy s pont befokszáma elég nagy, akkor az egyik él fejét az s ponttól áttolhatjuk egy másik ponthoz, megtartva a k -élösszefügg®séget.

2.2.4. Lemma. Legyen D = (V, E) egy k-élösszefügg® irányított gráf és legyenek s, y ∈ V olyan pontok, hogy ρ∗ (s) ≥ k + 1. Ekkor létezik egy olyan zs él, hogy D − zs + zy k -élösszefügg®. ρ , δ adott pozitív egészekre egy (ρ, δ)-pontszétszedést egy s ∈ V pontra úgy

kapunk meg, hogy az s pontot s0 és s00 részekre hasítunk, melyeknek be- és kifokszáma rendre (ρ∗ (s) − ρ, δ ∗ (s) − δ ) és (ρ, δ). Egy k -élösszefügg® irányított gráfban (ρ, δ)-pontszétszedés megengedett, ha a kapott gráf is k -élösszefügg®.

2.2.5. Lemma. Legyen D = (V, E) egy k-élösszefügg® irányított gráf és legyen s ∈ V . Legyenek ρ és δ olyan egészek, melyekre k ≤ ρ ≤ ρ∗ (s)−k és k ≤ δ ≤ δ ∗ (s)−k .

Ekkor D-nek van egy megengedett (ρ, δ)-pontszétszedése az s pontnál.


10

2.3. ábra. A zs él fejét áttolhatjuk az y ponthoz

Bizonyítás. A szimmetria miatt feltehetjük, hogy ρ ≤ δ . Indukcióval bizonyítunk δ − ρ szerint. Tegyük fel, hogy δ = ρ. Ekkor, mivel δ ∗ (s) − δ ≥ k és ρ∗ (s) − ρ ≥ k , használhatjuk a 2.2.3 lemmát, amib®l levezethetjük, hogy D-ben ρ darab megengedett leemelést hajthatunmk végre egymás után. Ha a leemelt éleket felosszuk egy ponttal, majd a felosztó pontokat összehúzzuk egy s00 ponttá, akkor egy k élösszefügg® D0 irányított gráfot kapunk. Azaz D0 egy megengedett (ρ, δ)-szétszedése D-nek. Most tegyük fel, hogy δ ≥ ρ+1 és hogy D-nek van egy D00 megengedett (ρ, δ −1)szétszedése.Szedjük szét az s pontot s0 és s00 pontokra rendre (ρ∗ (s) − ρ, δ ∗ (s) − δ + 1) és (ρ, δ − 1) fokszámokkal. Mivel δ ∗ (s) − δ + 1 ≥ k + 1, alkalmazható a 2.2.4 lemma, hogy találjunk egy olyan zs0 élt, hogy D00 − s0 z + s00 z k -élösszefügg® legyen. Ekkor D egy megengedett (ρ, δ)-pontszétszedését kapjuk. Most pedig megmutatjuk, mik azok a szükséges és elégséges feltételek ahhoz, hogy egy irányított gráfban legyen k -élösszefügg® r-szétszedés vagy f -szétszedés. Legyen D egy irányított gráf. D egy r-pontszétszedését hasonlóan deniáljuk, mint irányítatlan esetben. D egy f -pontszétszedése egy f függvény V -n, úgy hogy minden v ∈ V -re f (v) (ρVi , δiV ) rendezett párok egész sorozata (1 ≤ i ≤ r(v)), hogy Pr(v) V Pr(v) V ∗ ∗ i=1 ρi = ρ (v) és i=1 δi = δ (v). D egy f -szétszedése az az r -szétszedés, ahol a részek be- és kifokszámát az f (v) párok határozzák meg minden v ∈ V -re.

2.2.6. Tétel ([1] Tétel 1.3). Legyen D = (V, E), r : V → Z+ . D-nek van kélösszefügg® r-pontszétszedése akkor és csak akkor, ha (a) D k -élösszefügg®, (b) ρ∗ (v) ≥ kr(v) és δ ∗ (v) ≥ kr(v) minden v ∈ V -re, Továbbá, ha D-nek van k -élösszefügg® r-pontszétszedése, akkor D-nek van k -élösszefügg® f -pontszétszedése is minden f r-fokszámel®írásra, ahol ρvi és δiv ≥ k minden v ∈ V -re és minden 1 ≤ i ≤ r(v)-re.


11

Bizonyítás. Az (a) és (b) feltételek szükségessége nyilvánvaló. Ahhoz, hogy az elégségességet és a tétel második részét belássuk, meg kell mutatnuk, hogy ha D k -élösszefügg® és f egy olyan r-fokszámel®írás, ahol ρvi és δiv ≥ k minden v ∈ V re, akkor D-nek van egy k -élösszefügg® f -pontszétszedése. Indukcióval bizonyítunk P v∈V (r(v) − 1) szerint. Ha r(v) = 1, akkor az állítás nyilván igaz. Tegyük fel, hogy van egy él, melyre r(v) ≥ 2. A 2.2.5 lemma miatt D-nek van egy D0 megengedett (ρv1 , δ1v )-szétszedése v -nél, melyet úgy kapunk, hogy a v -t szétszedjük a v 0 és v 00 élekre rendre (ρ∗ (v) − ρv1 , δ ∗ (v) − δ1v ) és (ρv1 , δ1v ) fokszámokkal. Ezután alkalmazzuk az indukciót D0 -re, ahol r0 (v 0 ) = r(v) − 1, r0 (v 00 ) = 1, f 0 (v 00 ) = ((ρv1 , δ1v )), f 0 (v 0 ) = ((ρv2 , δ2v ), ..., (ρvr (v), δrv (v))) és minden más u élre r0 (u) = r(u) és f 0 (u) = f (u).

3. fejezet Gráfok el®írt fokszámokkal Ebben a fejezetben megvizsgáljuk, hogy mikor van egy gráfnak olyan irányítása, amelynek van k éldiszjunkt feszített feny®je egy kijelölt s gyökérrel, és eleget tesz a bemen® élek alsó és fels® korlátjának a gráf minden pontjában. Erre adunk szükséges és elégséges feltételeket. Az eredményt felhasználjuk arra, hogy jellemezni tudjuk azokat a gráfokat, amelyeknek van k éldiszjunkt feszít®fát tartalmazó pontszétszedése. 3.1.

Alsó és fels® korlátok

Legyen l, u : V → Z+ két függvény.

3.1.1. Deníció. G gráf egy D irányítása l-irányítás (u-irányítás), ha l(v) ≤ ρ(v) (ρ(v) ≤ u(v)) minden v ∈ V -re. Továbbá D egy (l, u)-irányítás, ha egyidej¶leg mindkét megkötést kielégíti. A következ® tétel megmutatja, hogy egy gráfnak mikor van (l, u)-irányítása.

3.1.2. Tétel ([2] Tétel 2 ). Legyen G = (V, E) egy gráf és legyen l, u : V → Z+ két függvény, melyekre l ≤ u. Ekkor G-nek van (l, u)-irányítása akkor és csak akkor ha e(X) ≥ l(X) minden X ⊆ V − re,

és i(X) ≤ u(X) minden X ⊆ V − re.

Az X, Y ⊆ V részhalmazok keresztez®k, ha az X ∩Y , X \Y , Y \X és a V \(X ∪Y ) közül egyik sem üres. 12

3. fejezet Gráfok el®írt fokszámokkal

13

A q : 2V → Z+ , q(∅) = q(V ) = 0 függvény keresztez® G-szupermoduláris, ha q(X) + q(Y ) ≤ q(X ∩ Y ) + q(X ∪ Y ) + d(X, Y )

minden X, Y ⊆ V keresztez® párra. A V egy P = {X1 , X2 , . . . , Xt } partíciójára legyen e(P) a P különböz® részeit összeköt® élek száma. G egy D irányításában az X -be men® élek számát ρ(X)-szel jelöljük.

3.1.3. Tétel ([2] Tétel 3). Legyen G = (V, E) egy gráf és legyen q : 2V → Z+ egy keresztez® G-szupermoduláris függvény. Ekkor G-nek van egy D irányítása, melyben ρ(X) ≥ q(X) minden X ⊆ V -re, akkor és csak akkor, ha e(P) ≥

t X

q(Xi )

i=1

és e(P) ≥

t X

q(V \ Xi )

i=1

V -nek minden P = {X1 , X2 , . . . , Xt } partíciójára.

3.2.

Irányítások

Legyen D = (V, E) egy irányított gráf és legyen s ∈ V . Azt mondjuk, hogy D k -élösszefügg® s gyökérrel ha ρ(X) ≥ k minden X ⊆ V − s-re. Az alábbi tétel az olyan gráfokat jellemzi, amelynek van olyan (l, u)-irányítása, amely k -élösszefügg® s gyökérrel.

3.2.1. Tétel ([2] Tétel 4). Legyen G = (V, E) egy gráf, legyen s ∈ V és legyen l, u : V → Z+ két függvény, melyekre l ≤ u. Ekkor G-nek van (l, u)-irányítása,

amely k -élösszefügg® s gyökérrel akkor és csak akkor ha e(P) ≥

t X

h(Xi )

(3.1)

i=1

V -nek minden P = {X1 , X2 , . . . , Xt } partíciójára, ahol h(X) = k minden X ⊆ V −s-

re, |X| ≥ 2, h(v) = max{l(v), k} minden v ∈ V − s-re, h(s) = l(s), és h(X) = 0 egyébként, és i(X) + k(X) ≤ u(X)

minden X ⊆ V -re, ahol (X) = 1 ha s 6∈ X és (X) = 0 egyébként.

(3.2)


14

Ha az el®bbi tételben u ≡ ∞ (ill l ≡ 0), akkor arra a következtetésre juthatunk, hogy G-nek van egy olyan l-irényítása (ill. u-irányítása), amely k -élösszefügg® s gyökérrel akkor és csak akkor, ha (3.1) teljesül (ill. G-nek van k éldiszjunkt feszít®fája és (3.2) teljesül). Ha csak alsó korlát van megadva, és k = 1, akkor a következ®képpen egyszer¶síthetjük az eredményt:

3.2.2. Tétel ([2] Tétel 9). Legyen G = (V, E) egy gráf, s ∈ V és l : V → Z+ . Ekkor G-nek van egy l-irányítása, amely tartalmaz egy s-feny®t akkor és csak akkor, ha e(X) ≥ l(X) + c(X) − (X)

minden X ⊆ V -re, ahol (X) = 1 ha s 6∈ X és (X) = 0 egyébként. 3.3.

Pontszétszedések

Ebben a részben olyan pontszétszedéseket vizsgálunk, amelyek eleget tesznek bizonyos összefügg®ségi követelményeknek. Egy G gráf k -partíció-összefügg®, ha tartalmaz k éldiszjunkt feszít®fát.

3.3.1. Tétel ([2] Tétel 11). Legyen G = (V, E) egy gráf és k egy pozitív egész. Ekkor G-nek van egy k -partíció-összefügg® r-pontszétszedése akkor és csak akkor, ha i(X0 ) + e(P) ≥ k(t − 1) + kr(X0 )

(3.3)

V -nek minden P = {X1 , X2 , . . . , Xt } partíciójára, ahol X0 lehet üres. Továbbá, ha G-

nek van egy k -partíció-összefügg® r-pontszétszedése, akkor G-nek van egy k -partícióösszefügg® f -pontszétszedése is, minden f r-fokszámel®írásra, melyre dvi ≥ k minden v ∈ V és 1 ≤ i ≤ r(v). A következ® tétel a Nash-Williams tétel hurokmentes változata.

3.3.2. Tétel ([2] Tétel 12). Legyen G = (V, E) egy gráf, r : V → Z+ és f egy rfokszámel®írás. Tegyük fel, hogy G-nek van egy összefügg® r-pontszétszedése. Ekkor (i) G-nek van egy összefügg® hurokmentes r-pontszétszedése akkor és csak akkor, ha r(v) ≥ 2 minden v ∈ V -re, amire i(v) ≥ 1, (ii) G-nek van egy összefügg® hurokmentes f -pontszétszedése akkor és csak akkor ha dvi ≤ d(v) + i(v) minden v ∈ V -re és 1 ≤ i ≤ r(v)-re.


15

Bizonyítás (i) Legyen H egy összefügg® r-szétszedés és tegyük fel, hogy v egyik vi részén van egy hurok. Ekkor r(v) ≥ 2 és így a hurok eltüntethet®, ha egyik végét áttoljuk v egy másik részéhez. (ii) Legyen H egy összefügg® f -szétszedés és tegyük fel, hogy v egyik vi részén van egy hurok. Mivel deg(vi ) = dvi ≤ d(v)+ i(v), ezért van egy vj vl él, ahol vj , vl 6= vi részei v -nek. Ekkor megszüntethetjük a hurkot úgy, hogy töröljük azt és a vj vl élet, és a gráfhoz hozzáadunk két új élet, vi vj -t és vi vl -t. Ekkor H összefügg® marad és a fokszámok sem változnak.

4. fejezet Fokszámsorozatok és gráfok éldiszjunkt feszít®fával Ebben a fejezetben azt fogjuk vizsgálni, hogy milyen tulajdonságú fokszámsorozatoknak vannak realizációi, azaz pozitív egészek egy d1 , d2 , ..., dn sorozatához van-e olyan n pontú gráf, hogy a vi pont foka di minden 1 ≤ i ≤ n-re. Továbbá azt is megköveteljük, hogy a gráf rendelkezzen k éldiszjunkt feszít®fával. 4.1.

k

éldiszjunkt feszít®fával rendelkez® gráfok tu-

lajdonságai

El®ször összegezünk néhány hasznos tulajdonságot a legalább k éldiszjunkt feszít®fával rendelkez® gráfokkal kapcsolatban. Legyen G gráf és k ≥ 2 egész. Legyen τ (G) az éldiszjunkt feszít®fák száma G-ben, és Tk azon gráfok halmaza, melyre τ (G) ≥ k . Deníció szerint, K1 ∈ Tk minden k > 0 egészre. v ∈ V (G) pontra és K részgráfra G-ben, dK (v) azon pontok száma K -ban, amelyek szomszédosak v -vel G-ben. Ha X ⊆ E(G), akkor G[X] az a részgráf G-ben, amelyet az X indukál, és G(X) a feszít® részgráf G-ben X élhalmazzal. A G gráf nemtriviális, ha E(G) 6= ∅. Legyen X ⊂ E(G), ekkor G/X egy összehúzása G-nek, amit úgy kapunk, hogy az X -beli élek két végpontját összehúzzuk egy ponttá, és töröljük a hurkokat a kapott gráfból. Ha X = {e}, akkor G/{e} = G/e. Továbbá G/∅ = G.

4.1.1. Lemma. Bármely k egészre Tk összefügg® gráfok egy családja, melyekre igazak: (i) K1 ∈ Tk 16

4. fejezet Fokszámsorozatok és gráfok éldiszjunkt feszít®fával

17

4.1. ábra. Pontösszehúzás

(ii) Ha e ∈ E(G) és G ∈ Tk , akkor G/e ∈ Tk (iii) Ha H részgráfja G-nek, és H , G/H ∈ Tk , akkor G ∈ Tk (iv) Ha H1 és H2 olyan részgráfjai G-nek, melyekre H1 , H2 ∈ Tk és V (H1 ) ∩ V (H2 ) 6= ∅, akkor H1 ∪ H2 ∈ Tk G egy H részgráfjának s¶r¶ségét a következ®képpen deniáljuk: d(H) =

|E(H)| |V (H)−1|

,

ha |V (H)| > 1.

4.1.2. Tétel ([3] Tétel 2.2). Legyen G egy gráf. Ha d(G) ≥ k, akkor G-nek van egy olyan nemtriviális H részgráfja, hogy H ∈ Tk .

4.1.3. Deníció. Legyen G egy nemtriviális összefügg® gráf, r egy pozitív egész. Ekkor G-nek egy nemtriviális H részgráfja Tr -maximális ha H ∈ Tr és H -nak nincs olyan K részgráfja, hogy K ∈ Tr . G-nek egy Tr -maximális H részgráfja r-régió, ha r = τ (H). Legyen τ¯(G) = max { r: G-nek van egy r-régió részgráfja}.

4.1.4. Lemma. Legyenek r és r0 > 0 egészek, H egy r-régiója, H 0 pedig egy r0 régiója G-nek. Ekkor az alábbiak közül pontosan egy igaz: (i) V (H) ∩ V (H 0 ) = ∅ (ii) r = r0 és H = H 0 (iii) r < r0 és H egy nemfeszít® részgráfja H 0 -nek (iv) r > r0 és H tartalmazza H 0 -t, mint egy nemfeszít® részgráfot

4.1.5. Tétel ([3] Tétel 2.4). Legyen G egy nemtriviális összefügg® gráf, ekkor


18

(a) létezik egy m pozitív egész és egy (i1 , i2 , ..., im ) rendezett m-es, hogy τ (G) = i1 < i2 < · · · < im = τ¯(G)

és az élek részhalmazainak egy sorozata Em ⊂ · · · ⊂ E2 ⊂ E1 = E(G)

úgy, hogy a G[Ej ] részgráfok minden komponense egy r-régiója G-nek valamilyen r ≥ ij -re, (1 ≤ j ≤ m), és hogy legalább egy komponens H ∈ G[Ej ] egy ij -régiója G-nek; (b) ha H egy olyan részgráfja G-nek, hogy τ (H) ≥ ij , akkor E(H) ⊆ Ej ; (c) minden gráfban egy ilyen m és élrészhalmaz-sorozat van.

4.1.6. Lemma. Legyen k ≥ 1 egy egész, G egy gráf, melyre τ¯(G) ≥ k. Ekkor a következ®k igazak: (i) G-nek van egy egyedülálló Xk ⊆ E(G) élhalmaza úgy, hogy G[Xk ] minden komponense egy Tk -maximális részgráf. Vagyis G 6∈ Tk akkor és csak akkor, ha E(G) 6= Xk . (ii) ha G 6∈ Tk , akkor G/Xk nem tartalmaz olyan H 0 nemtriviális részgráfot, melyre τ (H 0 ) ≥ k . (iii) ha G 6∈ Tk , akkor d(H 0 ) < k G/Xk bármely nemtriviális részgráfjára. Bizonyítás. Ha G ∈ Tk , akkor E(G) = Xk . Tegyük fel tehát, hogy G 6∈ Tk . Mivel τ (G) < k ≤ τ¯(G), a 4.1.5 tétel (a) pontja miatt létezik olyan j egész, hogy ij−1 < k ≤ ij . Legyen Xk = Eij . Ekkor G[Xk ] minden komponense egy Tk -maximális részgráf. A 4.1.5 tétel (c) pontja miatt egyetlen ilyen Xk van. Ezzel bebizonyítottuk az (i) részt. A (ii) részt bizonyításához tegyük fel indirekt, hogy G[Xk ] tartalmaz egy nemtriviális H 0 részgráfot, melyre τ (H 0 ) ≥ k és V (H 0 ) = {v1 , v2 , ..., vh }, h ≥ 2. Tegyük fel, hogy a vi összehúzás el®tti képe a G-ben a Hi , és Hi nemtriviális 1 ≤ i ≤ t-re és triviális t + 1 ≤ i ≤ h-ra. Legyen G0 = G[∪hi=1 V (Hi )]. Indukcióval megmutatjuk, hogy τ (G0 ) ≥ k . Legyen t = 1, ekkor G0 /H1 = H 0 és H 0 , H ∈ Tk . A 4.1.1 lemma (iii) pontja miatt ekkor G0 ∈ Tk . Tegyük fel, hogy t ≤ s-re már tudjuk, hogy G ∈ Tk . Most nézzük t = s + 1-re. Ekkor az indukciós feltevés miatt G0 /Hs+1 ∈ Tk , így a 4.1.1 (iii) pontja miatt G0 ∈ Tk , tehát a (ii) rész is teljesül. A (iii) rész bizonyításához indirekt tegyük fel, hogy d(H 0 ) ≥ k . Ekkor |E(H 0 )| ≥ k(|V (H 0 )|−1). A 4.1.2 tétel miatt H 0 -nak van olyan H 00 nemtriviális részgráfja, hogy


19

H 00 ∈ Tk . De mivel H 00 is egy nemtriviális részgráfja G/Xk -nak ez ellentmond a (ii)

résznek.

Vegyük észre, hogy a 4.1.2 tétel alapján d(G) ≥ k -b®l következik, hogy τ¯(G) ≥ k . Így, ha (G) ≥ k , akkor a 4.1.6 lemmában deniált Xk élrészhalmaz létezik.

4.1.7. Lemma. Legyen G egy gráf, melyre d(G) ≥ k és legyen Xk ⊂ E(G) a 4.1.6 lemmában deniált élrészhalmaz. Ha G[Xk ]-nak van legalább két komponense, akkor bármely nemtriviális H komponensére d(H) ≥ k és van legalább egy olyan H komponense, hogy d(H) > k . Bizonyítás A 4.1.6 lemma (i) alapján G[Xk ] bármmely nemtriviális H komponensére H ∈ Tk . Ezért |E(H)| ≥ k(|V (H)| − 1) és így d(H) ≥ k . Tegyük fel, hogy G[Xk ]-nak van c ≥ 2 komponense: H1 , H2 , ..., Hc . Indirekt tegyük fel, hogy G[Xk ] minden H nemtriviális komponensére d(H) = k . Legyen x = |E(G) − Xk |. Ekkor |E(Hi )| = k(|V (Hi )| − 1) minden 1 ≤ i ≤ c-re és |E(G)| =

c X i=1

|E(Hi )| + x =

c X

(k|V (Hi )| − k) + x = k|V (G)| − kc + x

i=1

Ebb®l x = |E(G)| − k|V (G)| + kc ≥ k(|V (G)| − 1) − k|V (G)| + kc = k(c − 1). Legyen G0 = G/G[Xk ]. Ekkor |V (G0 )| = c > 1 és |E(G0 )| = x. Tehát d(G0 ) ≥ k , ami ellentmond a 4.1.6 lemma (iii) pontjának. Így tehát G[Xk ]-nak van legalább egy Hi komponense, hogy d(Hi ) > k . Jelölje α0 (G) a G gráf maximális párosításának a méretét.

4.1.8. Lemma. Minden egyszer¶ G gráfra, melyre E(G) ≥ 1, α (G) ≥ 0

l

τ (G) 2

m

.

4.1.9. Deníció. η(G) = min {d(G/X) : |V (X)| < |V (G)|} a G gráf er®ssége. A G gráf egy H részgráfja η -maximális, ha G minden olyan H 0 részgráfjára, amelynek H valódi részgráfja, η(H 0 ) < η(H).

4.1.10. Tétel ([3] Tétel 2.10). Minden k ≤ d(G) egészre vagy E(G) k darab éldiszjunkt feszít®fa úniója, vagy G-nek van egyetlen olyan X élrészhalmaza, hogy η(H) > k és H = G[X] η -maximális. Egy G összefügg® gráfra legyen Ek (G) = {e ∈ E(G) : τ (G − e) ≥ k}.

4.1.11. Tétel ([3] Tétel 2.11). Legyen G egy összefügg® gráf, melyre τ (G) ≥ k. Ekkor Ek (G) = E(G) akkor és csak akkor, ha η(G) > k .


20

Ha H1 és H2 két részgráfja G-nek, akkor legyen E(H1 , H2 ) = {e = uv ∈ E(G) : u ∈ V (H1 ), v ∈ V (H2 )}.

4.1.12. Lemma. Legyen G egy egyszer¶ gráf és legyen Xk ⊂ E(G) a 4.1.6 lemmában deniált élhalmaz. Ha H 0 és H 00 két komponense G(Xk )-nak, akkor az alábbiak teljesülnek: (i) |E(H 0 , H 00 )| < k (ii) ha d(H 0 ) > k , akkor létezik olyan K ⊆ H1 , hogy d(K) > k és τ (K − e) ≥ k minden e ∈ E(K)-ra (iii) ha d(H 0 ) > k , akkor létezik olyan e0 ∈ E(H 0 ), hogy τ (H 0 −e0 ) ≥ k és E(G)−Xk nak legfeljebb egy olyan éle van, amely összeköti e0 végeit H 00 -vel.

4.1.13. Lemma. Legyen G egy nemtriviális gráf, melyre τ (G) ≥ k. Ha d(G) = k, akkor G minden nemtriviális H részgráfjára d(H) ≤ k . Továbbá, ha τ (H) ≥ k , akkor d(H) = k . Bizonyítás. Mivel τ (G) ≥ k és |E(G)| = k(|V (G)| − 1), ezért τ (G) = k és E(G) k darab éldiszjunkt feszít®fa úniója. Legyenek T1 , T2 , ..., Tk éldiszjunk feszít®fák Gben. Ekkor G minden nemtriviális H részgráfjára |E(H) ∩ E(Ti )| ≤ |V (H)| − 1, 1 ≤ i ≤ k . Ezért |E(H)| = |E(H) ∩

(∪ki=1 E(Ti ))|

=

k X

|E(H) ∩ E(Ti )| ≤ k(|V (H)| − 1)

i=1

Tehát d(H) ≤ k . Ha τ (H) ≥ k , akkor |E(H)| ≥ k(|V (H)| − 1), és így d(H) ≥ k . Ezekb®l következik, hogy d(H) = k . 4.2.

Realizációk

k

éldiszjunkt feszít®fával

Most megmutatjuk, melyek azok a fokszámsorozatok, amelyeknek van realizációja k darab éldiszjunkt feszít®fval. Legyen G = (V, E) véges, irányítatlan, hurok nélküli gráf, |V | = n, d1 , d2 , ..., dn fokszámsorozat. ω(G) a G gráf komponenseinek száma. A d = (d1 , d2 , ..., dn ) sorozat nemnövekv®, ha d1 ≥ d2 ≥ ... ≥ dn . A d sorozat grakus, ha van G egyszer¶ gráf d fokszámsorozattal. Ebben az esetben G a d-nek egy realizációja, vagy azt mondjuk, hogy G egy d-realizáció.

4.2.1. Tétel ([3] Tétel 3.1). Egy d nemnövekv® grakus sorozatnak van G ∈ Tk realizációja, akkor és csak akkor, ha vagy n = 1 és d1 = 0 vagy n ≥ 2 és az alábbiak teljesülnek:


21

(i) dn ≥ k (ii)

Pn

i=1

≥ 2k(n − 1)

Bizonyítás. Ha n = 1 és d1 = 0 az állítás triviális. Tegyük fel, hogy n > 1. Ha P G ∈ Tk , akkor 2k(|V (G)| − 1) ≤ 2|E(G)| = ni=1 di és minden pont foka legalább k . Ez bizonyítja a szükségességet. Most belátjuk az elégségességet. Tegyük fel, hogy d egy nemnövekv® grakus fokszámsorozat, melyre teljesülnek a 4.2.1 tétel (i) és (ii) pontja. Tegyük fel indirekt, hogy minden G d-realizációra G 6∈ Tk . Ekkor a 4.1.6 lemma miatt G-nek van egyetlen olyan Xk ⊆ E(G) élrészhalmaza, hogy G[Xk ] komponensei Tk -maximális részgráfok. Legyen X = E(G) − Xk . Mivel G 6∈ Tk , X 6= ∅. Tegyük fel, hogy G − X -nek c darab komponense van, H1 , H2 , ..., Hc , amelyek úgy vannak jelölve, hogy d(H1 ) ≥ d(H2 ) ≥ · · · ≥ d(Hc ) és Hj = K1 minden j = t + 1, ..., c-re. Legyenek F1 (G) = {Hi : d(Hi ) > k} és F2 (G) = {Hi : d(Hi ) = k}

Ekkor |F1 (G)| + |F2 (G)| = t.

1.Állítás Ha egyetlen d-realizáció sincs Tk -ban, akkor létezik egy olyan G d-realizáció, hogy |F1 (G)| = 1. Indirekt tegyük fel, hogy minden G d-realizációra |F1 (G)| ≥ 2. Válasszunk egy olyan G d-realizációt, melyre ω(G − X) minimális és ezek közül is olyat, melyre |X| maximális. Mivel |F1 (G)| ≥ 2, ezért d(H1 , d(H2 ) ≥ k . A 4.1.12 lemma (iii) pontja miatt létezik e1 = u1 v1 ∈ E(H1 ) és e2 = u2 v2 ∈ E(H2 ) úgy, hogy H1 − e1 , H2 − e2 ∈ Tk , és az e1 és e2 élek végeihez legfeljebb egy X -beli él csatlakozik. Az általánosság megszorítása nélkül feltehetjük, hogy u1 u2 , v1 v2 6∈ E(G). Ekkor legyen G1 = (G − {u1 v1 , u2 v2 }) ∪ {u1 u2 , v1 v2 } és X1 = X ∪ {u1 u2 , v1 v2 }

(4.1)

Ekkor az u1 u2 és v1 v2 élek választása miatt G1 is egy d-realizáció. Mivel G1 −X1 = (H1 − u1 v1 ) ∪ (H2 − u2 v2 ) ∪ H3 ∪ · · · ∪ Hc , G1 − X1 minden komponense Tk -beli és ω(G − X) minimális, ezért E(G1 )-nek az X1 az egyetlen olyan részgráfja, hogy ω(G1 − X1 ) = ω(G − X) = c és G1 − X1 minden komponense egy Tk -maximális részgráf. Ekkor |X1 | = |X| + 2, ami ellentmond annak, hogy |X| maximális. Ezzel beláttuk az 1. állítást. A 4.1.7 lemma alapján egy tetsz®leges G0 gráfra vagy G0 ∈ Tk vagy |F1 (G0 )| ≥ 1. A tétel bizonyításához tegyük fel indirekt, hogy minden G d-realizációra G ∈ Tk . Ekkor az 1. állítás miatt létezik olyan G, melyre |F1 (G)| = 1. Válasszunk egy olyan


22

G d-realizációt melyre teljesül, hogy |F1 (G)| = 1 és |V (H1 )| maximális

(4.2)

ezek közül is válasszunk olyat, melyre |X| maximális. Nézzük a következ® eseteket.

1.Eset: t ≥ 2, és így H2 6= K1 . Ekkor a 4.1.12 lemma (iii) pontja miatt létezik olyan e1 ∈ E(H1 ) és e2 ∈ E(H2 ), hogy G-ben legfeljebb egy él csatlakozik e1 -hez és e2 -höz, és H1 − e1 ∈ Tk . Legyen G1 és X1 mint (4.1)-ben. Mivel d(H2 − e2 ) < k , H2 − e2 már nincs benne Tk -ban. Legyenek G1 [(H1 − e1 ) ∪ (H2 − e2 )] Tk -maximális részgráfjai H1,2 , H2,1 , ..., H2,t2 , ahol H1 − e1 ⊆ H1,2 és H2,1 , ..., H2,t2 ⊆ H2 − e2 . Mivel d(H2 ) = k és H2,i ⊆ H2 , ezért a 4.1.13 lemma miatt minden H2,i -re vagy d(H2,i ) = k vagy H2,i = K1 . Vegyük észre, hogy G/(H1 ∪ H2 ) = G1 /[(H1 − e1 ) ∪ (H2 − e2 )]. Következésképpen H1,2 , H2,1 , ..., H2,t2 , H3 , ..., Hc Tk -maximális részgráfjai G1 -nek. (4.2) és F1 (G1 ) = H1,2 miatt H1,2 = H1 − e1 . Legyen X 0 olyan élrészgráfja G1 -nek, hogy G1 − X 0 = H1,2 ∪ H2,1 ∪ · · · ∪ H2,t2 ∪ H3 ∪ · · · ∪ Hc . Ekkor X 6= X1 és X ⊂ X1 ⊂ X 0 , ami ellentmond annak, hogy |X| maximális. 2.Eset: t = 1, és így H2 = K1 . Ha c = 2, akkor a 4.2.1 tétel (i) miatt H1 és H2 között leglább k él fut. Mivel H1 ∈ Tk , következik, hogy G ∈ Tk , ami ellentmond a feltevéseinknek. Így tehát c ≥ 3. Legyen V (Hi ) = {xi }, i ≥ 2-re. Vegyük észre, hogy minden Hi = K1 -re létezik egy Hj = K1 , hogy e = xi xj ∈ X . Máskülönben xi csak H1 -beli ponthoz csatlakozhatna és a 4.2.1 (i) miatt |E(Hi , H1 )| ≥ k lenne, ami ellentmond a 4.1.12 lemma (i) pontjának. Az általánosság megszorítása nélkül feltehet®, hogy x2 x3 ∈ X . A 4.1.12 lemma miatt létezik egy nemtriviális K ⊆ H1 részgráf, hogy K − e ∈ Tk minden e ∈ E(K)-ra. 2.Állítás Létezik olyan e0 = uv ∈ E(K), hogy ux2 , vx3 6∈ E(G). A bizonyításhoz deniáljuk a következ®ket: B1 = {v ∈ V (K) : vx2 , vx3 6∈ E(G)},

B2 = {v ∈ V (K) : vx2 ∈ (EG), vx3 6∈ E(G)}

B3 = {v ∈ V (K) : vx2 6∈ (EG), vx3 ∈ E(G)},

B4 = {v ∈ V (K) : vx2 , vx3 ∈ E(G)}

és legyen N (B1 ) = {v ∈ V (K) : ∃u ∈ B1 hogy uv ∈ E(K)}. A deníció miatt V (K) = B1 ∪ B2 ∪ B3 ∪ B4 . Ha B1 = ∅, akkor N (B2 ) ∪ N (B3 ) ⊆ B4 . Ekkor |B4 | ≥ k − 1 és így x2 legalább k éllel csatlakozik K -hoz, ami ellentmond annak,


23

hogy x2 6∈ V (H1 ). Tehát B1 6= ∅. Ha E(G[B1 ]) 6= ∅, akkor a 2. állítás teljesül. Tegyük fel tehát, hogy E(G[B1 ]) = ∅. Ebb®l következik, hogy N (B1 ) ∩ B1 = ∅. El®ször megmutatjuk, hogy N (B1 ) ∩ [B2 ∪ B3 ] 6= ∅

(4.3)

Ha ez nem igaz, akkor N (B1 ) ⊆ B4 , mert V (K) = B1 ∪ B2 ∪ B3 ∪ B4 . Mivel K ∈ Tk , ezért minden v ∈ B1 élre dk (v) ≥ k , amib®l következik, hogy |B4 | ≥ |N (B1 )| ≥ k . Ekkor viszont a B4 deníciója miatt |E(H1 , H2 )| ≥ |E(B4 , x2 )| = |B4 | ≥ k , ami ellentmond a 4.1.12 lemma (i) pontjának. Tehát (4.3) igaz. Ez azt jelenti, hogy létezik v ∈ N (B1 ) ∩ B2 vagy létezik u ∈ N (B1 ) ∩ B3 . El®ször tegyük fel, hogy létezik v ∈ N (B1 ) ∩ B2 . Ekkor létezik u ∈ B1 , hogy uv ∈ E(K). A B1 és B2 deníciója miatt ux2 6∈ E(G) és vx3 6∈ E(G), tehát igaz az állítás. Most tegyük fel, hogy létezik u ∈ N (B1 ) ∩ B3 . Ekkor létezik v ∈ B1 , hogy uv ∈ E(K). A B3 és B1 deníciója miatt ux2 6∈ E(G) és vx3 6∈ E(G), tehát az állítás szintén igaz. Ezzel bebizonyítottuk a 2. állítást. A 2. állítás szerint legyenek G2 = (G − x2 x3 − uv) ∪ ux2 , vx3 és X2 = X − x2 x3 ∪ ux2 , vx3

Ekkor az u, v, x2 és x3 választása miatt G2 is egy d-realizáció. Megmutatjuk, hogy F(G2 ) = 1. Indirekt tegyük fel, hogy F(G2 ) ≥ 2. Ekkor létezik egy S ∈ F(G2 ), ami nem egyenl® H1 − uv -vel. A 4.1.1 lemma (iv) miatt V (S) ∩ V (H1 ) = ∅. De ekkoor S egy H1 -t®l különböz® részgráfja G-nek, ami ellentmond annak, hogy F(G) = 1. 4.2 alapján H1 −uv egy Tk -maximális részgráfja G-nek. Mivel G2 [H2 ∪· · ·∪Hc ] = G2 [H2 ∪ · · · ∪ Hc ] − x2 x3 , ezért H2 , ..., Hc Tk -maximális részgráfjai G2 -nek. Ekkor viszont |X2 | = |X1 | + 1, ami ellentmond annak, hogy |X1 | maximális. Ezzel bebizonyítottuk a tételt.

5. fejezet Gráfok nem-szeparálható pontszétszedése Ebben a fejezetben azzal a kérdéssel foglalkozunk, hogy adott G gráfra és r : V (G) → Z+ függvényre mik azok a szükséges és elégséges feltételek ahhoz, hogy G-nek legyen egy nem-szeparálható r-pontszétszedése, azaz egy olyan összefügg® r-szétszedése, ami nem tartalmaz elvágó pontot. 5.1.

F® eredmények

Legyen G egy gráf. Egy v ∈ G pont elvágó pont, ha |E(G)| ≥ 2 és v -hez csatlakozik egy hurok, vagy G − v -nek több komponense van, mint G-nek.

5.1.1. Deníció. Egy gráf nem-szeparálható, ha összefügg® és nincs elvágó pontja. 5.1.2. Deníció. Legyen G egy gráf és N (G) = {v ∈ V : deg(v) ≥ 4}. Adott r : V → Z+ -re legyen N1 (G, r) = {v ∈ N (G) : r(v) = 1} és N2 (G, r) = {v ∈ N (G) : r(v) = 2}.

Megmutatjuk, mik azok a szükséges és elégséges feltételek, hogy G-nek legyen egy nem-szeparálható r-pontszétszedése. Ehhez szükségünk lesz a következ® lemmákra. A lemmákat hurokmentes gráfokra mondjuk ki, de alkalmazhatók hurkokat tartalmazó gráfokra is, ha a gráf hurokjait felosztjuk.

5.1.3. Lemma. Legyen G egy kétszeresen összefügg® hurokmentes gráf és v ∈ N (G). Legyen r : V → Z+ , melyre r(v) = 2 és r(u) = 1 minden u ∈ V − v -re. Ekkor G-nek létezik egy olyan H kétszeresen élösszefügg® r-szétszedése, hogy v H -beli részei közül legalább egynek a foka kett®. Továbbá, ha v egy elvágó pontja G-nek, akkor G-nek létezik egy olyan H 0 kétszeresen élösszefügg® r-szétszedése, hogy v részei v1 , v2 nem elvágó pontok H 0 -ben és dH 0 (v2 ) = c(v). 24

5. fejezet Gráfok nem-szeparálható pontszétszedése

25

5.1.4. Deníció. Legyen G egy gráf. B egy blokk G-ben ha maximális nem-szeparálható részgráfja G-nek. Ha G nem-szeparálható, akkor maga is egy blokk. A v ∈ V pont egy bels® pont B -ben, ha v nem elvágó pontja G-nek. Egy végblokk G-ben egy olyan blokk, amely legfeljebb egy G-beli elvágó pontot tartalmaz. Vegyük észre, hogyha G szétválasztható, akkor van legalább két végblokkja.

5.1.5. Deníció. Azt mondjuk, hogy G egy uv-blokkút, ha G összefügg® és pontosan két végblokkja van, B1 és B2 , és u, v rendre a B1 és B2 bels® pontjai. ux és vz élekre G(ux, vz) = G − {ux, vz} ∪ {uz, vx}. Vegyük észre, hogy ez a csere meg®rzi G fokszámsorozatát. A következ® lemma megmutatja, hogyan lehet ezzel a cserével csökkenteni a blokkok számát egy gráfban.

5.1.6. Lemma. Legyen G egy hurokmentes gráf, és ux, vz ∈ E(G) olyan élek, melyek pontdiszjunkt körökhöz tartoznak G-ben. Tegyük fel, hogy G egy blokk vagy egy uv -blokkút. Ekkor G(ux, vz) egy blokk. Bizonyítás Legyenek C1 és C2 diszjunkt körök, melyek rendre tartalmazzák ux-et és vz -t. Ekkor (C1 − ux) ∪ (C2 − vz) ∪ {uz, vx} egy kört indukál G(ux, vz)-ben, amely tartalmazza az u, x, v, z pontokat. Mivel G−{ux, vz} minden végblokkja tartalmazza u, x, v vagy z valamelyikét, mint bels® pontot, ezért G(ux, vz) egy blokk. Megmutatjuk, hogy ha G-nek van egy f -szétszedése egyetlen y ∈ N1 (G) vágócsúccsal, akkor G-nek van egy nem-szeparálható f -szétszedése, vagy van egy olyan X ⊆ N2 (G) halmaz, hogy r(X) + c(X + y) nagy. Legyen G egy gráf, y ∈ V (G), r : V → Z+ , r(y) = 1 és f egy fokszámel®írás G-re. Legyen H egy f -szétszedése G-nek, W ⊆ V (H) és u, v ∈ V (H) − W . Azt mondjuk, hogy u és v W -szeparált H -ban, ha u és v H − W különböz® komponenseihez tartozik. Deniáljuk az R1 , R2 , ... ⊆ V (G), S1 , S2 , ... ⊆ V (H) és W0 , W1 , ... ⊆ V (H) halmazsorozatokat a következ®képpen: legyen W0 = {y} és i ≥ 1-re legyen Ri = {v ∈ V (G) : v legalább két része Wi−1 -szeparált H -ban } Si = {vj ∈ V (H) : vj része valamely v ∈ Ri -nek } Wi = Si ∪ Wi−1

A deníciókból következik, hogy Si ∩ Sj = ∅ = Ri ∩ Rj (i 6= j) és Wi = {y} ∪ S1 ∪ S2 ∪ · · · ∪ Si . Vegyük észre, hogy Si = ∅ minden i ≥ 1-re, ha y nem elvágó pontja H -nak.

5.1.7. Lemma. Legyen H egy összefügg® f -szétszedése G-nek. Legyen Z H − Wi−1 komponense valamely i ≥ 1-re, és uv, wx ∈ E(Z). Tegyük fel, hogy Z(uv, wx) összefügg®. Ekkor H 0 = H(uv, wx) összefügg® f -szétszedése G-nek és Sm (H 0 ) = Sm (H) minden 1 ≤ m ≤ i-re.


26

Bizonyítás Mivel H -nak és H 0 -nek ugyanaz a fokszámsorozata, ezért H 0 is egy f szétszedése G-nek. Továbbá H 0 összefügg®, mert H és Z(uv, wx) összefügg®. Azt kell még megmutatnunk, hogy Sm (H 0 ) = Sm (H) minden 1 ≤ m ≤ i-re. Ezt indukcióval látjuk be i-re. Ha i = 1, akkor W0 (H 0 ) = {y} = W0 (H). Mivel Z(uv, wx) összefügg®, R1 (H) = R1 (H 0 ) és így S1 (H) = S1 (H 0 ). Most tegyük fel, hogy i ≥ 2. Az indukció miatt Sm (H 0 ) = Sm (H) minden 1 ≤ mß − 1-re. Vegyük észre, hogy H − Wm egy Z 0 komponense tartalmazza Z -t és Z 0 (uv, wx) összefügg®, mivel Z(uv, wx) összefügg®. Tehát Wi−1 (H 0 ) = Wi−1 (H). Mivel Z(uv, wx) összefügg®, Ri (H) = Ri (H 0 ) és így Si (H) = Si (H 0 ). El®ször arra a speciális esetre mondjuk ki a tételt, amikor a G gráf hurokmentes és N (G) független halmaz G-ben. Az általános eset azzal az egyszer¶ eljárással következik majd ebb®l a tételb®l, hogy G minden élét egy új ponttal felosztjuk két részre és az r-t kiterjesztjük úgy, hogy r(v) = 1 legyen az új pontokon.

5.1.8. Tétel ([4] Tétel 2.12). Legyen G = (V, E) egy hurokmentes gráf legalább két éllel és legyen r : V → Z+ . Tegyük fel, hogy N (G) a pontok egy független halmaza G-ben. Ekkor G-nek van egy nem-szeparálható r-pontszétszedése akkor és csak akkor, ha (i) G kétszeresen élösszefügg® (ii) d(v) ≥ 2r(v) minden v ∈ V -re, és (iii) d(X, V −X) ≥ r(X)+c(X +y)−1 minden y ∈ N1 (G, r)-re és X ⊆ N2 (G, r)-re Bizonyítás Csak a szükségességet bizonyítjuk. Tegyük fel, hogy H egy nem-szeparálható r-szétszedése G-nek. Ekkor H kétszeresen élösszefügg® és mivel a pontszétszedés m¶velet nem növelheti az élösszefügg®séget, az (i) teljesül. Mivel H -ban minden pontnak legalább kett® a fokszáma, (ii) szintén teljesül. A (iii) pont pedig következik 2.1.1 tételéb®l, mivel H − y egy összefügg® r|V −y -szétszedése G-nek. Most pedig lássuk az általános esetre kimondott tételt.

5.1.9. Tétel ([4] Tétel 2.1). Legyen G = (V, E) egy gráf, amely legalább két élet tartalmaz, és r : V → Z+ . Ekkor G-nek van egy nem-szeparálható r-pontszétszedése akkor és csak akkor, ha (i) G kétszeresen élösszefügg® (ii) deg(v) ≥ 2r(v) minden v ∈ V -re


27

(iii) i(v) = 0 minden v ∈ N1 (G, r)-re, és (iv) d(X, V − X − y) + i(X) ≥ r(X) + c(X + y) − 1 minden y ∈ N1 (G, r)-re és X ⊆ N2 (G, r)-re. Bizonyítás Legyen G0 az a gráf, amit úgy kapunk, hogy a G gráf minden élét felosztjuk egy ponttal. Ekkor G0 hurokmentes, N (G0 ) = N (G) és N (G0 ) független G0 -ben. Terjesszük ki r-t r0 -vé úgy, hogy r0 (v) = r(v) minden v ∈ V (G) pontra és r0 (v) = 1 minden v ∈ V (G0 ) − V (G) pontra. Ekkor N1 (G0 , r0 ) = N1 (G, r) és N2 (G0 , r0 ) = N2 (G, r). Be kell látnunk, hogy a 5.1.9 tétel feltételei igazak (G, r)-re akkor és csak akkor, ha a 5.1.8 tétel feltételei igazak a (G0 , r0 )-re. Egyértelm¶, hogy a 5.1.9 tétel (i) és (ii) pontjai akkor és csak akkor teljesülnek (G, r)-re, ha a 5.1.8 tétel (i) és (ii) pontjai teljesülnek (G0 , r0 )-re. Továbbá, mivel y ∈ N1 (G, r) = N1 (G0 , r0 ) és X ⊆ N2 (G, r) = N2 (G0 , r0 ), ezért r(X) = r0 (X) és dG (X, V − X − y) + iG (X) − cG (X + y) − iG (y) = dG0 (X, V − X) − cG0 (X + y). Ha a 5.1.9 tétel (iii) és (iv) pontja teljesül (G, r)-re, akkor eG (y) = 0 és emiatt a 5.1.8 tétel (iii) pontja teljesül (G0 , r0 )re. Most tegyük fel, hogy a 5.1.8 tétel (iii) pontja teljesül (G0 , r0 )-re. Ha X = ∅, akkor cG0 (y) ≤ 1 minden y ∈ N1 (G0 , r0 )-re és így iG (y) = 0 minden y ∈ N1 (G, r)-re. Ekkor a 5.1.9 tétel (iii) pontja teljesül (G, r)-re, és az el®bbi egyenl®ségeket felhasználva a 5.1.9 tétel (iv) pontja szintén teljesül (G, r)-re. A következ®kben a fokszámel®írt esetet fogjuk vizsgálni, azaz, hogy mik azok a szükséges és elégséges feltételek ahhoz, hogy egy G gráfnak legyen egy nemszeparálható f -szétszedése. Egy G = (V, E) gráfra és X ⊆ V (G)-re legyen Γ(X) azon V − X -beli pontok halmaza, amelyek szomszédosak X pontjaival. Legyenek x, y, z ∈ V (G) és xz ∈ E(G). Ekkor G(xz → yz) = G − xz + yz .

5.1.10. Lemma. Legyen G = (V, E) egy nem-szeparálható gráf és legyenek x, y ∈ V (G) különböz®ek. Legyenek xz1 , xz2 , ..., xzt a G − y gráf különböz® élei, t ≥ 3.

Ekkor G(xzi → yzi ) szeparálható minden 1 ≤ i ≤ t-re akkor és csak akkor, ha G − {x, y}-nak léteznek olyan különböz® C1 , C2 , ..., Ct komponensei, hogy zi ∈ V (Ci ) és d(x, Ci ) = 1 minden 1 ≤ i ≤ t-re.

5.1.11. Következmény. Legyen G = (V, E) egy nem-szeparálható gráf és legyenek x, y ∈ V (G) különböz®ek. Legyenek xz1 , xz2 , ..., xzt a G − y gráf különböz® élei, t ≥ 3. Ha t ≥ deg(y) − i({x, y}) + 1, akkor G(xzi → yzi ) nem-szeparálható valamely 1 ≤ i ≤ t-re

Bizonyítás Indirekt tegyük fel, hogy G(xzi → yzi ) szeparálható minden 1 ≤ i ≤ t-re. Ekkor a 5.1.10 lemma miatt c({x, y}) ≥ t. Mivel t ≥ deg(y) − i({x, y}) + 1, ezért


28

d(C, y) = 0 a G − {x, y} gráf valamely C komponenseire. Így x egy elvágó pont G-ben, ami ellentmond annak, hogy G nem-szeparálható.

5.1.12. Következmény. Legyen G = (V, E) egy nem-szeparálható gráf és legyenek x, y, w ∈ V (G) olyan különböz® pontok, melyekre deg(x) ≥ 3 és xy, xw 6∈ E(G).

Ekkor létezik egy olyan z ∈ Γ(x), hogy G(xz → yz) vagy G(xz → wz) nemszeparálható.

5.1.13. Lemma. Legyen G = (V, E) egy nem-szeparálható gráf. Tegyük fel, hogy c({x, y}) = deg(x) ≥ 3 valamely x, y ∈ V (G)-re. Legyen w a G − {x, y} gráf egy C komponensének olyan pontja, hogy d(w, y) = d(w, x) = 0 és legyen z ∈ Γ(x) − C . Ekkor G(xz → wz)(wz 0 → yz 0 ) nem szeparálható valamely z 0 ∈ Γ(w)-re, vagy

minden él, ami illeszkedik w-re G-ben egy elvágóél C -ben. A 5.1.9 tételhez hasonlóan el®ször azt az esetet vizsgáljuk, amikor G hurokmentes és N (G) független.

5.1.14. Tétel ([4] Tétel 2.23). Legyen G = (V, E) egy hurokmentes gráf legalább v két éllel, legyen r : V → Z+ és legyen f egy r-fokszámel®írás, ahol f (v) = (f1v , f2v , ..., fr(v) ) v minden v ∈ V -re. Tegyük fel, hogy N (G) független. Ekkor és f1v ≥ f2v ≥ · · · ≥ fr(v) G-nek van egy nem-szeparálható f -pontszétszedése akkor és csak akkor, ha

(i) G kétszeresen élösszefügg® (ii) fiv ≥ 2 minden v ∈ V -re és 1 ≤ i ≤ r(v) (iii) d(X + v, V − X − v) − f1v ≥ r(X + v) + c(X + v) − 2 minden v ∈ N (G)-re és X ⊆ N2 (G, r) − v -re. Bizonyítás Csak a szükségességet bizonyítjuk. Tegyük fel, hogy G-nek van egy H nem-szeparálható f -szétszedése. Az (i) és (ii) feltételek triviálisan teljesülnek G-re. Legyen v ∈ N (G) és X ⊆ N2 (G, r) − v . Legyenek C1 , C2 , ..., Cc a G − (X + v) komponensei, ahol c = c(X + v), és legyen Ci0 az a részgráf H -ban, amelyet a Ci pontjainak részei állítanak el®. Legyen v1 az a része v -nek, melynek fokszáma f1v . Legyen S az a halmaz, amely tartalmazza X összes pontjának részeit és a v pont v1 -t®l különböz® részeit. Ekkor |S| = r(X + v) − 1. Mivel G hurokmentes és N (G) független, H -ban d(X +v, V −X −v)−f1v él fut S pontjai és a C10 , C20 , ..., Cc0 részgráfok között. Mivel H nem-szeparálható, ezért H − v1 összefügg® és így d(X + v, V − X − v) − f1v ≥ c + r(X + v) − 2. Tehát (iii) teljesül G-re. Most nézzük az általános esetet.


29

5.1.15. Tétel ([4] Tétel 2.2). Legyen G = (V, E) egy gráf, amely legalább két élet v tartalmaz, r : V → Z+ , és legyen f egy r-fokszámel®írás, ahol f (v) = (f1v , f2v , ..., fr(v) ) v v v és f1 ≥ f2 ≥ · · · ≥ fr(v) minden v ∈ V -re. Ekkor G-nek van egy nem-szeparálható f -pontszétszedése akkor és csak akkor, ha

(i) G kétszeresen élösszefügg® (ii) fiv ≥ 2 minden v ∈ V -re és 1 ≤ i ≤ r(v) (iii) d(X + v, V − X − v) + i(X + v) − f1v ≥ r(X + v) + c(X + v) − 2 minden v ∈ N (G)-re és X ⊆ N2 (G, r) − v -re. Bizonyítás Legyen G0 = (V 0 , E 0 ) az a gráf, amit úgy kapunk, hogy G minden élét felosztjuk egy ponttal. Ekkor G0 hurokmentes, N (G0 ) = N (G) és N (G0 ) független. Legyen r0 és f 0 olyan, hogy r0 (v) = r(v) és f 0 (v) = f (v) minden v ∈ V (G)-re, és r0 (v) = 1 és f 0 (v) = 2 minden v ∈ V 0 − V -re. Ekkor N1 (G0 , r0 ) = N1 (G, r) és N2 (G0 , r0 ) = N2 (G, r). Meg kell mutatnunk, hogy a 5.1.15 tétel (i), (ii) és (iii) feltételei akkor és csak akkor teljesülnek (G, r, f )-re, ha a 5.1.14 tétel (i), (ii) és (iii) feltételei teljesülnek G0 , r0 , f 0 -re. Nyilvánvaló, hogy a 5.1.15 tétel (i) és (ii) feltételei akkor és csak akkor teljesülnek (G, r, f )-re, ha a 5.1.14 tétel (i) és (ii) feltételei teljesülnek G0 , r0 , f 0 -re. Továbbá v ∈ N (G) = N (G0 )-re és X ⊆ N2 (G, r) = N2 (G0 , r0 )0 re f1v = f1v , r(X) = r0 (X) és dG (X + v, V − X − v) + i(X + v) − cG (X + v) = dG0 (X + v, V − X − v) − cG0 (X + v). Így tehát a 5.1.15 tétel (iii) feltétele akkor és csak akkor teljesül (G, r, f )-re, ha a 5.1.14 tétel (iii) feltétele teljesül G0 , r0 , f 0 -re.

5.2.

Néhány következmény

Az els® következmény Euler tételét terjeszti ki.

5.2.1. Következmény. Legyen G = (V, E) egy kétszeresen élösszefügg® gráf és r : V → Z+ olyan, hogy deg(v) ≥ 2r(v) minden v ∈ V -re és r(v) ≥ 2 minden v ∈ N (G). v Legyen f egy r-fokszámel®írás, ahol f (v) = (f1v , f2v , ..., fr(v) ) és 2 ≤ fiv ≤ d deg(v) e− 2 r(v) + 2 minden v ∈ V -re és 1 ≤ i ≤ r(v)-re. Ekkor G-nek van egy nem-szeparálható f -pontszétszedése.


30

5.1. ábra. Euler-sétát tartalmazó gráf

5.2. ábra. Euler-sétát tartalmazó gráf egy pontszétszedése

Az alábbi következmény a nem-szeparálható gráfok fokszámsorozatát jellemzi.

5.2.2. Következmény. Legyen d1 ≥ d2 ≥ · · · ≥ dn ≥ 2 egészek (n ≥ 2). Ekkor létezik egy nem-szeparálható gráf (d1 , d2 , ..., dn ) fokszámsorozattal akkor és csak akkor, ha (i) d1 + d2 + · · · + dn páros, és (ii) d1 ≤ d2 + d3 + · · · + dn − 2n + 4. Bizonyítás El®ször a szükségességet bizonyítjuk. Tegyük fel, hogy van egy H nemszeparálható gráf ezzel a fokszámsorozattal, és legyen vi ∈ V (H) foka di minden 1 ≤ i ≤ n. Az (i) pont nyilván teljesül. Mivel H nem-szeparálható, H −v1 összefügg®. Így |E(H − v1 )| ≥ n − 2. Ezért d1 = d(V − v1 , v1 ) ≤ d2 + d3 + · · · + dn − 2n + 4.


31

Az elégségesség bizonyításához alkalmazzuk a 5.1.15 tételt egy olyan G gráfra, n hurok illeszkedik, továbbá r(v) = n amely egyetlen v pontból áll, amire d1 +d2 +···+d 2 és f (v) = (d1 , d2 , ..., dn ). A következ® eredmény arra az esetre vonatkozik, amikor a gráfban csak egy pontot akarunk szétszedni.

5.2.3. Következmény. Legyen G = (V, E) egy gráf, u ∈ V és r : V → Z+ olyan, hogy r(u) = m ≥ 2 és r(v) = 1 minden v ∈ V − u-re. Legyen f egy r-fokszámel®írás, ahol f (u) = (f1 , f2 , ..., fm ), f1 ≥ f2 ≥ · · · ≥ fm ≥ 2 és f (v) = deg(v) minden v ∈ V − u-re. Ekkor G-nek van nem-szeparálható f -pontszétszedése akkor és csak akkor, ha (i) G kétszeresen élösszefügg® (ii) i(v) = 0 és c(v) = 1 minden v ∈ V − u-re, (iii) f2 + f3 + · · · + fm ≥ c(u) + i(u) + m − 2, és (iv) d(u, V − v − u) + i(u) ≥ m + c({u, v}) − 1 minden v ∈ V − u-re. Az alábbiakban megmutatjuk, mik azok a szükséges és elégséges feltételek, hogy egy gráfnak legyen egyszer¶ nem-szeparálható r-szétszedése. Ugyanakkor az, hogy adott fokszámsorozathoz mikor van egy gráfnak egyszer¶ nem-szeparálható f -szétszedése nyitott probléma.

5.2.4. Következmény. Legyen G = (V, E) egy gráf és r : V → Z+ . Ekkor G-nek van egyszer¶ nem-szeparálható r-pontszétszedése akkor és csak akkor, ha (i) G kétszeresen élösszefügg®, (ii) deg(v) ≥ 2r(v) minden v ∈ V -re, (iii) d(X, V − X − y) + i(X) ≥ r(X) + c(X + y) − 1 minden y ∈ N1 (G, r) és X ⊆ N2 (G, r), és (iv) i(u) ≤

r(u)(r(u)−1) 2

és d(u, v) ≤ r(u)r(v) minden u, v ∈ V -re.

Egy G = (V, E) gráf k -összefügg®, ha |V | ≥ k + 1 és G − U összefügg® minden U ⊆ V (G), |U | ≤ k − 1-re. Így, ha |V | ≥ 3, akkor G nem-szeparálható akkor és csak akkor, ha G kétszeresen összefügg® és hurokmentes. Az alábbi következmény azt mutatja meg, hogy egy gráfnak mikor van kétszeresen összefügg® r-szétszedése.


32

5.2.5. Következmény. Legyen G = (V, E) egy gráf és r : V → Z+ olyan, hogy r(V ) ≥ 3. Ekkor G-nek van kétszeresen összefügg® r-pontszétszedése akkor és csak

akkor, ha (i) G kétszeresen élösszefügg®, (ii) deg(v) ≥ 2r(v) minden v ∈ V -re, (iii) d(X, V − X − y) + i(X) ≥ r(X) + c(X + y) − 1 minden y ∈ N1 (G, r) és X ⊆ N2 (G, r)-re. Elképzelhet®, hogy ez a következmény kiterjeszthet® k -élösszefügg®ségre, az alábbi sejtés alapján

Sejtés: Legyen k ≥ 2 egész, G = (V, E) egy gráf és r : V → Z+ olyan, hogy r(V ) ≥ k + 1. Ekkor G-nek van k -összefügg® r-pontszétszedése akkor és csak akkor, ha (i) G kétszeresen élösszefügg®, (ii) deg(v) ≥ kr(v) minden v ∈ V -re, (iii) G − y -nek van (k − r(y))-összefügg® r|V −y -pontszétszedése minden y ∈ V r(y) ≤ k − 1-re.

Irodalomjegyzék [1] Alex R. Berg, Bill Jackson, Tibor Jordán, Highly edge-connected detachments of graphs and digraphs, J. Graph Theory 43: 67-77, 2003 [2] Satoru Iwata, Tibor Jordán, Orientations and detachments of graphs with prescribed degrees and connectivity, Proc. 5th Hungarian-Japanese symposium on discrete mathematics and its applications, Sendai , April 2007, pp. 149-153 [3] Hong-Jian Lai, Yanting Liang, Ping Li, Jinquan Xu, Degree sequences and graphs with disjoint spanning trees, Discrete Applied Mathematics 159 (2011) 1447-1452 [4] Bill Jackson, Tibor Jordán, Non-separable detachments of graphs, Journal of Combinatorial Theory, Series B 87 (2003) 17-37 [5] C. St. J. A. Nash-Williams, Detachments of graphs and generalized Euler trails, J. London Math. Soc., Vol. 31, 1985, pp. 17-29

33

Többszörösen összefügg gráfok pontszétszedései

Recommend Documents