Seminarium Kombinatoryka, Teoria Grafów i Zbiorów Uporządkowanych
Wydział Matematyki i Nauk Informacyjnych, Politechnika Warszawska
Kalendarz Środy, 10:15-11:45
Pinezka Gmach MiNI PW, Sala 431, ul. Koszykowa 75, Warszawa
Komputer Seminaria odbywają się stacjonarnie z transmisją na platformie MS Teams.
Mail Jeśli chcesz dołączyć do spotkania, to napisz do sekretarza seminarium.

Najbliższy referat
28.10.2026 Ahmet Batal Izmir Institute of Technology
Algebraic characterizations of generating and affinely generating \(\Gamma\)-magic maps and \(\Gamma\)-distance magic labelings on regular graphs
\(\quad\)For a finite abelian group \(\Gamma\), a \(\Gamma\)-magic map on a graph \(G\) is a map \(f\colon V(G)\to\Gamma\) with constant open-neighborhood sums. It is generating if its labels generate \(\Gamma\), and affinely generating if their pairwise differences generate \(\Gamma\). Let \(G\) be regular and write \(\Gamma\cong\bigoplus_{i=1}^{r}\mathbb{Z}/d_i\mathbb{Z},\quad d_1\mid\cdots\mid d_r,\quad B_{\Gamma}=\bigoplus_{i=1}^{r-1}\mathbb{Z}/d_i\mathbb{Z},\) with \(B_{\Gamma}=\{0\}\) when \(r=1\). Let \(\overline A_m\) be the endomorphism induced by adjacency on \((\mathbb{Z}/m\mathbb{Z})^{V(G)}\) modulo constant vectors. We prove that \(G\) admits generating and affinely generating \(\Gamma\)-magic maps if and only if, respectively, \(B_{\Gamma}\hookrightarrow\ker\overline A_{d_r}\qquad\text{and}\qquad\Gamma\hookrightarrow\ker\overline A_{d_r}.\) When \(|V(G)|=|\Gamma|\), a bijective \(\Gamma\)-magic map, called a \(\Gamma\)-distance magic labeling, exists precisely when the latter embedding has an image that separates every pair of distinct vertices by a coordinate difference. If the integral reduced adjacency operator is nonsingular over \(\mathbb{Q}\), the first two criteria become subgroup conditions in its cokernel. A graph of order \(n\) is distance magic if it admits a bijection from its vertex set to \(\{1,\ldots,n\}\) with constant open-neighborhood sums. Cichacz and Froncek conjectured that every such graph is \(\Gamma\)-distance magic for every abelian group \(\Gamma\) of order \(n\). We use these characterizations to disprove this conjecture by constructing a \(6\)-regular distance magic graph of order \(27\) with no affinely generating \((\mathbb{Z}/3\mathbb{Z})^3\)-magic map. For Cayley graphs on elementary abelian \(p\)-groups, the same characterizations yield a nonexistence result which, combined with a known sufficient condition, shows that a \(\Gamma\)-distance magic labeling exists over some abelian group \(\Gamma\) of the graph order if and only if the regularity is divisible by \(p\).
Zespół prowadzący