A tight upper bound on the (2,1)-total labeling number of outerplanar graphs

Details A tight upper bound on the (2,1)-total labeling number of outerplanar graphs A tight upper bound on the (2,1)-total labeling number of outerplanar graphs

2009-11-24

arxiv.org/abs/0911.4590v1

Computer Science

Discrete Mathematics

17 pages, 9figures

Scientific paper

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)|\ge 2$ if $x$ is a vertex and $y$ is an edge incident to $x$, and $|f(x)-f(y)|\ge 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)\cup E(G)$. The $(2,1)$-total labeling number $\lambda^T_2(G)$ of a graph $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, 2585--2593 (2007)], Chen and Wang conjectured that all outerplanar graphs $G$ satisfy $\lambda^T_2(G) \leq \Delta(G)+2$, where $\Delta(G)$ is the maximum degree of $G$, while they also showed that it is true for $G$ with $\Delta(G)\geq 5$. In this paper, we solve their conjecture completely, by proving that $\lambda^T_2(G) \leq \Delta(G)+2$ even in the case of $\Delta(G)\leq 4 $.

Affiliated with

Also associated with

No associations

Rating

A tight upper bound on the (2,1)-total labeling number of outerplanar graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A tight upper bound on the (2,1)-total labeling number of outerplanar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A tight upper bound on the (2,1)-total labeling number of outerplanar graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-279755