Data: 05/04/2017

Título: Zero Forcing
Palestrante: Dieter Rautenbach, Ulm University, Germany
Local: UFF, Campus GRAGOATÁ
Sala: 407, Bloco H, 4o. andar
Horário: 16h

Resumo: A set $Z$ of vertices of a graph $G$ is a zero forcing set of $G$ if initially labeling all vertices in $Z$ with $1$ and all remaining vertices of $G$ with $0$, and then, iteratively and as long as possible, changing the label of some vertex $u$ from $0$ to $1$ if $u$ is the only neighbor with label $0$ of some vertex with label $1$, results in the entire vertex set of $G$. The zero forcing number $Z(G)$, defined as the minimum order of a zero forcing set of $G$, was proposed as an upper bound of the corank of matrices associated with $G$, and was also considered in connection with quantum physics and logic circuits. In view of the computational hardness of the zero forcing number, upper and lower bounds are of interest. We discuss such bounds and some of the corresponding extremal graphs.

Observações: This is joint work with M. Gentner, L.D. Penso, and U.S. Souza.

Confira aqui a apresentação