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.

  • $\begingroup$ 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). $\endgroup$ – 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.


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.