4
$\begingroup$

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?

$\endgroup$
3
  • $\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
    Commented Apr 24, 2019 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$ Commented Apr 24, 2019 at 13:06
  • $\begingroup$ @Timothy Budd. No. $\endgroup$
    – j.s.
    Commented Apr 24, 2019 at 19:12

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thank you for this helpful answer. $\endgroup$
    – j.s.
    Commented Apr 26, 2019 at 12:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .