Number of Vertices with $\mu$ Common Neighbor

41 Views Asked by At

$\mathcal{G}$ is a graph class. Each graph $G$ of $\mathcal{G}$ has the following properties-

  1. $G$ is a $k$ (variable with respect to different graphs) regular graph of $n$ vertices. The vertex set $V$ consists all $n$ vertices of $G$.

  2. Each $G$ has a subset $B$ of $V$ with $\mu$ (variable with respect to different graphs) common neighbors ( for all graphs of class $\mathcal{G}$).

  3. $|B| \leq c$ where $c$ is a constant (for all graphs of class $\mathcal{G}$).

Does graph class $\mathcal{G}$ exist?

For example, if we consider Strongly Regular Graph, then $c$ does not exist.

Is there anything in literature related to this problem?