The niche graphs of interval orders

DOI10.7151/DMGT.1741zbMATH Open1290.05124arXiv1304.5476OpenAlexW3104587833MaRDI QIDQ2450130FDOQ2450130

Authors: Jeongmi Park, Yoshio Sano 

Publication date: 16 May 2014

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

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)cap{N}_D^{+}(y)eqemptyset$ or $N_D^{-}(x)cap{N}_D^{-}(y)eqemptyset$, 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:VomathbbR$ on the set $V$ and a positive real number $deltainmathbbR$ such that $(x,y)inA$ if and only if $f(x)>f(y)+delta$. A digraph $D=(V,A)$ is called an interval order if there exists an assignment $J$ of a closed real interval $J(x)subsetmathbbR$ to each vertex $xinV$ such that $(x,y)inA$ if and only if $minJ(x)>maxJ(y)$. S. -R. Kim and F. S. Roberts characterized the competition graphs of semiorders and interval orders in 2002, and Y. 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.

Full work available at URL: https://arxiv.org/abs/1304.5476

Recommendations

• scientific article; zbMATH DE number 617581
• The niche graphs of doubly partial orders
• Niche graphs
• The niche graphs of bipartite tournaments
• scientific article; zbMATH DE number 2187703

zbMATH Keywords

competition graphinterval ordersemiorderniche graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Partial orders, general (06A06) Structural characterization of families of graphs (05C75)

Cites Work

• The competition-common enemy graph of a digraph
• Niche graphs
• The competition-common enemy graphs of digraphs satisfying Conditions $C(p)$ and $C'(p)$
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (4)

• Niche hypergraphs
• Title not available (Why is that?)
• The niche graphs of doubly partial orders
• The niche graphs of bipartite tournaments

This page was built for publication: The niche graphs of interval orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2450130)