The niche graphs of interval orders

Jeongmi Park, and Yoshio Sano. "The niche graphs of interval orders." Discussiones Mathematicae Graph Theory 34.2 (2014): 353-359. <http://eudml.org/doc/267657>.

@article{JeongmiPark2014,
abstract = {The niche graph of a digraph D is the (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if N+D(x) ∩ N+D(y) ≠ ∅ or N−D(x) ∩ N−D(y) ≠ ∅, where N+D(x) (resp. N−D(x)) is the set of out-neighbors (resp. in-neighbors) of x in D. A digraph D = (V,A) is called a semiorder (or a unit interval order ) if there exist a real-valued function f : V → R on the set V and a positive real number δ ∈ R such that (x, y) ∈ A if and only if f(x) > f(y)+δ. A digraph D = (V,A) is called an interval order if there exists an assignment J of a closed real interval J(x) ⊂ R to each vertex x ∈ V such that (x, y) ∈ A if and only if min J(x) > max J(y). Kim and Roberts characterized the competition graphs of semiorders and interval orders in 2002, and Sano characterized the competition-common enemy graphs of semiorders and interval orders in 2010. In this note, we give characterizations of the niche graphs of semiorders and interval orders},
author = {Jeongmi Park, Yoshio Sano},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {competition graph; niche graph; semiorder; interval order},
language = {eng},
number = {2},
pages = {353-359},
title = {The niche graphs of interval orders},
url = {http://eudml.org/doc/267657},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Jeongmi Park
AU - Yoshio Sano
TI - The niche graphs of interval orders
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 2
SP - 353
EP - 359
AB - The niche graph of a digraph D is the (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if N+D(x) ∩ N+D(y) ≠ ∅ or N−D(x) ∩ N−D(y) ≠ ∅, where N+D(x) (resp. N−D(x)) is the set of out-neighbors (resp. in-neighbors) of x in D. A digraph D = (V,A) is called a semiorder (or a unit interval order ) if there exist a real-valued function f : V → R on the set V and a positive real number δ ∈ R such that (x, y) ∈ A if and only if f(x) > f(y)+δ. A digraph D = (V,A) is called an interval order if there exists an assignment J of a closed real interval J(x) ⊂ R to each vertex x ∈ V such that (x, y) ∈ A if and only if min J(x) > max J(y). Kim and Roberts characterized the competition graphs of semiorders and interval orders in 2002, and Sano characterized the competition-common enemy graphs of semiorders and interval orders in 2010. In this note, we give characterizations of the niche graphs of semiorders and interval orders
LA - eng
KW - competition graph; niche graph; semiorder; interval order
UR - http://eudml.org/doc/267657
ER -