Name
Abstract | ||
|---|---|---|
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 @l\"p\",\"q^T(G), among all possible assignments. In this paper, we first give new upper and lower bounds on @l\"p\",\"q^T(G) for some classes of graphs G, in particular, tight bounds on @l\"p\",\"q^T(T) for trees T. We then show that if p@?3q/2, the problem for trees T is linearly solvable, and completely determine @l\"p\",\"q^T(T) for trees T with @D=4, where @D 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.disc.2012.01.007 | ISAAC |
Keywords | DocType | Volume |
tree | Journal | 312 |
Issue | ISSN | Citations |
8 | 0012-365X | 1 |
PageRank | References | Authors |
0.36 | 18 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toru Hasunuma | 1 | 142 | 16.00 |
| Toshimasa Ishii | 2 | 110 | 17.03 |
| Hirotaka Ono | 3 | 400 | 56.98 |
| yushi uno | 4 | 222 | 28.80 |