论文标题
一些与阈值和链图有关的不变性
Some invariants related to threshold and chain graphs
论文作者
论文摘要
令G =（V，e）为有限的简单连接图。我们说图G实现了类型0^S_1 1^T_1 0^S_2 1^T_2 ... 0^S_K1^T_K的代码，并且仅当G可以通过某些规则从代码获得。阈值和链图等某些类别的图表实现了上述类型的代码。在本文中，我们开发了一些计算可行的方法来确定一些有趣的图理论不变性。我们提出了一种有效的算法来确定阈值和链图的度量。我们计算阈值阈值尺寸和阈值图的限制。我们讨论L（2，1） - 阈值和链图的颜色。实际上，对于每个阈值图G，我们都会建立一个公式，通过该公式可以获得G的λ-Chromation Gumber。
Let G = (V, E) be a finite simple connected graph. We say a graph G realizes a code of the type 0^s_1 1^t_1 0^s_2 1^t_2 ... 0^s_k1^t_k if and only if G can obtained from the code by some rule. Some classes of graphs such as threshold and chain graphs realizes a code of the above mentioned type. In this paper, we develop some computationally feasible methods to determine some interesting graph theoretical invariants. We present an efficient algorithm to determine the metric dimension of threshold and chain graphs. We compute threshold dimension and restricted threshold dimension of threshold graphs. We discuss L(2, 1)-coloring of threshold and chain graphs. In fact, for every threshold graph G, we establish a formula by which we can obtain the λ-chromatic number of G. Finally, we provide an algorithm to compute the λ-chromatic number of chain graphs.
