The (p, q)-total labeling problem for trees
The (p, q)-total labeling problem for trees
复制标题
树的 (p, q)-总标记问题
DOI：
10.1016/j.disc.2012.01.007
复制
发表时间：
2012
影响因子：
0.8
通讯作者：
Yushi Uno
中科院分区：
文献类型：
--
作者：
Toru Hasunuma;Toshimasa Ishii;Hirotaka Ono;Yushi Uno
图G的一个（p，q）-全标号是从点集V（G）和边集E（G）到非负整数集合的一个赋值f，使得|f（x）-f（y）|≥p，如果x是顶点，y是与x关联的边，并且|f（x）-f（y）|≥q，如果x和y是一对相邻的顶点或一对相邻的边，对V（G）<$E（G）中的所有x和y.一个k-（p，q）-全标号是一个（p，q）-全标号f：V（G）<$E（G）→{0，.，k}，（p，q）-全标号问题要求在所有可能的赋值中取最小k，记为λp，qT（G）.本文首先给出了几类图G的λp，qT（G）的新的上下界，特别是树T的λp，qT（T）的紧界.然后证明了当p≤3q/2时，树T的问题是线性可解的，并完全确定了树T的λp，qT（T），其中Δ≥4，其中Δ是T的最大度.这与L（p，q）-标号问题（它是（p，q）-全标号问题的推广）是NP-困难的事实形成对比，对于任意两个正整数p和q，q不是p的除数。
A (p,q)-total labeling of a graph G is an assignment f from the vertex set V(G) and the edge set E(G) to the set of nonnegative integers such that |f(x)−f(y)|≥p if x is a vertex and y is an edge incident to x, and |f(x)−f(y)|≥q if x and y are a pair of adjacent vertices or a pair of adjacent edges, for all x and y in V(G)∪E(G). A k-(p,q)-total labeling is a (p,q)-total labeling f:V(G)∪E(G)→{0,…,k}, and the (p,q)-total labeling problem asks the minimum k, which we denote by λp,qT(G), among all possible assignments. In this paper, we first give new upper and lower bounds on λp,qT(G) for some classes of graphs G, in particular, tight bounds on λp,qT(T) for trees T. We then show that if p≤3q/2, the problem for trees T is linearly solvable, and completely determine λp,qT(T) for trees T with Δ≥4, where Δ is the maximum degree of T. It is contrasting to the fact that the L(p,q)-labeling problem, which is a generalization of the (p,q)-total labeling problem, is NP-hard for any two positive integers p and q such that q is not a divisor of p.
登录
查看更多内容
用距离为 2 的条件标记树
DOI：
10.1016/s0012-365x(02)00750-1
发表时间：
2003
期刊：
Discret. Math.
影响因子：
--
作者：
J. Georges;D. Mauro
通讯作者：
D. Mauro
DOI：
--
发表时间：
1982
期刊：
--
影响因子：
--
作者：
O. Terada
通讯作者：
O. Terada
影响因子：
1.1
作者：
Toru Hasunuma;Toshimasa Ishii;H. Ono;Yushi Uno
通讯作者：
Toru Hasunuma;Toshimasa Ishii;H. Ono;Yushi Uno
DOI：
10.1016/j.jda.2011.12.020
发表时间：
2009-11
期刊：
J. Discrete Algorithms
影响因子：
--
作者：
Toru Hasunuma;Toshimasa Ishii;H. Ono;Yushi Uno
通讯作者：
Toru Hasunuma;Toshimasa Ishii;H. Ono;Yushi Uno
L(j, k)-树的标记和最大有序度
DOI：
10.1016/j.dam.2009.11.018
发表时间：
2010
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
V. Pavlidis;E. Friedman
通讯作者：
E. Friedman