论文标题
本地半完整和弱的准传递二曲的弦
Chordality of locally semicomplete and weakly quasi-transitive digraphs
论文作者
论文摘要
弦图在结构和算法图理论中很重要。哈斯金（Haskin）和罗斯（Rose）于1973年引入了弦图的沟弦类似物，但直到最近，就迈斯特（Meister）和泰勒（Telle）发现了禁止的子图的表征，直到最近，直到最近对半完整的弦核挖掘表征进行表征。局部半完整的挖掘图，准传播的挖掘和扩展半完整的挖掘是半完整的挖掘物的最流行的概括之一。我们将半完整的弦式挖掘物的禁止子段表征扩展到局部半完整的和弦挖掘。我们介绍了一种新的挖掘图，称为弱传播的挖掘图，其中包含准传播的挖掘图，对称的挖掘和扩展的半完整挖掘图，但与局部半完整的二分法类别无与伦比。我们表明，可以通过从瞬时图形，半完整的挖掘和对称的挖掘物中递归构建弱的准传播挖掘图。这种弱构造的准传播挖掘物的递归构造，类似于准传播的挖掘物，证明了新的Digraph类的自然性。作为副产品，我们证明了半完整的弦式挖掘的禁忌子图对于弱传播的弦弦图是相同的。
Chordal graphs are important in the structural and algorithmic graph theory. A digraph analogue of chordal graphs was introduced by Haskin and Rose in 1973 but has not been a subject of active studies until recently when a characterization of semicomplete chordal digraphs in terms of forbidden subdigraphs was found by Meister and Telle. Locally semicomplete digraphs, quasi-transitive digraphs, and extended semi-complete digraphs are amongst the most popular generalizations of semicomplete digraphs. We extend the forbidden subdigraph characterization of semicomplete chordal digraphs to locally semicomplete chordal digraphs. We introduce a new class of digraphs, called weakly quasi-transitive digraphs, which contains quasi-transitive digraphs, symmetric digraphs, and extended semicomplete digraphs, but is incomparable to the class of locally semicomplete digraphs. We show that weakly quasi-transitive digraphs can be recursively constructed by simple substitutions from transitive oriented graphs, semicomplete digraphs, and symmetric digraphs. This recursive construction of weakly quasi-transitive digraphs, similar to the one for quasi-transitive digraphs, demonstrates the naturalness of the new digraph class. As a by-product, we prove that the forbidden subdigraphs for semicomplete chordal digraphs are the same for weakly quasi-transitive chordal digraphs.
