论文标题
在表征正确的最大点公差图
On characterizing proper-max-point tolerance graphs
论文作者
论文摘要
Catanzaro等人引入了最大点耐耐受图（MPTG）。在2017年作为间隔图的概括。该图类别在人类基因组以及网络的信号处理方面具有许多实际应用。 Soto and Caro在2015年还以P-Box（1）图的名称研究了相同的图形。在我们的文章中，我们考虑了一个自然的最大点含量图的子类，即，适当的最大点含量图（适当的MPTG）在与dertices相关的间隔中不适当地包含在彼此中。我们通过在顶点集上定义某些线性排序来介绍该图类的第一个表征定理。在这项研究的过程中，我们证明适当的最大耐耐耐受图是小行星三倍的无三重且完美的。我们还发现，正确的最大点耐耐能图等效于单位最大点含量图。此外，我们注意到MPTG（适当的MPTG）和最大耐受性图（适当的最大耐耐受图）是无与伦比的。总之，我们证明了适当的MPTG与MPTG的其他变体与最大耐受图之间的关系。
Max-point-tolerance graphs (MPTG) was introduced by Catanzaro et al. in 2017 as a generalization of interval graphs. This graph class has many practical applications in study of human genome as well as in signal processing for networks. The same class of graphs were also studied in the name of p-BOX(1) graphs by Soto and Caro in 2015. In our article, we consider a natural subclass of max-point-tolerance graphs namely, proper max-point-tolerance graphs (proper MPTG) where intervals associated to the vertices are not contained in each other properly. We present the first characterization theorem of this graph class by defining certain linear ordering on the vertex set. In course of this study we prove proper max-point-tolerance graphs are asteroidal triple free and perfect. We also find proper max-point-tolerance graphs are equivalent to unit max-point-tolerance graphs. Further we note that MPTG (proper MPTG) and max-tolerance graphs (proper max-tolerance graphs) are incomparable. In conclusion we demonstrate relations between proper MPTG with other variants of MPTG and max-tolerance graphs.
