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$?


2 Answers 2


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.

  • $\begingroup$ Thanks @Fedor for your thoughts! I will think about it... I hope it's OK if I don't accept it yet as it is not yet a full answer, but it provides valuable insights (so I voted it up). Happy Easter $\endgroup$ Mar 24, 2016 at 13:06
  • 2
    $\begingroup$ This is a nice analysis but there is a problem with it, at least for $k=1.$ Then you can have $2t$ vertices of degree $2=k+1$ all joined to a vertex of degree $2t.$ $\endgroup$ Mar 24, 2016 at 22:36
  • 1
    $\begingroup$ Ah, of course, thank you, in 'straightforward' part we use that $k>1$. But $k=1$ is another well known problem. $\endgroup$ Mar 25, 2016 at 6:05

This problem was (partially?) solved by Kelmans in 1973 and by Ralucca Gera and Jian Shen in 2008. See this paper including the comment. They consider the generalization that friends have $\lambda$ common friends and non-friends have $\mu$ common friends. If the graph is regular, it is strongly-regular by definition. If it is irregular, it is either a disjoint union of complete graphs of some specified sizes, or a disjoint union of complete graphs of the same size plus an extra vertex joined to everything.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.