# The niche graphs of interval orders

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 2, page 353-359
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJeongmi 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 -

## References

top- [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[Crossref] Zbl0677.05039
- [2] J.E. Cohen, Interval graphs and food webs. A finding and a problem, RAND Corpo- ration, 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 Pub- lication (John Wiley & Sons Ltd., Chichester, 1985). Zbl0551.06001
- [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. Zbl1231.05114
- [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[Crossref]

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.