Skip to main content
1 of 2
Shahrooz
  • 4.8k
  • 1
  • 24
  • 36

Cospectrality and dimension of graphs

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.

Thanks, if you wind up my long notes.

Shahrooz
  • 4.8k
  • 1
  • 24
  • 36