- Tytuł:
- The niche graphs of interval orders
- Autorzy:
-
Park, Jeongmi
Sano, Yoshio - Powiązania:
- https://bibliotekanauki.pl/articles/30148237.pdf
- Data publikacji:
- 2014-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
competition graph
niche graph
semiorder
interval order - Opis:
- 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 → \mathbb{R}$ on the set $V$ and a positive real number $δ ∈ \mathbb{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) ⊂ \mathbb{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
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2014, 34, 2; 353-359
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł