6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The famous cospectral mates with six vertices is the answer for one of questions $(1)$ or $(2)$. It seems that their dimension are equal. $\endgroup$ – Shahrooz Janbaz Sep 23 '13 at 19:38
1
$\begingroup$

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.

enter image description here

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.

enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.