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

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

ROBERT BAILEY, University of Regina
A matrix method for resolving sets in Johnson graphs  [PDF]

A {\em resolving set} for a graph $G$ is a subset of vertices with the property that the list of distances from a vertex to the chosen set uniquely identifies that vertex. The {\em metric dimension} of $G$ is the smallest size of a resolving set.

In this talk, we use incidence matrices of set systems to obtain resolving sets for the Johnson graph $J(n,k)$, and show how some interesting combinatorial objects can be used.

JOSÉ CÁCERES, Universidad de Almería, Almería (Spain)
Metric dimension in infinite but locally finite graphs  [PDF]

We present some results about the metric dimension in infinite but locally finite graph. Necessary conditions for these graphs to have a finite metric dimension are given, as well as a characterization of infinite trees with finite metric dimension. We also establish some results about the metric dimension of some cartesian product involving infinite graphs. Finally, we describe the actual state of this problem.

ALBERTO MÁRQUEZ, University of Seville (Spain)
Some question about metric dimension of some families of graphs  [PDF]

The metric dimension of graph has been studied since the works of Slater (1975) and Harary-Melter (1976). We focuss in some of the problem we are working within that subject. Namely, we shall show that the metric dimension of some important families of graphs as Kneser graphs and Johnson graphs are related with some other problems as partial geometries or surface tilings. Additionally, we try to find how many different bases can a graph have.

MERCÈ MORA, Universitat Politècnica de Catalunya
Geodetic and hull numbers in strong product graphs  [PDF]

Classical convexity can be extended in a natural way to graphs by considering shortest paths. Geodetic and hull sets play an important role in this approach. In this talk I will present some results concerning geodetic and hull sets. More concretely, we prove upper and lower tight bounds of the geodetic and hull numbers of strong product graphs. We give also exact values for some concrete families of strong product graphs.

MICHAEL YOUNG, Iowa State University
Disjoint Homometric Sets in Graphs  [PDF]

Two subsets of vertices in a graph are called $homometric$ if the multisets of distances determined by each set are the same. Let $h(n)$ denote the largest number $h$ such that any connected graph of $n$ vertices contains two disjoint homometric subsets of size $h$. This talk will cover bounds of $h$, as well as other results about disjoint homometric sets.

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