Give an example of $k$-iso-regular for $k \ge 2$

147 Views Asked by At

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.

enter image description here

2

There are 2 best solutions below

2
On BEST ANSWER

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

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.