论文标题
半图像弦的弦
Semi-strict chordality of digraphs
论文作者
论文摘要
和弦图在算法图理论中很重要。和弦挖掘图是弦图的一个挖掘类似物，最近是活跃研究的主题。与弦图不同，弦弦的图形缺乏许多结构特性，例如禁止的子图或表示特征。在本文中，我们介绍了半分节弦式挖掘的概念，这些弦曲线构成了一个chordal digraphs和和弦图之间的类别。半图案弦式挖掘具有丰富的结构特性。我们在打结图方面表征了半图案弦式挖掘图，这一概念类似于加莱（Gallai）为研究可比性图研究的概念。在局部半完整的挖掘和弱的准传输挖掘的情况下，我们还提供了半分数弦弦图形的禁忌子图表。
Chordal graphs are important in algorithmic graph theory. Chordal digraphs are a digraph analogue of chordal graphs and have been a subject of active studies recently. Unlike chordal graphs, chordal digraphs lack many structural properties such as forbidden subdigraph or representation characterizations. In this paper we introduce the notion of semi-strict chordal digraphs which form a class strictly between chordal digraphs and chordal graphs. Semi-strict chordal digraphs have rich structural properties. We characterize semi-strict chordal digraphs in terms of knotting graphs, a notion analogous to the one introduced by Gallai for the study of comparability graphs. We also give forbidden subdigraph characterizations of semi-strict chordal digraphs within the cases of locally semicomplete digraphs and weakly quasi-transitive digraphs.
