Graphs and Games: the Mathematics of Richard Nowakowski (Part III) Org: Nancy Clarke (Acadia University)
[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.