|
|||||
The Metric Dimension of a Graph and its Variants - Part I
Org: Shonda Dueck (University of Winnipeg)
[PDF]
Org: Shonda Dueck (University of Winnipeg)
[PDF]
- FLORENT FOUCAUD, University Clermont Auvergne, France
Bounds on the order of a graph of given metric dimension and diameter: studies for standard graph classes [PDF]
-
It is easily seen that any graph of metric dimension $k$ and diameter $D$ has at most $D^k+k$ vertices. This is almost never reached for general $k$ and $D$; a tight bound (still exponential) was derived by Hernando, Mora, Pelayo, Seara and Wood in 2011. However, for many graph classes, a polynomial bound holds. We discuss such bounds for trees, interval graphs, permutation graphs, planar graphs, etc. One of the tools that is helpful here is the notion of distance-$V$-$C$ dimension. Joint work with Laurent Beaudou, Peter Dankelmann, Michael Henning, Arnaud Mary, George Mertzios, Reza Naserasr, Aline Parreau, Petru Valicov.
- DOROTA KUZIAK, Universidad de Cadiz, Spain
The strong metric dimension of a graph [PDF]
-
A vertex $w$ strongly resolves a pair $u, v$ of vertices of a connected graph $G$ if there exists some shortest $w-u$ path containing $v$ or some shortest $w-v$ path containing $u$. A set $S$ of vertices is a strong metric generator for $G$ if every pair of vertices of $G$ is strongly resolved by some vertex of $S$. The smallest cardinality of a strong metric generator for $G$ is the strong metric dimension of $G$. We shall present exact values or sharp bounds for the strong metric dimension of cactus graphs and some product graphs.
- TERO LAIHONEN, Turku University, Finland
On Vertices Belonging to Every Metric Basis [PDF]
-
A set $S\subseteq V(G)$ is a resolving set in a graph $G$ if for any pair $u,v\in V(G)$ there exists $s\in S$ such that $d(u,s)\neq d(v,s)$. A metric basis is a resolving set of the smallest possible cardinality. It is known that there are graphs where some vertices must belong to every metric basis. We call these vertices basis forced vertices. In this talk, we give, for example, bounds on the size of a graph with $k$ basis forced vertices.
This is a joint work with Anni Hakanen, Ville Junnila and Ismael Yero.
- ELIZABETH MARITZ, University of the Free State, South Africa
On the partition dimension of circulant graphs [PDF]
-
Let $\Pi = \{ S_1, S_2, \dots , S_k \}$ be an ordered partition of the vertex set $V(G)$ of a~graph $G$. The partition representation of a vertex $v \in V(G)$ with respect to $\Pi$ is the $k$-tuple $r(v|\Pi)=(d(v, S_1), d(v, S_2), \dots , d(v, S_k))$. If every pair of distinct vertices have distinct partition representations with respect to $\Pi$, then $\Pi$ is a resolving partition for $G$. The cardinality of a smallest resolving partition of $G$ is called the partition dimension of $G$. We present exact values and bounds on the partition dimension for undirected and directed circulant graphs.
- ISMAEL GONZALEZ YERO, Universidad de Cadiz, Spain
Comparing the metric and edge metric dimensions of graphs [PDF]
-
Given a connected graph $G$, the cardinality of a smallest set of vertices that uniquely identifies all the (vertices or edges, resp.) of $G$, through a vector of distances to such set of vertices, is the (metric or edge metric, resp.) dimension of $G$.
We shall present in this talk some comparisons between metric and edge metric dimension of graphs. Specifically, that for every $r,t\ge 2$, with $r\ne t$, there is $n_0$, such that for every $n\ge n_0$ there exists a graph $G$ of order $n$ with metric dimension $r$ and edge metric dimension $t$.