Cospectrality and dimension of graphs

Question

Firstly, I apologize if the question is long. I appreciate any helpful answers and ideas.

In the following all graphs are simple and connected.

Let $G$ be graph with vertex set $V=\left\{v_1,v_2,\ldots,v_n\right\}$ and $W=\left\{w_1,w_2,\ldots,w_k\right\}$ be a ordered subset of $V$. For a vertex $v\in V$, define $r(v,W)=(d(v,w_1),d(v,w_2),\ldots,d(v,w_k))$, where $d(x,y)$ represents the distance between the vertex $x$ and $y$. The set $W$ is a resolving set for $G$ if for every two vertices $v_i,v_j\in V$, we have $r(v_i,W)\neq r(v_j,W).$

A resolving set containing a minimum number of vertices is called a basis for $G$ and the number of vertices in a basis is its dimension, $dim(G).$ A graph $G$ is $D$-dimensional , if and only if $dim(G)=D.$

We say two graphs $G_1$ and $G_2$ are cospectral with respect to adjacency (laplacian) matrix if the spectrum of these two matrices be identical, and we write it by $spec(G_1)=spec(G_2).$

After long definitions, my questions are:

$1)$ What are the smallest (with respect to the number of vertices) cospectral graphs that have same dimension?

$2)$ What are the smallest (with respect to the number of vertices) cospectral graphs that have different dimension?

$3)$ Is it true that, for every $k\in N$ there are two graphs $G_1$ and $G_2$ such that we have $spec(G_1)=spec(G_2)$ and $|dim(G_1)-dim(G_2)|\geq k.$

In my opinion, the Shrikhande graph and its cospectral mate $L(K_{4,4})$ can be a good options for answering the above questions. But until now, I did not find good results.

I add this note, since I need a program in Magma or GAP or Maple language to compute the dimension of a simple graph. Are there any such program with acceptable complexity? But any program for this computation is helpful for me.

Thanks, if you wind up my long notes.

Answer 1

I found the answers of the questions $(1)$ and $(2)$ and also an approach for the the third question. Also, I will introduce a software such that it is very good for finding the dimension of arbitrary graphs.

Answer of question $(1)$: The two below graphs$,G_1$ and $G_2,$ are the smallest pairs which are cospectral and also have same dimension.

The spectrum of these graphs are: $\{-1.90321,(-1)^2,0.19394,1,2.70928\},$

The dimension of these two graphs are: $dim(G_1)=dim(G_2)=2$.

Answer of question $(2)$:The two below graphs, left graph is $H_1$ and right graph is $H_2$, are the smallest regular pairs which are cospectral and have different dimension.

The spectrum of these graphs are: $\{-2.56155,(-1)^6,1.56155,3,4\},$

The dimension of these two graphs are: $dim(H_1)=4$ and $dim(H_2)=3$.

I used the program $Dimension-Metrica$ for computing the dimension of graphs. This is a java based program with good GUI. Also, I wrote a $Maple$ program to check the minimality of graphs that is wanted in the question.

For third question, I tried to solve it by $Schwenk's$ method that allow us to construct infinite pairs of cospectral trees. But, as I checked it until now and I believe it is true in general, all these cospectral mates have same dimension. In contrast, I believe the third question is true in general. One approach for solving this question is finding a relation between graph products, such as Cartesian product or strong product, and the dimension of resulting graph based on dimension of its components in product.