1
$\begingroup$

$\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?

$\endgroup$
  • $\begingroup$ $|B|$ is the number of vertices in subset $B$. $\endgroup$ – Jim May 29 '16 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.