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.

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