3-reguláris gráfok minimális levélszámú feszítőfái
Egy összefüggő gráf minimális levélszámú feszítőfájának megtalálása a Hamilton-út probléma egyik legtermészetesebben adódó általánosítása (a minimális levélszám akkor és csak akkor 2, ha a gráfnak van Hamilton-útja), így persze ez a probléma is NP-nehéz. Lu és Ravi [3] azt is megmutatta, hogy a feladatra nem létezik konstans faktorú approximáció sem. A 3-reguláris gráfok Hamilton-köreivel és Hamilton-útjaival kapcsolatos vizsgálatok mindig is az érdeklődés középpontjában álltak, különösen síkgráfok esetén, hiszen Tait sejtéséből (minden 3-reguláris 3-összefüggő síkgráfnak van Hamilton-köre) azonnal következett volna a híres négy szín sejtés. A 3-reguláris gráfok minimális levelű feszítőfáival kapcsolatos legfrissebb eredmények az [1] és [2] cikkekben találhatók. A [2] cikkben Goedgebeur és szerzőtársai bebizonyítják Zoeram és Yaqubi sejtését [4], mely szerint minden összefüggő n csúcsú 3-reguláris gráfnak van legfeljebb n/6+1/3 levelű feszítőfája és megmutatják, hogy ha a gráf ezen felül még 2-összefüggő is, akkor ez 13n/85-re javítható. Megfogalmazzák továbbá azt a sejtést, hogy minden 2-összefüggő n csúcsú 3-reguláris gráfnak van legfeljebb n/10+1 levelű feszítőfája, vagyis a 13/85 érték akár 1/10-re is javítható (ennél tovább viszont már nem, mint ahogy az n/6+1/3-os becslés is éles). Az [1] cikkben (számos egyéb eredmény mellett) Boyd és szerzőtársai megmutatják, hogy minden 2-összefüggő n csúcsú 3-reguláris multigráfnak van legfeljebb n/6+2/3 levelű feszítőfája. A dolgozatban egy korábban nem használt megközelítés segítségével jelentősen megjavítjuk Goedgebeur és szerzőtársai eredményét: megmutatjuk, hogy 2-összefüggő 3-reguláris gráfok esetén a 13/85-ös érték 1/8-ra javítható és egyben új bizonyítást adunk Boyd és szerzőtársai eredményére is. A módszer továbbfejlesztésével nem tűnik elérhetetlennek Goedgebeurék sejtésének igazolása sem.
Irodalom:
[1] S. Boyd, R. Sitters, S. van der Ster, L. Stougie, The traveling salesman problem on cubic and subcubic graphs, Math. Program. A 144
227-245. (2014)
[2] J. Goedgebeur, K. Ozeki, N. van Cleemput, G. Wiener: On the minimum leaf number of cubic graphs, arXiv preprint: arXiv:1806.04451 (2018)
[3] H.-I. Lu and R. Ravi. The power of local optimization: Approximation algorithms for maximum-leaf spanning tree (draft). Technical Report CS-96-05, Department of Computer Science, Brown University, Providence, Rhode Island (1996)
[4] H. G. Zoeram, D. Yaqubi, Spanning k-ended trees of 3-regular connected graphs, Electronic J. of Graph Theory and Applications 5 , 207–211. (2017)
szerző
-
Dücső Márton
Matematikus mesterképzési szak (MSc)
mesterképzés (MA/MSc)
konzulens
-
Dr. Wiener Gábor
egyetemi docens, Számítástudományi és Információelméleti Tanszék