B. YAO ET AL.
66
distinct. In fact, there are many edge labeling that are
defined by |f(x)f(y)| or f(x)+ f(y) ([10], [6]).
New labellings. We are motivated from [4] and [6] to
define two new labellings as follo ws. All elements of any
number set mentioned are non-negative integers here. A
(p,q)-graph is one on p vertices and with q edges. The
symbol [k, k+m] stands for the set {k, k+1, , k+m},
where integers m>k0. A set S is called a k-set if it con-
tains k elements, i.e. k=|S|. The largest integer and the
least integer in S are denoted by max(S) and min(S), re-
spectively. The graphs under consideration are simple
and finite, undirected and loopless. We use the standard
notation and technology of graph theory, or they can be
found in [3] and [6]. We will show some connections
between our labellings and well-known colorings, such
as, the chromatic index
(G) and the chromatic number
(G) of a graph G.
A proper total coloring of a graph G is defined on a
subset of V(G)E(G) such that two adjacent or incident
elements of the subset are colored with different colors.
Similarly, a mapping f from the vertex set V(G) to [0,q] is
a proper vertex labelling of G if f(u) f(v) for all edges
uvE(G). Write f(V(G))={f(u): uV(G)} and f(E(G))=
{f(uv): uvE(G)}, or f(V) and f(E) if there is no danger of
confliction. Let k=max (f(V)) and let s indicate the num-
ber of distinct colors used in f(V), we call f a proper
(k,s)-vertex labelling of G. Thereby, we can define two
labellings as follows. Given a (p,q)-graph G having a
(k,s)-vertex labelling f: V(G)[0, q]. An induced differ-
ence edge-labelling if of f in G is defined as if
(uv)=|f(u)f(v)| for each edge uvE(G); and an induced
harmonious edge-labelling i+f of f in G is defined as i+f
(uv)=f(u)+f(v) (mod q) for each edge uvE(G).
Definition 1. A proper (k,s)-vertex labelling f of a
(p,q)-graph G, from V(G) to [0, q], is an induced differ-
ence total labelling (IDT labelling) of G if its induced
difference edge-labelling if is a proper edge coloring of
G. We say f to be a (k,s,t)-IDT labelling of G, where t =
|if(E)|. The least number of k spanning over all
(k,s,t)-IDT labellings of G, denoted as
(G), is called the
IDT-hromatic number.
Definition 2. A proper (k,s)-vertex labelling h of a
(p,q)-graph G, from V(G) to [0, q], is an induced ha rmo-
nious total labelling (IHT labelling) of G if its induced
harmonious edge-labelling i+h is a proper edge coloring
of G. Let t=|i+h (E)|, f is also called a (k,s,t)-IHT labelling
of G. The IHT-chromatic number of G, denote d as
+(G),
is the smallest number of k spanning over all (k,s,t)-IHT
labellings of G.
An IDT labelling f of a (p,q)-graph G is consecutive if
f(V)=[0, p1]. Analogously, an IHT labelling h of G is
consecutive if h(V)=[0, p1]. Clearly, every graph admits
a (k,s,t)-IDT labelling and a (k,s,t)-IHT labelling. A
(k,s,t)-IDT labelling of G is strong if it satisfies two addi-
tional requirements that k=
(G) and t is least, that is to
say, for any (k', s',t')-IDT labelling of G there is tt'. A
consecutive (k,s,t)-IDT labelling of a graph G may be a
graceful labelling or a sequential labelling of a
(p,q)-graph G if t=q (ref. [5], [6] and [13]), but a band-
width labelling of G, such a counterexample is a star. A
(k,s,t)-IHT labelling of G may b e a harmonious labelling
or a felicitous labelling of G if t=q ([6], [12]).
Let P4=uvwx denote a path on 4 vertices. A consecu-
tive (3,4,3)-IDT labelling f of P4 can be represented as
3302211, where f(u)=3, if (uv)=3, f(v)=0, if (vw)=2,
f(w)=2, if (wx)=1, f(x)=1. Again, P4 has a (3,3,3)-IDT
labelling 3301123 and a consecutive (3,3,2)-IDT label-
ling 2201123. We have that
(P4)=2 since P4 admits a
strong (2,3,2)-IDT labelling 1102211.
Definition 3. [14] Let S be a nonnegative integer k-set
containing zero. S is called an ordinary antiaverage k-set
if for any aS, the set S satisfies ai,1+ai,2++ ai,
a for
distinct ai,jS\{a}, 1j
. The ordinary antiaverage
number, denoted by
(
)(k), is equal to minSmax(S) span-
ning over all or di nary antiave rage k-sets S.
It is easy to see that
(Kn)=
(2)(n). We will use the
followin g gra p hs.
(1) The join graph of two graphs G and H, denoted by
G+H, is defined by V(G+H)=V(G)V(H) and E(G+H)=
E(G)E(H){uv: uV(G), vV(H)}.
(2) The kth power Gk of G is a simple graph with its
vertex set V(Gk)=V(G) and the edge set E(Gk)={uv:
dG(u,v)k}, where dG(u,v) indicates the distance between
u and v in G. Obviously , (Gk)[(G)]k.
(3) A uniquely cycle graph H holds that the graph He
will be a tree for any edge e on a cycle of H.
(4) For each vertex u of a connected G, its neighbor set
N(u) is {u1,u2,,ud}, where d=dG(u). We take another
graph Hu,d with vertex set V(Hu,d)={v1, v
2, , v
d}, and
then delete the vertex u from G, and next join vi to ui with
an edge for 1id. The resulting graph is denoted by
G(Hu,d), called a Hu,d -substitution graph of G. If each
Hu,d is a complete graph Kd, we write G(Kd) instead of
G(Hu,d).
2. Main Results
Observation 1. Let f be a (k,s,t)-IDT labelling of a graph
G. (i) (G)
'(G) tsk.
(ii) There is no path P=uwv on 3 vertices such that
f(u)+f(v)=2f(w).
(iii) The complementary labelling g of the labelling f is
defined by g(u)=kf(u) for all uV(G). Then g is a
(k,s,t)-IDT labelling.
(iv) Any induced subgraph by two color classes in a
(k,s,t)-IDT labelling of G consists of isolated edges plus
isolated vertices.
(v) If f(u)=f(v), then dG(u,v)3.
Copyright © 2013 SciRes. CN
