• CARMA DISCRETE MATHEMATICS SEMINAR
  • Speaker: Sudeep Stephen, The University of Newcastle
  • Title: The Forcing Number of Graphs with Given Girth
  • Location: Room VG25, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 3:00 pm, Mon, 14th Nov 2016
  • Abstract:

    For a two-coloring of the vertex set of a simple graph $G$ consider the following color-change rule: a red vertex is converted to blue if it is the only red neighbor of some blue vertex. A vertex set $S$ is called zero-forcing if, starting with the vertices in $S$ blue and the vertices in the complement $V \setminus S$ red, all the vertices can be converted to blue by repeatedly applying the color-change rule. The minimum cardinality of a zero-forcing set for the graph $G$ is called the zero-forcing number of $G$, denoted by $Z(G)$.

    There is a conjecture connecting zero forcing number, minimum degree $d$ and girth $g$ as follows: "If G is a graph with girth $g \geq 3$ and minimum degree $d \geq 2$, then $Z(G) \geq d+ (d-2)(g-3)$".

    I shall discuss a recent paper where the conjecture is proved to be true for all graphs with girth \leq 10.

  • [Permanent link]