CanaDAM 2013
Memorial University of Newfoundland, June 10 - 13, 2013

Independence Number: Theory and Applications II.
Chair: Ermelinda DeLaVina (University of Houston--Downtown)
Org: Ermelinda DeLaVina (University of Houston--Downtown) and Craig Larson (Virginia Commonwealth University)

JOCHEN HARANT, Technical University of Ilmenau
Packing of isomorphic induced independent subgraphs  [PDF] [SLIDES]

Lower bounds on the independence number $\alpha(G)$ of a graph $G$ are popular topics in research, however, upper bounds have barely been touched in the literature. New upper bounds on $\alpha(G)$ are presented and, moreover, the independence concept is generalized to packing of subgraphs into $G$.

This is joint work with S. Richter and H. Sachs.

BERT HARTNELL, Saint Mary's University
Eternal Domination with Independent Guards  [PDF] [SLIDES]

We consider the problem of monitoring (or dominating) a network by an independent set of guards with an additional dynamic property. If an intruder appears at a node unoccupied by a guard one can move one step to that position to handle the attack while others can either remain fixed or move to adjacent nodes such that the new set of positions for the guards is also independent. Furthermore this process can be repeated (the eternal part). The problem of multiple simultaneous attacks is also briefly considered. This is part of a joint investigation with A. Finbow and K. Mynhardt.

CRAIG LARSON, Virginia Commonwealth University
The Independence Number Project  [PDF] [SLIDES]

The independence number can be computed efficiently for many graph classes, either because they are belong to class of graphs where an efficient algorithm exists (for example, claw-free graphs), or because efficiently computable upper and lower bounds predict the value of this invariant. We discuss a project to extend independence number theory and to find new graph classes where the independence number can be efficiently computed. In particular we identify graphs which are ``difficult'' with respect to existing independence number theory and propose these as motivating problems.

RYAN PEPPER, University of Houston--Downtown
Recent Results on k-independence in graphs  [PDF]

We survey and discuss some recent results on the k-independence number. In particular, how the k-independence number is related to the k-domination number, how the DSI strategy can be used to improve bounds on the k-independence number, and how the k-residue function can be used in certain cases to improve upon all known lower bounds for k-independence.

DOUG RALL, Furman University
On Maximal Independent Sets in Cartesian Products  [PDF] [SLIDES]

A graph is said to be \textit{well-covered} if all of its maximal independent sets have the same cardinality. In this talk we present our preliminary work on the question, ``When is the Cartesian product $G\Box H$ of two graphs $G$ and $H$ well-covered?'' In particular, we prove that if $G\Box H$ is well-covered, then at least one of $G$ or $H$ is well-covered. This answers a question of Topp and Volkmann posed in 1992.

This is joint work with Bert Hartnell.

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 Memorial University of Newfoundland