Graf $G$ o $2^n$ wierzchołkach nazwiemy grafem otwarcie (domknięcie) XOR-magicznym, jeśli jest spójny i istnieje bijekcja ze zbioru wierzchołków grafu $G$ w zbiór ciągów binarnych długości $n$ taka, że dla każdego wierzchołka tego grafu, suma etykiet wierzchołków w jego otwartym (domkniętym) sąsiedztwie jest równa wektorowi zerowemu.

W jednej z prac dotyczących tego tematu, Batal badał problem istnienia regularnych grafów XOR-magicznych. W szczególności, postawił on problem otwarty: czy istnieje graf nieparzyście (parzyście) regularny graf otwarcie (domknięcie) XOR-magiczny?

W trakcie referatu odpowiemy pozytywnie na wyżej wymieniony problem, pokazując istnienie takich grafów rzędu $2^n$ dla każdego $n$ większego od 3. Ponadto, przedstawimy warunek konieczny (w nurcie spektralnej teorii grafów) istnienia grafów otwarcie XOR-magicznych wraz z jego zastosowaniami do wybranych grafów Cayleya.

Współautorki: Sylwia Cichacz, Rita Zuazua