Nemes Bernadett: Szoros irányított gráfok direkt szorzata

Egy C irányított gráfot nevezzünk injektívnek, ha tetszőleges A, B véges irányított gráfok esetén A^C és B^C gráfok izomorfiájából következik A és B izomorfiája. Nem injektív összefüggő véges gráfokra példák a páros gráfok, és ezek természetes általánosításai, az úgynevezett nem szoros gráfok. Egyéb példát nem ismerünk, így felmerül a kérdés, hogy véges összefüggő gráfok között az injektívek megegyeznek-e a szorosakkal.

Mivel az injektív gráfok zártak a direkt szorzásra, a fenti sejtést tesztelendő érdemes megvizsgálni, hogy összefüggő szoros gráfok direkt szorzata szükségképpen szoros-e. Ezt a problémát javaslatunkra kitűzték a 2025-ös Schweitzer versenyen.