|
|||||
The Metric Dimension of a Graph and its Variants - Part II
Org: Shonda Dueck (University of Winnipeg)
[PDF]
Org: Shonda Dueck (University of Winnipeg)
[PDF]
- SHONDA DUECK, University of Winnipeg, Canada
Logarithmic bounds on the threshold strong dimension of a graph [PDF]
-
A set $W$ of vertices of a connected graph $G$ is a strong resolving set for $G$ if, for every pair of vertices, one of the vertices in the pair lies on a shortest path from the other vertex to some vertex of $W$. The smallest cardinality of a strong resolving set of vertices of $G$ is the strong dimension of $G$. The threshold strong dimension of $G$ is the smallest strong dimension among all graphs having $G$ as a spanning subgraph. We establish logarithmic bounds on the threshold strong dimension for graphs in general, and for trees.
- LINDA EROH, University of Wisconsin, Oshkosh Campus, USA
The threshold strong dimension of trees [PDF]
-
The cardinality of a smallest set that strongly resolves every pair of vertices in $G$ is the strong dimension $\beta_s(G)$ of $G$. The threshold strong dimension $\tau_s(G)$ of $G$ is the smallest strong dimension among all graphs having $G$ as a spanning subgraph.
We show that trees with strong dimension $3$ or $4$ have threshold strong dimension $2$. Oellermann et al observed $\tau(K_{1,6}) > 2$. Since $\beta_s(K_{1,6})=5$ and $\tau(K_{1,6}) \le \tau_s(K_{1,6})$, the threshold strong dimension of trees with strong dimension $5$ need not be $2$. We observe there are trees of arbitrarily large dimension with threshold strong dimension 2.
- BETH NOVICK, Clemson University, USA
A geometric characterization of the threshold strong dimension of a graph [PDF]
-
The threshold strong dimension of a graph $G$, denoted $\tau_S(G)$, is the smallest strong dimension among all graphs having $G$ as a spanning subgraph. We give a geometric characterization of the threshold strong dimension. It expresses $\tau_S(G)$ in terms of the smallest number of paths (each of sufficiently large order) whose strong product admits a certain type of embedding of $G$. This characterization leads to several results. This is joint work with Nadia Benakli, Novi H. Bong, Shonda Dueck (Gosselin), Linda Eroh, and Ortrud Oellermann.
- RICHARD TILLQUIST, University of Colorado, USA
A Bound on the Metric Dimension of Hamming Graphs and Applications in Machine Learning [PDF]
-
Many powerful data analysis and data mining techniques require that data be embedded in Euclidean space. When faced with symbolic datasets, including biological sequence data produced by high-throughput sequencing assays, it is not always clear how to generate an effective embedding. In this talk, we discuss low-dimensional representations of symbolic information based on metric dimension. Specifically, we consider an upper bound on the metric dimension of Hamming graphs and how this bound can be used to map biological sequences of arbitrary length to real space.