论文标题
各种图类的注入性船体
Injective hulls of various graph classes
论文作者
论文摘要
如果其磁盘满足Helly特性，即G中的每个家族在G中的磁盘都有一个共同的相交，则图形为Helly。众所周知，对于每个图G，都存在一个独特的最小的Helly图H（g），G中嵌入了g。 h（g）称为G的内注射船体。由此激发，我们研究了各种图类别的注入性船体的结构特性。我们说，如果$ g \ in \ mathcal {c} $ in \ mathcal {c} $ in \ mathcal {c} $ in \ mathcal {c} $ in \ mathcal {c} $，则在地狱化下关闭了一类图形$ \ MATHCAL {C} $。我们确定了在地狱化下关闭的几个图表类。我们表明，置换图在地狱化下并未闭合，而是弦图，方形图形和距离式图形。具有有效计算的注射式船体的图特别感兴趣。提供了用于构建任何距离heredarentar图的注射船体的线性时间算法，我们表明，来自其他一些众所周知的图形类别的几个图形的注入性船体在次指定时间中不可能计算。特别是，有分型图，可可比较图，双分图G，使得H（g）包含$ω（a^{n}）$ vertices，其中$ n = | v（g）| $和$ a> 1 $。
A graph is Helly if its disks satisfy the Helly property, i.e., every family of pairwise intersecting disks in G has a common intersection. It is known that for every graph G, there exists a unique smallest Helly graph H(G) into which G isometrically embeds; H(G) is called the injective hull of G. Motivated by this, we investigate the structural properties of the injective hulls of various graph classes. We say that a class of graphs $\mathcal{C}$ is closed under Hellification if $G \in \mathcal{C}$ implies $H(G) \in \mathcal{C}$. We identify several graph classes that are closed under Hellification. We show that permutation graphs are not closed under Hellification, but chordal graphs, square-chordal graphs, and distance-hereditary graphs are. Graphs that have an efficiently computable injective hull are of particular interest. A linear-time algorithm to construct the injective hull of any distance-hereditary graph is provided and we show that the injective hull of several graphs from some other well-known classes of graphs are impossible to compute in subexponential time. In particular, there are split graphs, cocomparability graphs, bipartite graphs G such that H(G) contains $Ω(a^{n})$ vertices, where $n=|V(G)|$ and $a>1$.
