Minimálisan 1-szívós gráfok minimális fokszámai
A dolgozatban szívós gráfokkal foglalkozunk. Egy G gráf t-szívós, ha tetszőleges S elvágó ponthalmaz esetén S-t elhagyva a gráf legfeljebb |S|/t részre esik szét, ahol t pozitív valós szám. A definícióból könnyen láthatóan következik, hogy egy t-szívós gráf mindig 2t-szeresen összefüggő, viszont ez fordítva nem feltétlenül igaz. Látható, hogy minél több éle van egy gráfnak, annál nagyobb lesz az összefüggőségi és szívóssági számuk is, ezért érdemes vizsgálni, mit lehet tudni azon gráfokról, amiből bármely élet elhagyva csökken az összefüggőségi illetve szívóssági számuk, azaz minimálisan k-összefüggőek illetve minimálisan t-szívósak. Mader belátta, hogy egy minimálisan k-szorosan összefüggő gráfnak van k-adfokú csúcsa. Ennek analógiájaként Kriesell megfogalmazta a következő sejtést: minden minimálisan 1-szívós gráf tartalmaz másodfokú pontot.
A dolgozatban először áttekintünk néhány szívóssággal kapcsolatos ismert tételt, majd konstruálunk tetszőlegesen nagy nemtriviális minimálisan 1-szívós gráfokat. Kriesell sejtéséről eddig nem ismert semmilyen eredmény, még olyan sem, amiben valamely gyengébb felső korlátot adnának a minimális fokszámra. Belátjuk, hogy minden minimálisan 1-szívós gráfnak van legfeljebb (n/3 + 3)-adfokú csúcsa. Végül néhány érdekes összefüggést vizsgálunk a karommentes gráfok szívósságáról, és bebizonyítjuk, hogy a minimálisan 1-szívós karommentes gráfok kizárólag a körök, így Kriesell sejtése ebben az esetben nyilvánvalóan fennáll.
Hivatkozások:
D. Bauer, H. Broersma, E. Schmeichel, Toughness in Graphs - A Survey, Graphs and Combinatorics, 22 (2006) 1-35.
W. Mader, Eine Eigenschaft der Atome endlicher Graphen, Arch. Math., 22 (1971) 333-336.
T. Kaiser, Problems from the workshop on dominating cycles, http://iti.zcu.cz/history/2003/Hajek/problems/hajek-problems.ps
szerző
-
Varga Kitti
matematikus
nappali
konzulens
-
Dr. Katona Gyula
egyetemi docens, Számítástudományi és Információelméleti Tanszék
