6
$\begingroup$

Indifference graphs are those graphs $G=(V,E)$ for which there exists a real-valued function $f$ defined on $V(G)$ such that, if $u$ and $v$ are distinct vertices, $|f(u)−f(v)| \lt 1$ if and only if $\{u,v\}\in E$. A famous result of Roberts (1969) shows that this graphs are equivalent to the unit interval graphs (or the proper interval graphs), and they are further equivalent to the $K_{1,3}$-free interval graphs.

I need know about those graphs $G=(V,E)$ for which there exists two real-valued function $f$ and $g$ defined on $V(G)$ such that, if $u$ and $v$ are distinct vertices, $|f(u)−f(v)| \lt |g(u)−g(v)|$ if and only if $\{u,v\}\in E$. ISGCI didn't know of such a class.

Have this class of graphs been studied before? What kind of properties do they have? Are they perhaps equivalent to some well-known (or a better known) graph class?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

Seeing that indifference graphs are the same as unit interval graphs is very easy: we simply identify each vertex $v$ with a unit interval centred at $f(v)$.

We can try to do something similar here. Identify each vertex $v$ with the point $(f(v), g(v))$ in $\mathbb R^2$. Then two points are adjacent if and only if the line joining them is closer to vertical than horizontal. Rotating the picture 45 degrees anticlockwise, two points are adjacent if and only if the line joining them has negative slope. If we assume that in this rotated picture no $x$ or $y$ coordinate is repeated, then this is precisely the definition of a permutation graph.

If some coordinates are repeated, then we can perturb the points slightly so that the associated vertical or horizontal lines joining pairs of points become lines of positive slope, so we also get a permutation graph in this case.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Quite interesting. $\endgroup$
    – T. Amdeberhan
    Commented Jan 13, 2017 at 13:47
  • $\begingroup$ @Ben Barber: A Genius Answer. thanks. But It's not perfectly clear to me why the class of permutation graphs are equivalent to graphs constructed by assigning a point in plane to each vertex and connecting two vertices by an edge when the line joining them has negative slope. Is this obvious? $\endgroup$
    – j.s.
    Commented Jan 13, 2017 at 22:31
  • 1
    $\begingroup$ Given a permutation, we can draw its graph (in the sense that functions have graphs) as a subset of $\mathbb R^2$. Then inversions correspond precisely to pairs of points joined by a line of negative slope. Note that the actual $x$ and $y$ coordinates aren't important: all that matters is their relative order. This is only obvious if you've seen it before! $\endgroup$
    – Ben Barber
    Commented Jan 13, 2017 at 23:06
  • $\begingroup$ @Ben Barber: Thank you so much for this wonderful answer. $\endgroup$
    – j.s.
    Commented Jan 14, 2017 at 3:57

You must log in to answer this question.

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