The distance between two vertices in a graph is the length of the shortest path connecting the vertices. Determining the distance between a pair of vertices in a graph is known to be solvable in polynomial time [Dijkstra (1959), Floyd and Warshall (1962)]. Since then, many distance-related problems have arisen the years.

I am currently working on three problems connected to the distance notion. First, in the degree/diameter problem, we maximize the order of a graph given its maximum degree and diameter. By metric dimension, the position of a vertex in a graph is uniquely determined using distances. And with distance-magic labeling, we generalize the well-known magic labeling notion through distances.

The diameter of a graph G is the greatest distance between two vertices in G. Considering three parameters in a graph: order, degree, and diameter, we can optimize one parameter while fixing the other two parameters. Among three optimization possibilities, maximizing the order of the graph given its maximum degree and diameter is one problem that has attracted many researchers since first introduced by Moore, Hoffman, and Singleton in 1960. A natural upper bound for the maximum order is known due to Moore, and a graph whose order attains such a bound is called a Moore graph.

Unfortunately, or maybe fortunately for the sake of further research, there only exist very few Moore graphs. So researchers usually try to construct larger graphs and prove the non-existence or otherwise of graphs whose order misses the Moore bound by a small number of vertices. A more detailed explanation of this problem can be found in Combinatorics Wiki, and a comprehensive survey by my two Ph.D. supervisors: Mirka Miller and Jozef Siran, can be downloaded in the Electronic Journal of Combinatorics.

In this area of research, we have contributed several results: proving the non-existence of graphs of maximum degree 4 with order two less than the Moore bound and constructing larger graphs for more restricted versions of the degree/diameter problem (i.e., graphs embeddable in fixed surfaces and bipartite Cayley graphs).

With the motivation to uniquely identify the location of each vertex in a graph, the notion of metric dimension was introduced separately by Peter Slater (1975) and Frank Harary and Robert Melter (1976). They called an ordered set of vertices S resolves a graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G, dim(G), is the minimum cardinality of a resolving set of G. Determining the metric dimension of an arbitrary graph has been proved to be NP-hard [Garey and Johnson (1979)]. So research in this area is then constrained towards characterizing graphs with particular metric dimensions, determining metric dimensions of particular graphs, and constructing algorithms that best approximate metric dimensions. Our research has contributed results in the first two topics. Robert Bailey and Peter Cameron have written a nice survey on this problem; you can download the preprint or published version of the paper (subscription needed).

One of the hurdles in the metric dimension concept is that the resolving set should be ordered. In 2017, we introduced the multiset dimension, where we consider a set S m-resolves a graph G if every vertex is uniquely determined by its multiset of distances to the vertices in S. However, with this variation, it is possible for a graph to not have an m-resolving set; in this case to have an infinite dimension. In 2019, Reynaldo Gil-Pons, Yunior Ramíres-Cruz, Rolando Trujillo-Rasua, and Ismael Yero fixed this hurdle by considering only vertices outside S uniquely determined and called this concept the outer multiset dimension.

Vilfred (1994) defined distance-magic labeling of a graph G as labeling of vertices in G by consecutive integers from 1 up to the order of G such that the summation of all labels of a vertex’s neighbors (i.e., vertices of distance one) is independent of the choice of the vertex. In a way, this labeling can be viewed as a natural extension of previously known graph labelings: magic labeling [Sedlacek (1963), Kotzig and Rosa (1970)] and radio labeling (which is distance-based) [Griggs and Yeh (1992)]. A short survey of this labeling type can be found in Section 5.5 of Joe Gallian’s dynamic survey of graph labeling. In addition, O’Neal and Slater (2012) have generalized the notion of distance-magic labeling by considering the summation for labels of all vertices with particular distances to the vertex under consideration, not only its neighbors.