Paper Menu >>

Journal Menu >>

Communications and Network, 2013, 5, 65-68
http://dx.doi.org/10.4236/cn.2013.53B2013 Published Online September 2013 (http://www.scirp.org/journal/cn)
Induced Total Labellings of Models as Scale-free
Networks
Bing Yao1, Jiajuan Zhang1, Xiangq ian Zhou1, Xiang’en Chen1, Xiaomin Zhang1,
Ming Yao2, Mogang Li2
1College of Mathematics and Statistics, Northwest Normal University, Lanzhou, Gansu, China
2Department of Information Process and Control Engineering,
Lanzhou Petrochemical College of Vocational Technology, Lanzhou, China
Email: [email protected], [email protected]
Received April, 2013
ABSTRACT
A recently discovered approach including de Brujin graphs and Eulerian circuits are used to DNA sequencing and
fragment assembly, and to simplify DNA graphs through a series of transformations on graphs and digraphs in the field
of bioinformatics. Since numbered graphs provide underlying mathematical models in studying the wide variety of
seemingly unrelated practical applications, so graph colorings often are used to divide large systems into subsystems. A
new graph labeling has been introduced and investigated.
Keywords: Bioinformatics; Network; Graph Labeling; Chromatic Numbers
1. Introduction
Scientists and researchers have emphasized DNA se-
quencing and fragment assembly with the hopes of en-
hancing their abilities to reconstruct full strands of DNA
based on the pieces of data they are able to record in re-
cent years. Complications arise with fragment assembly
due to imperfect data sets. Strands are often riddled with
repeats and come in varying sizes. As a result, configur-
ing the image of the original genome is not as easy as
fitting one puzzle piece into the next [7]. A recently dis-
covered approach including de Brujin graphs and Eule-
rian circuits are used to DNA sequencing and fragment
assembly, and to simplify DNA graphs through a series
of transformations on graphs and digraphs in the field of
bioinformatics [9].
In Operations Research or Systems Engineering The-
ory and Methods, one very often use graph colorings to
divide large systems into subsystems. Coloring (di)
graphs can be used to describe the street configuration
[1], and distinguishing colorings [11] are related with
traffic network and the frequency assignments of radio
and satellites. Numbered graphs interpretations also ap-
ply to other areas of mathematics. Some of the most sig-
nificant numerical results have result from the corre-
spondence between some ruler problems in additive
number theory and numbered graphs. Many applications
of graph labeling can be found in [6].
Bloom and Golomb [2] have shown that numbered
graphs provide underlying mathematical models in
studying the wide variety of seemingly unrelated practi-
cal applications. For example, the design of certain im-
portant classes of good non-periodic codes for pulse ra-
dar and missile guidance is equivalent to numbering the
complete graph in such a way that all the edge numbers
are distinct; “nonnatural” methods of encoding the inte-
gers from 0 to bn1 using n-digit vectors from the
b-symbol alphabet have been devised to minimize the
seriousness of errors occurring in a single digit; determi-
nation of crystal structures from X-ray difference data
has long been a concern of crystallographers; other ap-
plications of numbered graphs have included design of
highly accurate optical gauging systems for use on auto-
matic drilling machines, design of angular synchroniza-
tion codes, design of optical component layouts for cer-
tain circuit-board geometries, and determining configura-
tions of simple resistor networks which can be used to
supply any of a specific set of resistance values. Bollobas
and Pikhurko [4] introduce that a difference-magic label-
ling of a graph G is an injective mapping f: V(G)N (the
set of all natural numbers) such that the labels |f(x)f(y)|
of edges xyE(G) are pair wise distinct. Clearly, every
graph admits a difference-magic labeling, so a natural
question to ask is how economical it can be. More pre-
cisely, the difference-magic number D(G) which is the
smallest k such that a difference-magic labeling of G into
{1,2,, k} exists. And they also defined: A sum- magic
labeling of a graph G as an injection f: V(G)N such
that the labels f(x)+f(y) of edges xyE(G) are pair wise
C
opyright © 2013 SciRes. CN
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
B. YAO ET AL. 67
Observation 2. Let G be a (p,q)-graph.
(i)
(H)
(G) for any subgraph H of G,
(ii)
(G2)
(G).
(iii) p1
(G)
(2)(p) if the diameter of G is not lar-
ger than 2.
Lemma 1. If f is an IDT labelling of a connected
graph G, then f is also an IHT labelling of G.
Lemma 1 shows that a graceful labeling of G is also a
harmonious labelling of G [6].
Theorem 2. A connected graph G holds
(G)
+(G)
(G).
Lemma 3. Let Kn be a complete graph on n vertices,
Km,n be a complete bipartite graph on n+m vertices; Wn be
a wheel, Fn be a fan, Hn be a helm, Pn a path and Cn a
cycle on n vertices, respectively
1)
(Kn)=
(2)(n) and n+3
(Kn) for n5.
2)
(Km,n)=m+n1.
3)
(W4)=4,
(F5)=5 and
(Wn)=n1 for n 6.
4)
(Fn)=n1.
5)
(H2n-1)=n1 for n 8, especially,
(H2n-1)=7 for
n= 4,5,6, 7.
6)
(Pn)=2 for n=3,4, and
(Pn)=3 for n5.
7)
(Cn)=4 for n=4,5, and
(Cn)=3 for n6.
8) Cartesian product graphs PmPn, mn hold
(P2Pn)=3,
(PmPn)=3 for m3.
The number
(G) can be referred to the partly an-
tiaverage number for f(u)+f(v)2f(w) in f(V(G)). Since
(Fn)=n1, however, the color set f(V(Fn))=[0, n1] is
not an antiaverage n-set at all. Another instance is that
(K5)=8. It is easy to test
(K5uv)=6, where the graph
K5uv is obtained by deleting an edge uv from K5, using
a coloring f: V(K5uv){0,1,3,4,6} such that f(u)=6 and
f(v)=3. Therefore, we say that the color set f(V(G)) is
partly antiaverage. Because diameters D(G+H)2 and
D(Km,n)=2, and any bipartite graph G is a subgraph of a
certain bipartite complete graph Km,n. We have
Corolla ry 4. ( i) For the join graph G+H of two graph s
G and H, |V(G)|+|V(H)| 1
(G+H)
(2)(V(G)|+|V(H)|).
ii) Let K(G) and Ks,t be the order of the largest clique
and a bipartite subgraph of a (p,q)-graph G respectively.
Then max{
(2)(K(G)), s+t1}
(G)
(2)(p).
iii) For a bipartite graph G,
(G)|V(G)| 1.
Theorem 5. Let G be a (p,q)-graph. Th en
(G) p2,
otherwis e 2q
(G) or 2q1
(G).
Theorem 6. Let T be a tree. Then
(T)
(T)(T)+1,
and the bounds are tight. Furthermore, T has a strong
(k,s,t)-IDT labelling such that t=
'(T).
Theorem 7. A connected uniquely cycle graph H
holds (H)+1
(H)(H)+2.
Corolla ry 8. Let T be a tree with maximum degree ,
then
(T(Kd))=
(2)(+1), and
(T(Hu,d))
(2)(+1).
For a subset S of V(G) whose cardinality |S| 2, we say
S a k-distance set of G if the distance dG(u,v)=k for any
pair of two vertices u,vS. If mutually disjoint k-distance
sets V1, V2,,Vn of G satisfies
11
(|| 1)(|| 1)
nm
i
ij
VS

