# Graph families with high $k$-community

Just a quick question here, is there a known description of a graph family where for every graph $G=(V,E)$ it holds that for every $(u,v) \in E$ you have $|N(u) \cap N(v)| \geq k$? There was a definition for such graph as $k$-community. Even non-trivial examples (e.g., cliques) might be interesting.

Also, how to construct a graph which is a $k$-community, but does not have a $k+2$ clique? Is it possible at all?

Note that non-trivial cases also exclude not connected graphs and 1-vertex graphs.

• Think of a polyhedron with triangular faces. That is an example of $2$-communities without $4$-cliques. More generally, the $1$-skeleton of a simplicial $k$-sphere is a $k$-community without $k+2$-cliques (but with many $k+1$-cliques). – Willard Zhan Feb 23 '18 at 18:56

Strongly regular graphs fit the bill, i.e., one property is that adjacent vertices have (exactly) $\lambda$ common neighbors. Paley graphs should give you an infinite family and an explicit construction.