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?

  • $\begingroup$ 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. $\endgroup$ – LSpice Apr 24 '19 at 11:33
  • 2
    $\begingroup$ 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? $\endgroup$ – Timothy Budd Apr 24 '19 at 13:06
  • $\begingroup$ @Timothy Budd. No. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ thank you for this helpful answer. $\endgroup$ – j.s. Apr 26 '19 at 12:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.