Hi Simon!

I know of two papers that give examples of the graphs that you are looking for. The first is 'On k-dimensional graphs and their bases' by Buczkowski, Chartrand, Poisson & Zhang. The second is 'Unique basis graphs' by Bagheri, Jannesari & Omoomi. Hope that helps :)

James

Hi James i saw theorems related to Unique basis graphs but not any example. If you find any one , kindly share it.

Hi Simon! I'll describe the construction from the second paper. Take two sets W = { w_0,w_1,...,w_{k-1}} and U = {u_0,u_1,...,u_{2^k-1}}. The vertex set of our graph is the union of U and W, so the order is k+2^k. The graph is a split graph, with U inducing a clique and W an independent set.

The only thing left to specify is the edges between U and W. With each vertex u_j of U we associate the length-k vector that gives the binary expansion of j. Then we join u_j and w_i if the i-th entry of u_j is one.

This raises the question of finding the smallest graph with metric dimension k and a unique basis. I'm not aware that anyone has looked at that.

All the best,

James

SIMON RAJ F James Tuite

A non-trivial graph with a unique metric basis is the complete graph on four vertices, also known as the K₄ graph.

The K₄ graph consists of four vertices, where each vertex is connected to every other vertex by an edge. It can be visualized as a square with diagonals.

To define a metric basis, we need to specify a set of edges that form a basis for the metric space on the graph. A basis for a metric space is a set of edges such that every other edge in the graph can be expressed as the sum of basis elements with non-negative coefficients.

In the case of the K₄ graph, we can choose the following set of edges as a metric basis:

1. The edge connecting vertex 1 to vertex 2.

2. The edge connecting vertex 2 to vertex 3.

3. The edge connecting vertex 3 to vertex 4.

With these three edges as a basis, we can express any other edge in the graph as a combination of these basis elements. For example, the edge connecting vertex 1 to vertex 3 can be expressed as (1/2) * (1-2) + (1/2) * (2-3) = (1/2) * (1-3), which is a non-negative combination of the basis elements.

It is important to note that the choice of the metric basis is not unique for most graphs. However, in the case of the K₄ graph, the basis described above is unique because the graph is small and simple. In larger and more complex graphs, it becomes increasingly likely that multiple metric bases exist.

Hope it helps: Partial credit to AI

Hi Mohammad! I'm not sure that this definition matches what Simon specified in the question. For metric dimension we have to choose a set of vertices and the vertices of the graph must be distinguished by their distances to the chosen vertices. So K_n will have metric dimension n-1.

A back of the envelope calculation shows that the construction that I described above, upon setting k = 2, gives a smallest graph with a unique basis, i.e. with order 6. The graph is K_4 plus two non-adjacent vertices that each have two neighbours in the K_4, one of these neighbours being a common neighbour. So in a sense that graph is the simplest example.

Does that indicate that the 2^k+k construction is in general very small for graphs with metric dimension k and a unique basis? Interesting...

James

My colleague Grahame Erskine informs me that the smallest graph (or graphs?) with metric dimension three and a unique basis has nine vertices. So 2^k+k is not best possible.

Hi James , can you please send the image of that graph?. Is there any non-Trivial graph G (other than Complete graph Kn) satisfying K+d^k = Size (G) =n and dim(G)

Here is a quick sketch of the simplest one :) Does this work for you?

The two degree two vertices :)

Yes . Thank you James. that was a wonderful Example.

Glad to help :)