Vertex-primitive graphs with two vertices having almost the same neighbourhood

Question

Hypothesis: Let $\Gamma$ be a vertex-primitive graph with two vertices $u$ and $v$ such that $$|N(u) \cap N(v)|=|N(v)|-1$$

Question: Is it true that $\Gamma$ must either be a complete graph or have prime order?

---

Terminology and notation:

• By $N(v)$, I mean the set of neighbours of $v$ in $\Gamma$.

• By vertex-primitive, I mean that the automorphism group acts primitively on the vertices. In other words, the automorphism group does not preserve any partition of the vertex-set apart from the trivial ones (into singletons or with just one part).

---

Comments:

• It is easy to see that a vertex-primitive graph with two distinct vertices having the same neighbourhood must be edgeless. From this perspective, the question is thus about the first non-trivial case.

• Complete graphs clearly satisfy the hypothesis.

• There are indeed non-complete graphs (of prime order) satisfying the hypothesis. For example, cycles of prime order. More generally, let $p\geq 5$ be a prime, let $i\in\{2,3,\ldots,\frac{p-1}{2}\}$ and let $S=\{\pm i, \pm (i+1),\ldots, \pm(\frac{p-1}{2})\}$. Then the Cayley graph $\mathrm{Cay}(\mathbb{Z}_p,S)$ is easily seen to satisfy the hypothesis (with $u=0$ and $v=1$, for example).

• In fact, computer calculations show that there are no counterexamples up to order $100$, say.

Answer 1

Pablo Spiga found a proof a few weeks ago. Together, we then proved a slightly more general result which is now on the arxiv: http://arxiv.org/abs/1501.05046

It is more general in two ways: it deals with digraphs rather than graphs, and it gives some information in general when two vertices have neighbourhoods differing by say $k$, although we only get a complete classification of the graphs when $k=1$, which was the original question. (This is Corollary 4.2.)

Answer 2

Here is a partial solution. If the vertices $u$ and $v$ in the statement of the problem are neighbors, I claim that the graph must be complete. Here is my argument:

Let $D = N(u) \cap N(v)$ so by hypothesis, there is exactly one point in $N(v)$ that is not in $D$. Since I am assuming that $u \in N(v)$ and we know that $u \not\in D$, it must be that $N(v) = D \cup \{u\}$. Now suppose the graph is not complete so there exists a point $x$ not in $N(u)$ and different from $u$. Then $x \not\in D$ and thus $x$ is not in $N(v)$, and certainly, $x$ is different from $v$ since it is not a neighbor of $u$. Also, by the symmetry of the assumption, nothing is changed if we swap $u$ and $v$.

Now let us say that an edge is "good" if it is an image of the edge joining $u$ and $v$ under the automorphism group of the graph. By the primitivity assumption, the graph is connected by good edges. We showed that a vertex $x$ different from $u$ and not connected to $u$ is also different from $v$ and not connected to $v$, and thus $x$ has the same property with respect to any vertex that can be reached from $u$ by a chain of good edges. But this is a contradiction since $x$ can reached. This proves my claim