1-relaxed modular edge-sum labeling game number

Author(s)
Hang
Do
*,
Linfield college
Brent
Moran
,
University of Colorado Denver
Timothy
Singer
,
Linfield College
Talk Abstract
Motivated in part by anti-magic labeling and similar schemes, we introduce a new graph labeling and derive from it a game on graphs called the \emph{1-relaxed modular edge-sum labeling game}.

The players, Alice and Bob, alternate turns with Alice going first. Each turn, the player chooses an unlabeled edge $e$, and assigns to $e$ a label $w(e) \in [n]$. At any point in the game, let $L'$ be the set of labeled edges. For any turn $t$, let $v$ be a vertex for which $N'(v)\cap L' \neq \emptyset$. We define the label for $v$ at this point in the game to be $\ell_t(v)$ according to the following:
\[
\ell_t (v) = \sum_{e\in N'(v)\cap L'} w(e) \pmod{n}.
\]
The defect of $v$ is the number of vertices which are adjacent to $v$ and labeled identically to $v$. We call a labeling \emph{legal} if each labeled vertex has defect at most 1, and we require that the players maintain a legal
labeling at each stage of the game.

Alice wins if play continues until $L' = E(G)$; otherwise, Bob wins. The least $n$ such that Alice has a winning strategy for on $G$ using $[n]$ is called the \emph{1-relaxed modular edge-sum labeling game number of $G$}.

We provide an upper bound for this number on trees, as well as providing the exact value of the number for various classes of graphs.
Talk Subject
Combinatorics
Time Slot
2015-03-13T10:30:00