Min-Orderable Digraphs
Min-Orderable Digraphs
复制标题
最小可排序有向图
DOI：
10.1137/19m1241763
复制
发表时间：
2020
影响因子：
0.8
通讯作者：
Rafiey, Arash
中科院分区：
文献类型：
--
作者：
Hell, Pavol;Huang, Jing;McConnell, Ross M.;Rafiey, Arash
我们统一了几个看似不同的图和有向图类在一个保护伞下。 广义地说，这些类都是区间图的不同推广，除了区间图之外，还包括调整区间有向图、阈值容差图的补图（称为co-TT图）、二部区间包含图、二部共圆弧图和双向正交射线图。(The最后三个类重合，但在不同的上下文中进行了研究。）我们表明，所有上述类是统一的一个共同的排序特征，存在一个最小的顺序。 然而，由于自反关系（循环）的存在或不存在会影响图或有向图是否具有最小排序，为了获得这个结果，我们必须定义图和有向图，使其具有它们的定义所暗示的那些循环。 这些在以前的工作中基本上被忽略了。 我们提出了一个共同的概括所有这些图和有向图类，即符号区间有向图，其特征在于存在一个紧凑的表示，符号区间模型，这是一个推广的已知表示的图形类。 我们表明，符号区间有向图正是那些有向图，其特征在于存在一个最小的顺序时，该模型所隐含的循环被认为是图的一部分。 我们还提供了这些有向图的另一种几何表征。 证明了co-TT图是对称的符号区间有向图，调整区间有向图是自反的符号区间有向图，区间图是这两类图的交集，即自反的符号区间有向图和对称的符号区间有向图. 类似的结果也适用于二部区间包含图、二部共圆弧图和双向正交射线图。
We unify several seemingly different graph and digraph classes under one umbrella. These classes are all, broadly speaking, different generalizations of interval graphs, and include, in addition to interval graphs, adjusted interval digraphs, complements of threshold tolerance graphs (known as co-TT graphs), bipartite interval containment graphs, bipartite co-circular arc graphs, and two-directional orthogonal ray bigraphs. (The last three classes coincide, but have been investigated in different contexts.) We show that all of the above classes are united by a common ordering characterization, the existence of a min ordering. However, because the presence or absence of reflexive relationships (loops) affects whether a graph or digraph has a min ordering, to obtain this result, we must define the graphs and digraphs to have those loops that are implied by their definitions. These have been largely ignored in previous work. We propose a common generalization of all these graph and digraph classes, namely signed-interval digraphs, characterized by the existence of a compact representation, a signed-interval model, which is a generalization of known representations of the graph classes. We show that the signed-interval digraphs are precisely those digraphs that are characterized by the existence of a min ordering when the loops implied by the model are considered part of the graph. We also offer an alternative geometric characterization of these digraphs. We show that co-TT graphs are the symmetric signed-interval digraphs, the adjusted interval digraphs are the reflexive signed-interval digraphs, and the interval graphs are the intersection of these two classes, namely, the reflexive and symmetric signed-interval digraphs. Similar results hold for bipartite interval containment graphs, bipartite co-circular arc graphs, and two-directional orthogonal ray bigraphs.
登录
查看更多内容
DOI：
--
发表时间：
2006
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Jing Huang
通讯作者：
Jing Huang
禁止的有序子图
影响因子：
6.1
作者：
P. Damaschke
通讯作者：
P. Damaschke
统治
影响因子：
0.7
作者：
Lonnie Athens
通讯作者：
Lonnie Athens
排列矩阵以避免禁止子矩阵
DOI：
10.1016/0166-218x(94)00054-h
发表时间：
1995
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Bettina Klinz;Rüdiger Rudolf;G. Woeginger
通讯作者：
G. Woeginger
影响因子：
1.1
作者：
T. Feder;P. Hell;Jing Huang
通讯作者：
Jing Huang