Számítástudományi és Információelméleti Tanszék

Különböző gráfelméleti és gyakorlati alkalmazások kapcsán gyakran felmerül, hogy mennyire robusztus egy gráf, azaz ha elhagyjuk valamilyen részét, néhány pontját vagy élét, akkor hány és milyen komponensre esik a gráf. Például számítógéphólázatoknál, ha meghibásodik a rendszer egy része, mennyire marad működőképes a maradék rendszer. A robusztusság mérésére többféle módszer ismeretes, a két legismertebb a többszörös összefüggőség és a szívósság (toughness). A kutatás célja további ismereteket szerezni a különböző mérőszámok összefüggéseiről, kapcsolatukról a faktorokkal, Hamilton-körrel. Megvizsgálni, kiterjeszthetők-e ezek a definíciók hipergáfokra is.

Egy gráf k-szorosan összefüggő, ha akárhogyan is hagyunk el a gráfból k-nál kevesebb pontot, még összefüggő marad.  Viszont k pont elhagyásával már akár nagyon sok komponensre eshet a gráf. Ennek a problémának a kezelésére született a szívós (tough) gráfok definíciója. Egy gráf t-szívós, ha akárhogyan is hagyunk el S ponthalmazt a gráfból nem esik több komponensre mint |S| / t .  Rögtön adódik, hogy egy t-szívós gráf 2t-szeresen összefüggő. Vannak más hasonló definíciók is. Különböző alkalmazásokban más változatok bizonyultak hasznosnak. Érdekes volna felderíteni ezek közötti pontos kapcsolatokat.

A szívósság legelőször a Hamilton körök elméletében merült fel. Ugyanis világos, hogy ha egy gráfban van Hamilton kör, akkor 1-szívós. Fordítva ez nem igaz, viszont hosszú ideje megoldatlan kérdése Chvátalnak, hogy van-e olyan t, amire igaz, hogy minden t-szívós gráfban van Hamilton-kör. Sokáig élt az a feltételezés, hogy létezik ilyen t, sőt t=2.  Néhány évvel ezelőtt azonban született egy konstrukció: olyan gráfot adtak, melyben nincs Hamilton-kör, viszont közel 9/4-szívós.  Ebből következik, hogy t >= 9/4, ha létezik egyátalán.  Hasznos lenne megjavítani ezt a konstrukciót. Ennek egyik nehézsége, hogy be kell látni, hogy a konstruált gráfban nincs Hamilton-kör. Ennek bizonyításához volna szükség valami új ötletre.

Munkanyelv: angol.