Abstract | ||
---|---|---|
A (2, 1)-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 {0, 1, ..., k} of nonnegative integers such that |f(x) - f(y)| ≥ 2 if x is a vertex and y is an edge incident to x, and |f(x) - f(y)| ≥ 1 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). The (2, 1)-total labeling number λ2T(G) of G is defined as the minimum k among all possible assignments. In [D. Chen and W. Wang. (2,1)-Total labelling of outerplanar graphs. Discr. Appl. Math. 155 (2007)], it was conjectured that all outerplanar graphs G satisfy λ2T(G) ≤ Δ(G)+2, where Δ(G) is the maximum degree of G, while they also showed that it is true for G with Δ(G) ≥ 5. In this paper, we solve their conjecture completely, by proving that λ2T(G) ≤ Δ(G)+2 even in the case of Δ(G) ≤ 4. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/978-3-642-19222-7_11 | IWOCA |
Keywords | Field | DocType |
maximum degree,adjacent vertex,total labelling,outerplanar graph,adjacent edge,edge set e,minimum k,graph g,edge incident,w. wang,satisfiability | Integer,Discrete mathematics,Graph,Combinatorics,Bound graph,Vertex (geometry),Degree (graph theory),Conjecture,Mathematics | Conference |
Citations | PageRank | References |
2 | 0.36 | 10 |
Authors | ||
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 |