Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
The (2,1)-Total Labeling Number of Outerplanar Graphs Is at Most Δ + 2
verfasst von : Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno
Erschienen in: Combinatorial Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\lambda^T_2(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
$\lambda^T_2(G) \leq \Delta(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
$\lambda^T_2(G) \leq \Delta(G)+2$
even in the case of Δ(
G
) ≤ 4 .