论文标题
没有间隙vertex标签的图形：家庭和边界
Graphs without gap-vertex-labellings: families and bounds
论文作者
论文摘要
图$ g $的正确标记是一对$（π，c_π）$，其中$π$是$ g $的某些元素的数字标签的分配，而$c_π$是$π$在一组标签元素上通过某些数学功能引起的着色。在这项工作中，我们考虑了Gap-vertex-Labellings，其中顶点的颜色由考虑分配给其邻居的标签之间的最大差异确定。我们提供了任意图的顶点间隙数量的第一个上限，这是正确标记图所需的标签数量最少。我们调查了不接受任何差距标签的图形家族，而不管标签的数量多少。此外，我们引入了与此标签相关联的新型参数，并为其提供了完整图的界限$ {k_n} $。
A proper labelling of a graph $G$ is a pair $(π,c_π)$ in which $π$ is an assignment of numeric labels to some elements of $G$, and $c_π$ is a colouring induced by $π$ through some mathematical function over the set of labelled elements. In this work, we consider gap-vertex-labellings, in which the colour of a vertex is determined by a function considering the largest difference between the labels assigned to its neighbours. We present the first upper-bound for the vertex-gap number of arbitrary graphs, which is the least number of labels required to properly label a graph. We investigate families of graphs which do not admit any gap-vertex-labelling, regardless of the number of labels. Furthermore, we introduce a novel parameter associated with this labelling and provide bounds for it for complete graphs ${K_n}$.
