A graph is said to be $k$-isoregular if for every subset $S$ of at most $k$ vertices the number common neighbors of the elements of $S$ depends only on the isomorphism type of the subgraph induced by $S$. I need an example of $k$-isoregular, where $k \ge 2$. The below given graph is not an valid example, see $\{4,14\}$ and $\{4,5\}$. Thanks in the advance.
2026-03-27 19:53:40.1774641220
On
Give an example of $k$-iso-regular for $k \ge 2$
147 Views Asked by user437890 https://math.techqa.club/user/user437890/detail At
2
There are 2 best solutions below
2
On
The regular complete $r$-multipartite graph $K_{n,n,\dots,n}$ is $k$-complete for all $k$.
The only way in which $S$ has common elements is if the $k$ elements are in different classes and then the number of common elements is $n(r-k)$.
For a much simpler example consider the empty and complete graphs.

Generally, any strongly regular graph satisfies the condition with $k=2$. For an example, consider the cycle $C_5$, or the Petersen Graph.