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

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).

• 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.

• Any cycle of order $n\geq 5$ satisfies the requirement that there are $u,v \in V(C)$ such that $|N(u)\cap N(v)| = |N(v)|-1$: Let $\Gamma = (\{1,\ldots,n\}, E)$ where $E = \{\{k, k+1\} : 1 \leq k < n\}$ \cup $\{\{1,n\}\}$. Then pick $u=1, k=3$. So we don't need the order $n$ to be prime. - Or did I misunderstand your notion of ''order''? – Dominic van der Zypen Nov 10 '14 at 13:55
• Right, any cycle satisfies the second part of the hypothesis, but the only cycles that are vertex-primitive are the ones of prime order. – verret Nov 10 '14 at 14:00
• +1 - great question. Except that when I saw the title, I thought "oh, if anyone can answer that it will be verret..." :-) – Nick Gill Nov 11 '14 at 15:33
• Nick, graphs with two-transitive groups are not too interesting, as for your second question, if $u$ is adjacent to $v$, then the transposition $(uv)$ is in the group of the graph and so it is the symmetric group and we fall back into your first case. – Gordon Royle Nov 12 '14 at 1:19
• @Nick : In that case $u$ and $v$ must have the same neighbours apart from each other. – Brendan McKay Nov 12 '14 at 23:22

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.)
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