Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ we set $N(v)=\{w\in V:\{v,w\}\in E\}$.


We say that $G$ is $k$-*common-neighbor-regular* if for all $v\neq w\in V$ we have $|N(v)\cap N(w)|=k$. (I haven't been able to find out whether there is a canonical term for this concept.)


Clearly the complete graph on $k+2$ points is $k$-common-neighbor-regular, but for $k>0$ I haven't been able to find non-complete examples.


Question: Given $k>0$, for which $n\in\mathbb{N}$ does there exist a $k$-common-neighbor-regular graph $G=(V,E)$ with $|V|=n$?



"Common-neighbor-regular" graphs
I claim that for $k>1$ any such graph is regular, in this case we get a well-known problem (subproblem of describing strongly regular graphs), which does not seem to be solved completely. Case $k=1$ is itself known, friendly vertex exists in this case by the friendship theorem of Paul Erdős, Alfréd Rényi, and Vera T. Sós (1966), see Brendan's comment. Ah, he have already found the general result aswell. 


At first, if there exists a vertex $v$ of degree $k+1$, then $G$ is complete graph on $k+2$ vertices. (Indeed, considering $v$ and any its neghbor we see that $v$ and its neighbors form $K\_{k+2}$. If there is another vertex $u$, considering $v$ and $u$ we see that $u$ must be joined with $k$ neighbors of $v$, but if so any two of them --- here we use that $k>1$ --- have more than $k$ common neighbors.)
If some vertex is joined with all other vertices, any other vertex has degree $k+1$, so we again get complete graph on $k+2$ vertices. Proceed with other cases.


At first, I consider a special case: $V=V\_1\sqcup V\_2$ for non-empty sets $V\_1,V\_2$, and all edges between $V\_1$ and $V\_2$ exist. Denote $n\_1=|V\_1|$, $n\_2=|V\_2|$, we have $n\_1>1$, $n\_2>1$, since there is no vertex joined with all other vertices. Choose vertices $v\_i\in V\_i$, $i=1,2$. Denote by $d\_i$ their degrees in subgraphs $G(V\_i)$. We have $d\_1+d\_2=k$, in particular, this does not depend on how we choose vertices. Next, any two vertices in $V\_1$ have $k-n\_2=d\_1+d\_2-n\_2:=\alpha\_1$ common neighbors in $V\_1$. Let $W$ be a set of neighbors of $v\_1$ in $G(V\_1)$. Then counting edges between $W$ and $v\_1\setminus (W\cup v\_1)$ leads to a standard relation $(n\_1-d\_1-1)\alpha\_1=d\_1(d\_1-\alpha\_1-1)=d\_1(n\_2-d\_2-1)>\alpha\_1(n\_2-d\_2-1)$, i.e. $n\_1-d\_1-1>n\_2-d\_2-1$, analogously $n\_2-d\_2-1>n\_1-d\_1-1$. Contradiction.


Now assume that our graph is not regular and $1,\dots,m$, $n>m>1$, are all vertices of the same degree $d$ (we may always assume so, since any graph with at least 2 vertices has two vertices with the same degree.) Let $A$ be adjacency matrix, then consider eigenspace of $A^2$ corresponding to eigenvalue $d-k$. It is easy to see that this is a space of dimension $m-1$, it consists of vectors $(x\_1,\dots,x\_n)$ for which $x\_{m+1}=\dots=x\_n=0$ and $x\_1+\dots+x\_{m}=0$. But eigenspace of $A^2$ is invariant for $A$. Thus any vector with these properties is invariant for $A$. It follows that any vertex $i>m$ is either joined with all $1,\dots,m$, or with none of them. Assume that there are $s$ vertices joined with all $1,\dots,m$. Then $s\leqslant k$. since they are common neighbors of $1,2$. By already considered case there is another vertex $v$, not joined with $1,\dots,m$. But 1 and $v$ have at most $s$ common neighbors. Thus $s=k$. But vertex 1 has degree at least $k+2$, so it is joined with some vertices $u\_1,u\_2\in\{1,\dots,m\}$. These two vertices have at least $k+1$ common neighbors. Contradiction.


