# Uniqueness of graph neighbourhood sizes

I was thinking about graphs the other day, and had the following questions which I suppose fall under the topic of graph reconstruction. I am not very familiar with the literature, so in case this has been studied before, I'd appreciate any pointers.

Suppose we have a finite vector $\vec{n} \in \mathbb{N}^d$ with $\vec{n} = (n_1, n_2, ..., n_d)$, and a connected graph $G$ with the property that for any vertex $v \in V(G)$ and any $i \in [d]$, there are exactly $n_i$ vertices in $V(G)$ at distance $i$ from $v$.

Question 1: Must such a graph $G$ be vertex-transitive?

Another question I had was whether such graphs are uniquely determined (up to isomorphism, of course) by the sequence $\vec{n}$. That is, can there be two non-isomorphic graphs $G$ and $H$ that give rise to the same vector $\vec{n}$?

If $\max_i n_i \le 2$, then it is pretty straightforward to check that $G$ is determined uniquely. However, a friend pointed out that the sequence $\vec{n} = (3,2)$ is realised by both $K_{3,3}$ and $K_6 \setminus C_6$. Is this example sporadic, or can one find infinitely many vectors corresponding to non-isomorphic graphs?

Question 2: Are there infinitely many vectors $\vec{n}$ that can be realised by non-isomorphic graphs?

Finally, these thoughts on graphs arose by considering the sequence $n_i = \binom{d}{i}$, which is realised by the hypercube $Q_d = \{0,1\}^d$, where vertices are adjacent if they differ in exactly one coordinate. I would be interested to know if there are other graphs that give rise to this particular sequence.

Question 3: Is the hypercube $Q_d$ the only graph corresponding to the sequence $(\binom{d}{i})_{i \in [d]}$?

Any thoughts would be appreciated!

## 1 Answer

Q1. Put your $K_6\setminus C_6$ next to $K_{3,3}$ and connect each node to a partner in the other half:

This graph produces $\vec n=(4,7)$, but is not vertex-transitive, because each node in $K_6\setminus C_6$ is part of a triangle, and the ones in $K_{3,3,}$ aren't.

Q2. We can repeat the above construction with $p$ copies of $K_6\setminus C_6$ and $q$ copies of $K_{3,3}$, connected by six $K_{p+q}$ networks. As long as $p,q \ge 1$ the graph will give $\vec n=(p+q+2, 5(p+q)-3)$, but the results are not isomorphic because they contain different numbers of triangles, namely $\binom{p+q}3 + 2p$.

• Thanks for the quick answer, and nice constructions! I imagine Q3 will be too esoteric to attract much interest. Commented Jun 18, 2016 at 10:43
• @Shagnik: Q3 looks hard more than esoteric. It is not generally a good idea to ask multiple different questions in one post, because the site mechanics are based on the assumption that there will be one best/correct answer; it does not handle a situation well where several answers answer different parts of the question. Commented Jun 18, 2016 at 10:53
• That's a fair point, but the questions were pretty closely related, and I didn't want to spam with very similar questions. I was also more interested in getting an answer to the two you solved, and I figured they would stand or fall together! Commented Jun 18, 2016 at 15:34