Egy gráfelméleti problémáról

Corrádi, Keresztély (1965) Egy gráfelméleti problémáról. A MAGYAR TUDOMÁNYOS AKADÉMIA MATEMATIKAI ÉS FIZIKAI TUDOMÁNYOK OSZTÁLYÁNAK KÖZLEMÉNYEI, 15 (2). pp. 89-96.

Preview

Text cut_MATFIZ_15_2_1965_pp89_-_96.pdf - Published Version Download (333kB) | Preview

Abstract

E dolgozatban gráfon véges, többszörös élet és hurkot nem tartalmazó gráfot értünk. A G gráf szögpontjainak számát T(G)-vel, éleinek számát E(G)-vel jelöljük. HA H⊆G a G gráf egy részgráfja, E(G; H) jelöli G azon élei számát, amelyek H-beli szögpontokból indulnak ki. Jegyezzük meg, hogy e jelölésben a H-beli szögpontokat összekötő élek kétszer számítandóak. Szükségünk lesz a továbbiakban az alábbi jelölésmódra is: ha P ∈ G a G gráf egy tetszőleges szögpontja, akkor az E(G; P) kifejezés a P szögpontból kiinduló G-beli élek számát jelenti. Világos, hogy tetszőleges H⊆G G-beli részgráf esetén E(G; H) = ∑P∈H E(G; P) igaz az előbbiekben mondottak alapján. Állapodjunk meg végül abban, hogy a G gráf részgráfjainak egy rendszerét függetlennek fogjuk mondani, ha bármely két e rendszerhez tartozó részgráf közös szögpont nélküli. Bebizonyítjuk, hogy a fenti jelölések használata mellett áll az alábbi Tétel: Legyen G véges gráf, s legyenek n és k adott természetes számok. Tegyük fel, hogy T(G) = kn, továbbá, hogy minden P ∈ G szögpont esetén E(G; P) < n. Ekkor létezik egy S természetes szám, valamint G-beli A₁, A₂, ..., Aₛ részgráfok egy független rendszere azzal a tulajdonsággal, hogy T(Aᵢ) = k, (l ≦ i ≦ s) továbbá az Aᵢ részgráfok bármelyikében tetszőleges két szögpont között G-ben nem halad él. Az S természetes szám választható az S ≧ max (½ n, k/2(k - 1)n - ½) egyenlőtlenséget kielégítőnek. Az S maximális választása esetén a tétel feltételeit kielégítő részgráfok rendszerét a 3. és 4. §-ban rövidség kedvéért megengedett rendszernek fogjuk nevezni. A tétel k = 2 esetén azt jelenti, hogy minden 2n szögpontú G gráfot, amelyben minden szögpont foka n-nél kisebb, szét lehet bontani szögpont-párokra oly módon, hogy az egy párhoz tartozó szögpontok között nem halad G-ben él. Ez Dirac tétele. A tétel az alábbi problémával kapcsolatban merül fel. König Dénes „Theorie der endlichen und unendlichen Graphen" c. könyvében szerepel az alábbi állítás: Ha G véges gráf, minden szögpontjának foka kisebb mint n, akkor létezik G-ben legfeljebb n részgráfból álló független rendszer, amely G minden szögpontját tartalmazza, s azzal a tulajdonsággal rendelkezik, hogy e rendszer egyetlen részgráfja sem tartalmaz G-beli élet. Kérdés, lehet-e valamit mondani e független részgráfrendszer részgráfjainak szögpont-számáróí? Talán igaz az itt következő sejtés: Ha G véges gráf és T(G) = kn + r, 0 ≦ r < n, k, n természetes számok, r nem negatív egész, s minden P ∈ G-re igaz az E(G; P) < n egyenlőtlenség, akkor létezik az A₁, A₂, ..., Aₙ részgráfok egy független rendszere G-ben azzal a tulajdonsággal, hogy G minden szögpontja hozzátartozik e részgráfok valamelyikéhez, T(Aᵢ) = {k + 1, ha l ≦ i ≦ r, k, ha r + l ≦ i ≦ n, s végül az Aᵢ(l ≦ i ≦ n) részgráfok egyike sem tartalmaz G-beli élet. E sejtést Erdős Pál mondotta ki. Megmutatjuk, hogy elég lenne a sejtést az r = 0 és k > n esetre igazolni. Tegyük fel tehát, hogy G véges gráf, amelyre a T(G) = kn, k > n egyenlőség és az E(G; P) < n, egyenlőtlenség minden P ∈ G szögpontra igaz. Erre a G gráfra igaznak tételezzük fel a sejtés konklúzióját. Legyen most H tetszőleges véges gráf, amelyre a sejtés feltételei igazak, megmutatjuk hogy konklúziója is igaz. Evégből legyen T(H) = ln + r, 0 ≦ r < n. Válasszuk meg а k természetes számot úgy, hogy k > max (l + 1, n) teljesüljön. Jelöljön Sₙ egy n-szögpontú teljes gráfot. (Sₙ bármely két pontja éllel van összekötve.) Csatoljunk az Sₙ gráfból k — l— 1 példányt, s az Sₙ₋ᵣ gráfból egy példányt a H gráfhoz. A kapott G gráfra T(G) = T(H) + (k - l - 1)n + n - r = kn, k > n. Ha a H szögpontjaiból az új szögpontokhoz nem rajzolunk be éleket, akkor teljesül a E(G; P) < n feltétel is minden G-beli P szögpont esetén. G-re a sejtés konklúziója igaz. Van tehát G-ben egy B₁, B₂, ..., Bₙ független rendszer a kívánt tulajdonságokkal. Minden Bᵢ az Sₙ minden példányából pontosan egy szögpontot tartalmaz, s a Bᵢ-k közül n — r darab tartalmazza Sₙ₋ᵣ-nek egy szögpontját. Nevezetesen a Bᵢ részgráfok egyike sem tartalmaz G-beli élet, s így Sₙ-ből nem tartalmazhat legalább két szögpontot. Ha a Bᵢ, (l ≦ i ≦ n) részgráfokból elhagyjuk azokat a szögpontokat, amelyek nem H-hoz tartoznak, s a megmaradó H-beli részgráfokat Aᵢ-vel (l ≦ i ≦ n) jelöljük, akkor a T(Bᵢ) = k (l ≦ i ≦ n) feltétel teljesülése folytán az indexezés megfelelő választásával T(Aᵢ) = {l + 1, ha l ≦ i ≦ r, l, ha r + l ≦ i ≦ n, adódik, s igy a sejtés konklúziója a H gráfra is igaz. Ezt akartuk megmutatni. Az r = 0 esetben a sejtés azt mondja, hogy G-ben T(G) = kn esetén létezik a sejtés konklúzióját kielégítő n-darab független k szögpontú részgráf. A dolgozat tétele azt mondja, hogy legalább ½n darab van. A tétel bizonyítására két lemmára lesz szükség. Előbb ezeket fogalmazzuk meg és bizonyítjuk be.

Actions (login required)

Edit Item