 english accueil réunion accueil canadam

Graphs and Games: the Mathematics of Richard Nowakowski (Part III)
[PDF]

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.