Convexity and Metric Graph Theory II
Org:
José Cáceres (Universidad de Almería, Almería (Spain))
[
PDF]
 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 NPhardness 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 nonempty 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 3Steiner and 3Monophonic 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 $VX \in M$. A convexity has separation property (i) $S_3$ if every convex set $X$ and point $v \in VX$ 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 kvector $(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 locatingdominating. In this talk, we present our more significant contributions on both minimum locating dominating and locatingdominating sets, concerning extreme values, realization theorems and Cartesian products.
Handling of online submissions has been provided by the CMS.