Madarasi Péter: Új megközelítés a gráfizomorfiához

Az előadáson ismertetünk egy gráfizomorfia invariánst, amelyet felhasználva a gráfokhoz jól kezelhető "fingerprint" generálható izomorfia invariáns módon. Bebizonyítjuk,  hogy a fingerprintek több gráfpárt különböztetnek meg, mint a sajátalterek bizonyos izomorfia invariáns tulajdonságai. Megmutatjuk, hogy a fingerprint egyértelműen azonosítja a "friendly" gráfokat, a fákat és a 3-összefüggő síkgráfokat. Végül igazoljuk, hogy a k-összefüggő gráfok fingerprintjei különböznek a nem k-összefüggő gráfokétól, ahol k konstans.