Nowhere $0\mathrm{mod}p$ Dominating Sets in Multigraphs

Abstract

Let $G$ be a graph with integral edge weights. A function $d:V(G)\to {\mathbb{Z}}_p$ is called a nowhere $0\mathrm{mod}p$ domination function if each $v\in V$ satisfies $(\sum _{u\in N(v)}w(u,v)d(u))\ne 0\mathrm{mod}p$, where $w(u,v)$ denotes the weight of the edge $(u,v)$ and $N(v)$ is the neighborhood of $v$. The subset of vertices with $d(v)\ne 0$ is called a nowhere $0\mathrm{mod}p$ dominating set. It is known that every graph has a nowhere $0\mathrm{mod}2$ dominating set. It is known to be false for all other primes $p$. The problem is open for all odd $p$ in case all weights are one.

In this paper, we prove that every unicyclic graph (a graph containing at most one cycle) has a nowhere $0\mathrm{mod}p$ dominating set for all $p>1$. In fact, for trees and cycles with any integral edge weights, or for any other unicyclic graph with no edge weight of $(-1)\mathrm{mod}p$, there is a nowhere $0\mathrm{mod}p$ domination function $d$ taking only $0-1$ values. This is the first nontrivial infinite family of graphs for which this property is established. We also determine the minimal graphs for which there does not exist a $0\mathrm{mod}p$ dominating set for all $p>1$ in both the general case and the $0-1$ case.