Do different graphs exist for these vertex distances?

Question

Good day,

I was trying to learn and gain better understanding of the structure of graphs in general. I have a puzzle which tells me only distances between vertices and asks me for the graph which fits to them.

The puzzle gives a graph specification by a multiset matrix of distances, one multiset for each vertex in the (connected) graph. Each multiset contains all distances between the corresponding vertex $v$ of the multiset to all other vertices $v' \neq v$. In order to facilitate notation, the multisets are compressed with tuple notation. The $i$-th element (with $i\in \{1,..,|V|\}$) in a tuple gives the number of distances of length $i$ in the graph which are based on a corresponding vertex. E.g.: $(2,3,1)$ stands for $\{1,1,2,2,2,3\}$ as distances. The distance tuples are labeled to verify the solution more easily and to verify that the solution has been understood by the creator because the labels have to be mapped to the vertices in the solution.

This is the problem instance:

[4x] $a := (2,2,3,2,2,1)$

[2x] $b := (2,2,2,3,2,1)$

[1x] $c := (2,4,4,2)$

[4x] $d := (2,3,3,3,1)$

[2x] $e := (3,3,4,2)$

Now the task: find all graphs satisifying all distance constraints.

This is the only solution I could come up with: one graph which fulfills the conditions

Other tries missed the derived degree sequence or the labeling of vertices.

My question is: Is the given matrix of distances isomorphic to the depicted graph i.e. is there only one graph (ignoring the labels) which satisfy the distances or can one find another different graph?

And basically: Which different (non-isomorphic) connected graphs are known to share the same distance matrix? Maybe you can give me some suggestions for further information about the matter.

Thank you for reading.

EDIT: I have also a puzzle for a disconnected graph:

[4x] $a := (3)$

[6x] $b := (2,1)$

[4x] $c := (1,2)$

[2x] $d := (1,1,1)$

The question would be, is there a graph isomorphic to these constraints? Or do exist multiple different graphs which satisfy the puzzle? My approach is, that $(1,1,1)$ is a unique tree and both instances can only exist together with twice $(2,1)$. A component using $(1,2)$ exactly requires $(3)$ once. This disallows a complete component consisting of 4 times $(3)$ or a component consisting of 4 times $(2,1)$ for the residual problem:

[4x] $a := (3)$

[4x] $b := (2,1)$

[4x] $c := (1,2)$

Since each tuple can be given to components by a natural number of times, the $(3)$ must be divided into 1x $(3)$, 1x $(3)$ and 2x $(3)$ for each of the remaining three components (3 components because we only have components of always 4 vertices and 12 vertices remain). Partitioning it that way - so that 2 components only have $(3)$ once - is according to the fact, that a component can maximally have 3 times $(1,2)$ so that one is left over and a 2nd component must have at least one time $(1,2)$ too. These both components must exactly have the tuple $(3)$ once, not less and more. Because we must give 2 times $(3)$ to the third component, it cannot contain a $(1,2)$ so that there is only the possibility of giving one component 1x $(3)$ + 3x $(1,2)$ (because 1x $(3)$ + 2x $(1,2)$ + 1x $(2,1)$ is invalid) and one other component 1x $(3)$ + 1x $(1,2)$ + 2x $(2,1)$.

So if we know that:

• component 1: 2x $(1,1,1)$ + 2x $(1,2)$
• component 2: 1x $(3)$ + 3x $(1,2)$
• component 3: 1x $(3)$ + 1x $(1,2)$ + 2x $(2,1)$

there are only 4 tuples left, 2x $(3)$ and 2x $(2,1)$ , which are themselves a valid component.

My assumption is, there is only one solution. Is that correct?

More interesting: Do you know a puzzle for disconnected graphs with ambiguous solution?

Answer 1

As you already found out, the distances do not uniquely define the graph. In fact your last example can be modified into one such counter-example, and as an added bonus, this counter-example is quite sparse (unlike your "add-an-all-connecting-node" counter-example).

Graph A consists of:

• One $3$-armed star: $(3) + 3\times (1,2)$ [same as your component 2]

• One square-with-a-diagonal: $2\times (3) + 2\times (2,1)$ [same as your last component]

• One square: $4 \times (2,1)$

Graph B consists of:

• Three copies of triangle-with-an-extra-arm: $3 \times [ (3) + 2\times (2,1) + (1,2) ]$ [same as your component 3]

Each graph is made from $3\times (3) + 6 \times (2,1) + 3 \times (1,2)$.

Basically each of the four connected components is made entirely from the same three types of distance-multisets, i.e. $(3), (1,2), (2,1)$, just in different proportions, so basic linear algebra would say there is a redundant solution.

Answer 2

I made one finding which solves my general question. There are minimal graphs which keep all distances at a minimum which makes them collide very well.

Take two non-isomorphic graphs with equal degree spectrum and add to each of both graphs a vertex which is connected to all vertices of the previous vertex set. This will definitely result in same distance matrices for non-isomorphic graphs. This type of graph can arbitrarily be chained for the same purpose as a blockgraph. It might even work when adding less edges to the new vertex. I can't tell however if there is any class with unique distance matrix (for trees, see below) or if the uniqueness just vanishes with increasing number of vertices in a graph when there is a method to artifically set the distances by adding vertices. My conjecture is that this kind of distance matrix is unique for connected graphs with maximum circle length of $4$. This trick can also be achieved for bipartite graphs if one vertex is added for each colour class or with planar graphs (for examples an 8-vertex graph with circle of length 8 and two further edges). Comparing the distance matrix of two graphs could have a complexity of $\mathcal{O}(n^2\log{n})$ where $n$ is the vertex number of each of both graphs.

Conclusion: For general graphs, the distance matrix invariant is only slightly more expressive than the degree spectrum of a graph.