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