Skip to main content
1 of 6
Mike
  • 1k
  • 6
  • 14

Couldn't you write every $d$-regular graph this way? Indeed, let $G$ be your favorite $d$-regular graph on $n$ vertices.

Set $f_u$ to be the vector on $\mathbb{R}^{V(G)}$ s.t. $f_u(u) = 1$ and $f_u(v) = 0$ for each $v \in V(G) \setminus \{u\}$.

Set $g_u$ to be the vector on $\mathbb{R}^{V(G)}$ s.t. $g_u(u') = \frac{1}{\sqrt{d}}$ if either $u'=u$ or $u' \in N_G(u)$, and $g_u(v) = 0$ for each remaining $v$.

Then for every two vertices $u$ and $v$, note that $||f_u-f_v||_2^2$ is precisely 2. However, $||g_u-g_v||_2^2$ is $\left(\frac{1}{d} \right) \times 2d = 2$ iff $u$ and $v$ are adjacent in $G$, and is $\frac{2(d+1)}{d}$ otherwise.

My point is that the family of graphs that you just specified is likely quite a big family.

Mike
  • 1k
  • 6
  • 14