Geodesic
The niche graphs of interval orders
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 2, pp. 353-359
Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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
Keywords: competition graph, niche graph, semiorder, interval order 
@article{DMGT_2014_34_2_a9,
     author = {Park, Jeongmi and Sano, Yoshio},
     title = {The niche graphs of interval orders},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {353--359},
     year = {2014},
     volume = {34},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a9/}
}
TY  - JOUR
AU  - Park, Jeongmi
AU  - Sano, Yoshio
TI  - The niche graphs of interval orders
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 353
EP  - 359
VL  - 34
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a9/
LA  - en
ID  - DMGT_2014_34_2_a9
ER  - 
%0 Journal Article
%A Park, Jeongmi
%A Sano, Yoshio
%T The niche graphs of interval orders
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 353-359
%V 34
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a9/
%G en
%F DMGT_2014_34_2_a9
Park, Jeongmi; Sano, Yoshio. The niche graphs of interval orders. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 2, pp. 353-359. http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a9/

[1] C. Cable, K.F. Jones, J.R. Lundgren and S. Seager, Niche graphs, Discrete Appl. Math. 23 (1989) 231-241. doi:10.1016/0166-218X(89)90015-2

[2] J.E. Cohen, Interval graphs and food webs. A finding and a problem, RAND Corporation, Document 17696-PR, Santa Monica, California (1968).

[3] P.C. Fishburn, Interval Orders and Interval Graphs: A Study of Partially Ordered Sets, Wiley-Interscience Series in Discrete Mathematics, A Wiley-Interscience Publication (John Wiley & Sons Ltd., Chichester, 1985).

[4] S.-R. Kim and F.S. Roberts, Competition graphs of semiorders and Conditions C(p) and C∗(p), Ars Combin. 63 (2002) 161-173.

[5] Y. Sano, The competition-common enemy graphs of digraphs satisfying conditions C(p) and C′(p), Congr. Numer. 202 (2010) 187-194.

[6] D.D. Scott, The competition-common enemy graph of a digraph, Discrete Appl. Math. 17 (1987) 269-280. doi:10.1016/0166-218X(87)90030-8