The niche graphs of interval orders

Park, Jeongmi  ; Sano, Yoshio

Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 2, pp. 353-359

Résumé

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 → ℝ on the set V and a positive real number δ ∈ ℝ such that (x, y) ∈ A if and only if f(x) gt; 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) ⊂ ℝ to each vertex x ∈ V such that (x, y) ∈ A if and only if min J(x) gt; 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

Détail

Keywords: competition graph, niche graph, semiorder, interval order