CanaDAM 2017
Ryerson University, June 12 - 16, 2017

Graphs and Games: the Mathematics of Richard Nowakowski (Part III)
Org: Nancy Clarke (Acadia University)

ART FINBOW, Saint Mary's University
Extendable Vertices in Well-Covered Graphs  [PDF]

A graph $G$ is said to be {\it well-covered} if every maximal independent set of vertices in $G$ has the same cardinality. A vertex $v$ in a well-covered graph $G$ is said to be {\it extendable} provided both (1) $G – v$ is well-covered and (2) the independence numbers of $G$ and $G – v$ are equal. We present both a survey of results regarding such vertices and some extensions of this idea. \par This work is joint with various sets of coauthors, the union of which includes {\bf R. Nowakowski}, B. Hartnell, M. D. Plummer and C. Whitehead.

BERT HARTNELL, Saint Mary's University
Parity Dissociation Graphs  [PDF]

Finding the dissociation number of an arbitrary graph (the cardinality of the largest set of vertices in an induced subgraph of maximum degree one) is difficult. If one is given a graph in which every maximal such set of vertices is maximum (in the spirit of well-covered graphs) then it is straight forward. Recent work has characterized graphs with this property that have girth 7 or more. Here we illustrate attempts to tighten the girth restriction as well as looking at a broader collection, those graphs in which every maximal dissociation set is of the same parity.

JEANNETTE JANSSEN, Dalhousie University
An application of Hall's theorem to linear embeddings of graphs  [PDF]

Given a graph of order n, and any set of n locations on the real line, what is the best embedding of the vertices of G into these locations, so that the sum of squares of the distances of adjacent vertices is minimized? If the graph in question has a clear linear structure, i.e. is a proper interval graph, does the optimal embedding follows the natural ordering of the vertices? We give an affirmative answer for a special class of interval graphs, where the proof involves an application of Hall's theorem. Joint work with Nauzer Kalyaniwalla and Islay Wright.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Ryerson University Office of Naval Research Science and Technology