j

(1)
for any group of disjoint k-distance sets S1, S2,,Sm of G,
thus, we can write

1(|| 1)
n
ki
i
GV
and call this number the k-distance number of G, and V1,
V2,,Vn is a largest group of disjoint k-distance sets in G.
It should be pointed out that there may be n<m in (1), the
cycle C10 is such an example. In the following argument,
we use nk(G) to indicate n in k(G).
Observation 3. (i) Since a k-distance set Vi satisfies
|Vi| 2, so nk(G) |V(G)|/2.
(ii) Clearly,
(Gm)=p
m+1(G) for m 1.
(iii)
k(G)=0 for k 3 if and only if the diameter D(G)
2.
Theorem 9. Let G be a connected (p,q)-graph with
diameter D(G) 3, then
(G)
(2)(
(G2)).
Corollary 10. (i) Let Si be a 3-distance set of a con-
nected (p,q)-graph G for each i[1,s]. Le
1||
s
i
i
np S

and k=max{| Si |: i[1,s]}, so GK(n;sk) and then
(G)
(2)(n+k).
ii) If G is a connected (p,q)-graph with diameter D,
and let
n=p1(1)/
s
tDt
 3
where s=D/2, we have
(G)
(2)(n+s). Coloring
square graphs is related with the frequency assign prob-
lem, also is one of distance constrained labelings. Mi-
chael Molloy and M. R. Salavatipour (2005) announced:
(G2)5(G)/3+78 for a planar graph G. In [8], Lih
and Wang have shown: If (G)3 in an outerplanar
graph G, then
(G2)(G)+2. If (G)7, then
(G2)=
(G)+1. Thereby, we have
Corollary 11. Let G be a planar and connected graph.
(i) Then
(G)
(2)(5(G)/3+78).
(ii) If G is outerplanar,
(G)
(2)((G)+1) for (G)7,
(G)
(2)((G)+2) otherwise.
3. Conclusions and Future Works
We wish applying
(G) to approach some well-defined
graph colorings, for example,
(G2)
(G)
(2)(
(G2)).
We also define
n(G) to set
(Gm)=|G|
m+1(G), but
n(G)
is not easy to be valued. In [14], it has been known that
(2)(3)=3,
(2)(4)=4,
(2)(5)=8,
(2)(6)=10,
(2)(7)=12,
(2)(8)=13,
(2)(9)=19 and
(2)(10)=23. It reveals to be not
(2)
easy to gain the precise values of
(n). We propose
Copyright © 2013 SciRes. CN
B. YAO ET AL.
Copyright © 2013 SciRes. CN
68
nds
of et G be a graph on n vertices, there is
et integer n 5. An IDT labelling f
is
phs
w
et G be a planar graph, then
1
say a tree T belongs to Class 1 if
C
lin
4. Acknowledgements
y the National Natural Sci
REFERENCES
[1] Jogen Bang-Je, “Digraphs Theory
tions of num-
Problem 1. Determine or seek some efficient bou
Alg
(2)(n) for n5.
Conjecture 2. L
ber
(G) 3(n2).
Problem 3. Lof Kn
optimal if max f(V(Kn))=
(2)(n) since
(Kn)=
(2)(n).
Let Cf (u)={|f(u)f(x)|: xN(u)}. Wether Cf (u)Cf (v) for
all uvE(Kn) under an optimal IDT labelling f of Kn?
Our works show that some special classes of gra
hich suppo r t Co nj ectur e 4 , such as trees, uniquely cycle
graph, Ha l i n g raphs.
Conjecture 4. L
(G)(G)+3 and,
(G) (G)+2 if girth g(G) 5.
Conjecture 5. For every cubic graph G, then (G)+
(G) (G)+3.
Problem 6. We
(T)=(T), otherwise it is in Class 2, i.e.,
(T)=(T)+1.
haracterize structures of trees in Class 1, or in Class 2.
It may be interesting to consider the averaged label-
g of graphs. For a proper vertex coloring f of a
(p,q)-graph G, f: V(G)[0,q-1], if a path P=uwv of G
satisfies f(u)+f(v)=2f(w), we say P an averaged path, and
use the symbol
f (G) to denote the number of all aver-
aged paths in G. Find the maximum number p
(G) of
f(G) spanning over all vertex colorings.
This research is supported b -
ence Foundation of China in Grant No. 61163054 and
Grant No. 61163037, and Research Projects of Graduate
Teacher of Gansu University No. 1216-01. We thank
Yuan Yao (Support Center of Cooperative Communica-
tion and Operation of China Telecom, Hangzhou, 310016,
CHINA) for his useful sug ges tions of net wor k s.
nsen and Gregory Gutin,
orithms and Applications,” Springer-Verlag. Berlin
Heidelberg, New York, London, Paris, Tokyo, Hong
Kong, Barcelona, Budapest, August 2007.
[2] G.S. Bloom and S.W. Golomb, “Applica
ed undirected graphs,” Proc. IEEE, 65 (1977) 562-570.
doi:10.1109/PROC.1977.10517
[3] J.A. Bondy and U.S.R. Murty, “Graph Theory with Ap-
teger Sets with
ng, Bing Yao, Xiang-en Chen and Zhong-fu
raph Label-
Kaptcianos, “A Graph Theoretical Approach to
e Square
w
plication,” Macmillan, New York, 1976.
[4] Bela Bollobas and Oleg Pikhurko, “In
Prescribed Pairwise Differences Being Distinct,” pre-
printed
[5] Hui Che
Zhang, “On Graceful Generalized Spiders and Caterpil-
lars,”. Ars Combinatoria 87 (2008), 181-191.
[6] Joseph A. Gallian, “A Dynamic Survey of G
ing,” The electronic journal of combinatorics, 14 (2009),
# DS6.
[7] Jonathan
DNA Fragment Assembly,” American Journal Of Un-
dergraduate Research, VOL. 7, NO. 1 (2008)
[8] Ko-Wei Lih and Wei-Fan Wang, “Coloring Th
of An Outerplanar Graph,” Taiwanese Journal of Ma-
thematics, Vol. 10, No. 4 (2006), 1015-1023.
[9] Pevzner P.A., Tang H., and Waterman M.S, “A Ne
Approach to Fragment Assembly in DNA Sequencing,”
RECOMB 01 (2001), 256-267.
doi:10.1145/369133.369230
[10] Alexander Rosa, “On certain valuations of the vertices of
P.D. Vestergaard, “\alpha_k$- and
a graph,” Theory of Graphs (Internat. Symposium, Rome,
July 1966), Gordon and Breach, N. Y. and Dunod Paris
(1967), 349-355.
[11] J. Topp and
$\gamma_k$-stable graphs,” Discrete Mathematics 212
(2000), 149-160. doi:10.1016/S0012-365X(99)00216-2
[12] Yao Bing, Ming Yao, Hui Cheng, Jin-wen Li, Ji-guo Xie
and Hui Cheng, “On Generalized
and Zhong-fu Zhang, “On Felicitous Labelling of Trees,”
Proceeding of The 4th International Workshop on Graph
Labeling (IWOGL 2008), Harbin Engineering University
and University of Ba llarat, Australia, January, 2008, 5-8.
[13] Bing Yao, Hui Cheng, Ming Yao and Meimei Zhao, “A
Note on Strongly Graceful Trees,” Ars Combinatoria 92
(2009), 155-169.
[14] Bing Yao, Ming Yao
Antiaverage Problem,” Ars Combinatoria Volume XCVI,
July, 2010.