# Discrete math seminar

Title: Linear Algebra Miniatures

Speaker: Stefan Bard, University of Victoria

Date and time:
30 Mar 2015,
10:00am -
11:00am

Location: Maclaurin D105

Read full description

Stefan will present more sections from the book “Linear Algebra Miniatures”.

Title: Linear programming results for broadcast domination and multipacking

Speaker: Frank Yang, University of Victoria

Date and time:
23 Mar 2015,
10:00am -
11:00am

Location: MacLaurin D105

Read full description

Frank Yang will talk about *Linear programming results for broadcast domination and multipacking*, which is part of his Master’s thesis.

Title: Eternal Problems on Graphs

Speaker: William F. Klostermeyer, School of Computing, University of North Florida

Date and time:
16 Mar 2015,
10:00am -
11:00am

Location: MacLaurin D105

Read full description

Abstract:

Eternal problems in graphs concern the perpetual, dynamic maintenance of some configuration or property of a graph while an adversary attempts to destroy the configuration/property. For example, the eternal domination problem involves the placement of mobile guards on the vertices of a graph whose goal is to protect its vertices or edges against a sequence of attacks. This problem has its historical roots in the military strategy of Roman Emperor Constantine (a.k.a. Constantine The Great, 274-337 AD).

The problems explored in this talk aim to defend the vertices, or the edges, of a graph from an infinite sequence of attacks by an adversary. For example, in the eternal domination problem, we are interested in the minimum number of guards needed to defend the graph from any such sequence of attacks at vertices, as well as algorithmic strategies for moving the guards to successfully defend the graph. To defend an attack at an unguarded vertex, a guard must be sent from a neighboring vertex. Variations on this problem are discussed including the eviction model in which attacks occur at vertices with guards.

Results surveyed in this presentation compare the associated protection parameters with well-known graph parameters such as the domination number, independence number, chromatic number, and vertex cover number. A number of open problems and conjectures are presented.

Title: The 4/5 Upper Bound on the Game Total Domination Number

Speaker: Michael A. Henning, University of Johannesburg

Date and time:
12 Mar 2015,
10:00am -
11:00am

Location: MacLaurin D015

Read full description

Abstract: In this talk, we study the total domination game. This game is played on a graph $G$ by two players, named Dominator and Staller. They alternately take turns choosing vertices of $G$ such that each chosen vertex totally dominates at least one vertex not totally dominated by the vertices previously chosen. Dominator's goal is to totally dominate the graph as fast as possible, and Staller wishes to delay the process as much as possible. The game total domination number, $\gamma_{tg}(G)$, of $G$ is the number of vertices chosen when Dominator starts the game and both players play optimally. The Staller-start game total domination number, $\gamma_{tg}'(G)$, of $G$ is the number of vertices chosen when Staller starts the game and both players play optimally. We present a key lemma, known as the Total Continuation Principle, to compare the Dominator-start total domination game and the Staller-start total domination game. We show that if $G$ is a graph on $n$ vertices in which every component contains at least three vertices, then $\gamma_{tg}(G) \le 4n/5$ and $\gamma_{tg}'(G) \le (4n+2)/5$. As a consequence of this result, we obtain upper bounds for both games played on any forest that has no isolated vertices.

Title: Homomorphisms and colourings of signed graphs

Speaker: Edita Rollova, University of Western Bohemia in Pilsen, Czech. Republic

Date and time:
09 Mar 2015,
10:00am -
11:00am

Location:

Read full description

Title: Linear Algebra Miniatures

Speaker: Stefan Bard, University of Victoria

Date and time:
02 Mar 2015,
10:00am -
11:00am

Location: MacLaurin D105

Read full description

Stefan Bard will tell us about couple more sections from the book Linear Algebra Miniatures by Jiri Matuzak

Title: Some duality theorems on graph switching

Speaker: Jing Huang, University of Victoria

Date and time:
24 Feb 2015,
10:00am -
11:00am

Location: Maclaurin D105

Read full description