# Graphs with adjacency matrix depending on associated-vector distances

Let $$G$$ be a graph of order $$n$$ such that for each vertex $$v$$ there are two associated vectors, $$f_v, g_v\in R^n$$, where $$uv\in E(G)$$ if and only if $$\|f_u - f_v\|^2 \ge \|g_u-g_v\|^2$$.

ISGCI didn't discuss such a class.

Has this class of graphs been studied? What are their properties? Are they perhaps equivalent to some well-known graph class?

• I changed your title to something more informative. If I didn't capture the idea, then please feel free to change it again, but preferably still to something more informative than the original. – LSpice Apr 24 '19 at 11:33
• Is there any particular reason you take the vectors $f_v$, $g_v$ to have the same number of components as the order $n$ of the graph? – Timothy Budd Apr 24 '19 at 13:06
• @Timothy Budd. No. – j.s. Apr 24 '19 at 19:12

Couldn't you write (almost) every $$d$$-regular simple graph this way though. That is, any regular graph where the length of the smallest cycle is at least 5 can be written this way. [Meanwhile, for any fixed $$d$$ and $$n$$ sufficiently large relative to $$d$$, almost every $$d$$-regular graph on $$n$$ vertices has no cycle of length 4 or less].

Indeed, let $$G$$ be your favorite $$d$$-regular graph on $$n$$ vertices where the length of the smallest cycle in $$G$$ is at least 5.

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 no more than $$\left(\frac{1}{d} \right) \times 2d = 2$$ iff $$u$$ and $$v$$ are adjacent in $$G$$, and is at least $$\frac{2d+1}{d}$$ otherwise. [Precisely $$\frac{2d+1}{d}$$ iff nonadjacent $$u$$ and $$v$$ share a neighbour; $$\frac{2d+2}{d}$$ iff nonadjacent $$u$$ and $$v$$ do not share a neighbour. From the fact that there are no 4-cycles $$u$$ and $$v$$ cannot share more than 1 neighbour] So iff $$u$$ and $$v$$ are adjacent in $$G$$ then they will also be adjacent in this resulting graph $$H_G$$ where $$u$$ and $$v$$ are adjacent in $$H_G$$ iff the inequality

$$||f_u-f_v||_2^2 \le ||g_u-g_v||_2^2$$

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

If you are thinking social network graphs $$G$$ then from $$G$$ and a modified version of the above construction, you could obtain a graph $$H_G$$ where $$u$$ and $$v$$ would be adjacent in $$H_G$$ iff $$u$$ and $$v$$ have a lot of common contacts in $$G$$. OR you could flip $$f_v$$ with $$g_v$$ for each $$v \in V(G)$$ and achieve the complement.

• thank you for this helpful answer. – j.s. Apr 26 '19 at 12:35