PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

## Discussiones Mathematicae Graph Theory

2014 | 34 | 2 | 353-359
Tytuł artykułu

### The niche graphs of interval orders

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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
Słowa kluczowe
EN
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
353-359
Opis fizyczny
Daty
wydano
2014-05-01
online
2014-04-12
Twórcy
autor
• Department of Mathematics Pusan National University Busan 609-735, Korea, jm1015@pusan.ac.kr
autor
• Division of Information Engineering Faculty of Engineering, Information and Systems University of Tsukuba Ibaraki 305-8573, Japan, sano@cs.tsukuba.ac.jp
Bibliografia
• [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]
• [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).
• [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[Crossref]
Typ dokumentu
Bibliografia
Identyfikatory