CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Convexity and Metric Graph Theory II
Org: José Cáceres (Universidad de Almería, Almería (Spain))

MITRE DOURADO, Universidade Federal do Rio de Janeiro
Complexity aspects of graph convexity  [PDF]

In this talk we discuss characterizations, bounds, polynomial time algorithms, and NP-hardness results in some graph convexities concerning the determination of the parameters hull number, geodetic number, and convexity number for general graphs and some graph classes. The considered convexities are those in which the convex sets are defined by shortest paths, induced paths, paths of length three, Steiner sets, and alliances.

MORTEN NIELSEN, Thompson Rivers University
Helly theorems for convex sets in graphs  [PDF]

For a family $\mathcal{C}$ of vertex subsets of a graph, the \emph{Helly number} $h(\mathcal{C})$ is the smallest $h$ such that every $h$-wise intersecting subfamily $\mathcal{C'}$ of $\mathcal{C}$ has non-empty intersection.

With {\em convexity} defined in various ways, we determine $h(\mathcal{C})$ for the family $\mathcal{C}$ of all convex sets in a graph (belonging to two important classes).

Our motivation is Helly's Theorem that the convex sets in $\mathcal{R}^n$ have Helly number $n+1$.

ORTRUD R OELLERMANN, (with M. Nielsen), University of Winnipeg
Separation Properties for 3-Steiner and 3-Monophonic Convexity in Graphs  [PDF]

Let $(V,~M)$ be a convexity; $M$ is a family of convex subsets of $V$. An $X \in M$ is a halfspace if $V-X \in M$. A convexity has separation property (i) $S_3$ if every convex set $X$ and point $v \in V-X$ belong to complementary half spaces; (ii) $S_4$ if every pair of disjoint convex sets belong to complementary halfspaces. Characterizations of graphs with properties $S_3$ and $S_4$ relative to two graph convexities are given.

IGNACIO M PELAYO, Universitat Politècnica de Catalunya, Barcelona, Spain
Dominating location in graphs  [PDF]

A dominating set $S=\{u_1,\ldots,u_k\}$ of a graph $G$ is locating dominating if every vertex $v$ is uniquely determined by the k-vector $(d(v,u_1),\ldots, d(v,u_k))$. If moreover, every vertex $v$ not in $S$ is also uniquely determined by the set of neighbors of $v$ belonging to $S$, then it is called locating-dominating. In this talk, we present our more significant contributions on both minimum locating dominating and locating-dominating sets, concerning extreme values, realization theorems and Cartesian products.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria