Description
Absztrakt:
Egy gráf t-szívós, ha tetszőleges S ponthalmazt elhagyva legfeljebb |S|/t
komponensre eshet szét a gráf. Egy gráf szívóssági számán a legnagyobb
olyan t számot értjük, amelyre a gráf t-szívós. Egy gráfot minimálisan
t-szívósnak nevezünk, ha a szívóssági száma t, de bármely élt elhagyva a
szívóssági szám csökken. Az előadás alapjául Kriesell egy sejtése szolgál,
mely szerint minden minimálisan 1-szívós gráfnak van másodfokú csúcsa;
ezen kívül pedig még a minimálisan szívós gráfok felismerhetőségével is
foglalkozunk.