arXiv:2603.08585 · v2

A characterization of interval nest digraphs

区间嵌套有向图的刻画

首次提交 2026-03-10 00:37

版本更新 2026-11-13 01:43

雷达观测 2026-11-13 14:15

摘要

A digraph consisting of a set of vertices $V$ and a set of arcs $E$ is called an interval digraph if there exists a family of closed intervals $\{I_u,J_u\}_{u \in V}$ such that $uv$ is an arc if and only if the intersection of $I_u$ and $J_v$ is non-empty. Interval digraphs naturally generalize interval graphs, by extending the classical interval intersection model to directed graphs. Several subclasses of interval digraphs have been studied in the literature-such as balanced, chronological and catch interval digraphs-each characterized by admitting interval representations that satisfy specific restrictions. Among these, interval nest digraphs are the ones that admit an interval representation in which $J_u$ is contained in $I_u$ for all vertices $u$ of $V$. In this work, we provide a complete characterization of interval nest digraphs in terms of vertex linear orderings with forbidden patterns, which we call nest orderings. This result completes the picture of vertex-ordering characterizations among the main subclasses of interval digraphs.

作者备注：Small mistake correction with respect to the published version. A necessary condition in a related paper was (wrongly) stated buy us as a characterization, we have now corrected that mistake

期刊信息：Discrete Applied Mathematics 395 (2026), 337-344