You are here

1-relaxed modular edge-sum labeling game number

Hang Do*, Linfield college (Undergraduate Student)
Brent Moran, University of Colorado Denver (Undergraduate Student)
Timothy Singer, Linfield College (Undergraduate Student)
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: 
Talk Type: 
Oral Presentation
Friday, March 13, 2015 - 10:30