Journal of Software Engineering and Applications, 2013, 6, 29-32
doi:10.4236/jsea.2013.63b007 Published Online March 2013 (http://www.scirp.org/journal/jsea)
29
Felicitous Labellings of Some Network Models*
Jiajuan Zhang1, Bing Yao1, Zhiqian Wang2, Hongyu Wang1, Chao Yang1, Sihua Yang1
1College of Mathematics and Statistics, Northwest Normal University, Lanzhou, 730070, China; 2School of Mathematics Physics and
Software Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China.
Received 2013
ABSTRACT
Building up graph models to simulate scale-free networks is an important method since graphs have been used in re-
searching scale-free networks. One use labelled graphs for distinguishing objects of communication and information
networks. In this paper some methods are given for constructing larger felicitous graphs from smaller graphs having
special felicitous labelling s , and some network models are shown to be felicitous.
Keywords: Felicitous Labelling; Set-Ordered Felicitous Labelling; Symmetric Graphs ;Trees
1. Introduction
Graphs have been used in researching scale-free net-
works ([4],[9]). Many graph models can be labelled for
distinguishing objects in communication networks.
Ichishma and Oshima [3] investigated the relationship
between partitional graphs and strongly graceful graphs
and partitional graph s and stron gly felicitou s graphs . Yao,
Chen, Yao and Cheng [6] show several relationships
among several well-known labellings including felicitous
labelling. In [1], among the graphs known to be felicitous
are: Cn except when n2 (mod 4); Km,n when m,n>1;
P2C2n+1; P2C2n; P3C2n+1; SmC2n+1; Kn if and only if
n4; Pn+Km; the friendship graph (3)
n
C for n odd;
PnC3; PnCn+3. It has been noticed that some felicitous
graphs in literature can be constructed, such as some
classes of felicitous trees are obtained in [5]. Graham and
Sloane [2] conjectured: Every tree is felicitous. We will
present several methods for constructing larger felicitous
graphs from smaller graphs having special felicitous la-
bellings, and show some network models to be felicitous,
such as edge-symmetric and near-symmetric graphs that
are related with some models of self-similar and hierar-
chical networks in current research of complex networks.
Standard terminology and notation of graph theory are
used here. Simple graphs are finite, undirected, no multi-
ple edges and loopless, unless otherwise specified. The
shorthand notation [m,n] stands for an integer set {m,
m+1,…, n} with n>m0. A (p,q)-graph is a simple graph
with p vertices and q edges. A proper labelling f of a
(p,q)-graph G is a mapping from V(G) to [m,n] such that
f(x)f(y) for distinct x,y V(G).
Definition 1 [1] Suppose that a (p,q)-graph G has a
proper labelling f: V(G)[0,q]. The edge label f(uv) of
each edge uvE(G) is defined as f(uv)=f(u)+f(v) (mod q).
If the edge label set {f(uv): uvE(G)}=[0,q1], then we
say both G and f to be felicitous.
For the purpose of simplicity, we write f(S)={f(x):
xSV(G)} and f(E(G))={f(uv): uvE(G)}={f(u)+f(v)
(mod q): uvE(G)} and fG={f(u)+f(v): uvE(G)} for a
felicitous labelling f of a (p,q)-graph G throughout this
paper. Very often, the labelling h(x)=qf(x) for each
verte xV(G) is called the dual labelling of the labelling f.
The notation S (mod q) stands for the set {x (mod q): xS}
for a set S of non-negative integers. For a set
[6,14]={6,7,8,9,10,11,12,13,14}, as an example, [6,14]
(mod 10) ={0 ,1,2 ,3,4 ,6,7 ,8,9 }, and [6 ,14] (bmod 7) =[0, 7];
for S={3,7,9,10,12,13}, then S (mod 9)={0,1,3,4,7}.
In [7] and [8], the authors introduced the set-ordered
graceful labellings and the set-ordered odd-graceful la-
bellings: Let (X,Y) be the bipartition of a bipartite
(p,q)-graph G. If G admits a (an odd-)graceful labelling f
such that max{f(u):u X}<min{f(v):vY}, then we call f
a emphset-ordered (odd-)graceful labelling, and denote
this case as f(X)<f(Y). Motivated from the above
set-ordered (odd-)graceful labellings we define a
set-ordered felicitous labelling as follows.
Definition 2. Let (X,Y) be the bipartition of a bipartite
(p,q)-graph G. If G admits a felicitous labelling f such
that max{f(u): uX}<min{f(v): vY}, then we call f a
set-ordered felicitous labelling and G a set-ordered fe-
licitous graph, and write this case as f(X)<f(Y), and f is
called an optimal set-ordered felicitous labelling if
fG=[b,b+q1] and fG (mod q)=[0,q1].
*This research is supported by the National Natural Science Foundation
of China (No. 61163 054 and No. 61163037).

Felicitous Labellings of Some Network Models
30
Let Gi be the ith copy of a (p,q)-graph G with p3 for
i[1,n], n2. Every vertex u0V(G) has its correspond-
ing vertices 0
i
uV(Gi) for i[1,n]. We have a so-called
root graph H0 on n vertices, where V(H0)={vi: i[1, n]}.
The graph H1 obtained by identifying one vertex vjV(H0)
with one u^0jV(Gj) for j[1,n] is called an
edge-symmetric graph, denoted as H1=H0,G. Clearly,
the graph H1E(H0) has n components that are isomor-
phic to G. From the definition of H1, we can get the
edge-symmetric graphs Hi+1=Hi,G for i[1,N] such
that each component of Hi+1E(Hi) is isomorphic to G.
Let T be a (n,m)-graph and let G be a (p,q)-graph. We
define a near-symmetric graph H=TG such that H
contains T and n edge-disjoint copies Gi of G with
|E(HE(T))|=nq, |H|np and i[1,n].
2. Results
Lemma 1. Suppose that a connected (p,q)-graph G has a
felicitous labelling f. Then
(i) fG=[
 ,  +q1] and fG (mod q)=[0,q1], where
 =min fG.
(ii) The dual labelling g of f is also felicitous, and
g(xy)=qf(xy) for each edge xyE(G) with f(xy)0. Fur-
thermore, f is (optimal) set-ordered felicitous when G is
bipartite, so is g.
Lemma 2. Suppose that a bipartite graph G admits
set-ordered felicitous labellings. Then each set-ordered
felicitous labelling of G satisfies that one vertex of G is
labelled by zero and another vertex of G is labelled by
the number of edges of G.
Lemma 3. Suppose that a bipartite (p,q)-graph G is
set-ordered felicitous, and G' is a copy of G. Joining a
vertex uV(G) with its corresponding vertex u'V(G')
produces a set-ordered felicitous graph.
Theorem 4. Let G1, G2 be two disjoint bip artite gr aphs
having optimal set-ordered felicitous labellings. Then
there exist vertices uV(G1) and vV(G2) such that the
graph obtained by joining u with v or by identifying u
with v into one vertex is optimal set-ordered felicitous.
Theorem 5. Let T be a set-ordered felicitous tree and
let G be a connected (p,q)-graph having optimal set-or-
dered felicitous labellings. The near-symmetric graph
H=TG is felicitous.
In general, a near-symmetric graph TG having fe-
licitous labellings may not be set-ordered felicitous. We
Figure 1. (a) An optimal set-ordered felicitous labelling f of
K2,3 with fK2,3=[4,9]; (b) the dual labelling of f; (c) a non-
set-ordered felicitous labelling of K2,3; (d) a non-set-ordered
felicitous labelling of a 2-star; (e) a felicitous labelling of K4.
define the following matchable graphs and compound
graphs. Let T be a set-ordered felicitous tree on 2n verti-
ces. T has a set-ordered felicitous labelling f such that
f(xi)=i1 for i[1,2n].
For each k[1,n], there exists a graph Sk having 2m
vertices and 2q edges with respect to integers m,q1 such
that V(Sk)=XkYk, where Xk={xk,j: j[1,m]} and Yk={yk,j:
j[1,m]}. Furthermore, Sk is connected or has just two
components if it is disconnected. If Sk has just two com-
ponents Sk,1 and Sk,2, then xk,1V(Sk,1) and yk,1V(Sk,2),
and we call xk,1, yk,1 the bases of Sk, and Sk is called a
matchable graph if there is a labelling g such that Sk sat-
isfies the following:
(1) g(xk,1)=k(q+1)+f(xk), k[1,n];
(2) g(xk,j)+g(yk,j)=M, j[1,2m], where M=2n(q+1)1;
(3) g(Sk)=[Mk(q+1)+1, Mk(q+1)+q][k(q+1)q,
k(q+1)1].
Write Sk =C(T;2m,2q; x
k,1, y k,1), k[1,n]=[1, |T|/2].
Then we can construct a compound graph T*=C[S1, S2,
, Sn; T] by identifying x
k,1V(Sk) with xkV(T), and
yk,1V(Sk) with x2nk+1V(T) for k[1,n]; and by identi-
fying those vertices with the same labels in S2, S4, , S2z,
where z=[n/2]. It follows Theorem 5 that every com-
pound graph is felicitous.
Corollary 6. Every compound graph T*=C[S1, S2, ,
Sn; T] is felicitous.
Lemmas 2, 3 and Theorem 4 can be applied to con-
struct matchable graphs by the way used in the proof of
Theorem 5. It is noticeable, some compound graphs
T*=C[S1, S2, , Sn;T] having felicitous labellings are not
bipartite. If trees T holds |T|8, then a near-symmetric
graph H=TG is just an edge-symmetric graph H=T,
G. Figueroa-Centeno, Ichishima, and Muntaner-Batle [1]
define a felicitous graph to be strongly if there exists an
integer k such that every edge uv of the graph holds
min{f(u), f(v)}k<max{f(u), f(v)}.
Theorem 7. A connected graph G admits a strongly
felicitous labelling h if and only if h is a set-ordered fe-
licitous labelling.
Figure 2. Four graphs having optimal set-ordered felicitous
labellings. (a) fK2,3=[2,5]; (b) fK3,3=[3,11]; (c) fK2,3=[4,9];
(d) fT=[7,19].
Figure 3. Based on the graphs shown in Figure 2, two opti-
mal set-ordered felicitous graphs are used for illustrating
Theorem 4.

Felicitous Labellings of Some Network Models
31
Figure 4. Based on the graphs shown in Figure 2, two opti-
mal set-ordered felicitous graphs are used for illustrating
Theorem 4.
3. Conclusion
It may be meaning to consider the follo wing prob lems.
(1) Determine simple graphs having (optimal)
set-ordered felicitous labellings.
(2) If a connected graph G has a set-ordered felicitous
labeling f, then is f optimal?
(3) A simple graph G has a felicitous labelling f. Do
there exist edges xyE(G) and uvE(Gc) such that f is
still a felicitous labelling of the graph G xy+uv?
(4) Is a matchable graph felicitous?
Proof of Lemma 1. To show the assertion (i), we can
see fG=E<qEq, where E<q={f(x)+f(y)<q: xyE(G)}
and Eq=fG\E<q. So min E<q=  =min fG. By Defin ition
\refdefn:definition11, fG (mod q)=[0,q1]. On the other
hand, f(E(G))=E<qEq (mod q)=[0,q1], which implies
fG=[  ,  +q1]. If Eq(mod q)[0,1], then | E
<qEq
(mod q)|q1; a contradiction. So we have E<q=[  , q1]
and Eq (mod q)= [0,  1].
We show the assertion (ii). Notice that the dual label-
ling g of f is defined as g(x)=qf(x) for xV(G). For
every edge xyE(G) we have g(x)+g(y)+f(x)+f(y)=2q.
Hence, g(xy)+f(xy)=q for f(xy)0. Since f(x)+f(y)=q if
f(xy)=0, so g(x)+g(y)=q, which means g(xy)=0 (mod q).
Therefore, g(E(G))=[0,q1] according to f(E(G))=[0,
q1]. For xyE(G), f(xy)=f(x)+f(y) if f(x)+f(y)q1, we
have g(x)+g(y)=2q[f(x)+f(y)]=q+q f(xy); and f(xy)=
f(x)+f(y)q if f(x)+f(y)>q, so
g(x)+g(y)=2q[f(x)+f(y)]=2q[f(x)+f(y)q+q]=qf(xy).
Therefore, g(xy)=g(x)+g(y) (mod q)=qf(xy) for
xyE(G) and f(xy)0. If G is bipartite, let (X,Y) be the
bipartition of G. Suppose that f is set-ordered felicitous,
that is, f(X)<f(Y). Clearly, g(Y)<g(X). If f is optimal
set-ordered felicitous, so fG=[b,b+q1] with b=min f(Y).
Hence, gG=[2q(b+q1),2qb]=[qb+1,2qb], how-
ever, qb +1=min g(X). The proof of the assertion (ii) is
over.
Proof of Lemma 2. Let G be a bipartite connected
(p,q)-graph that admits a set-ordered felicitous label-
ling g. For the bipartition (X,Y) of V(G), where X={xi:
i[1,s]} and Y={yj: j[1,t]} with s+t=p, without loss of
generality, we let g(xi)<g(xi+1) for i[1,s1], g(xs)<g(y1),
and g(yj)<g(yj+1) for j[1,t1] by the choice of the label-
ling g.
Assume that g(x1)> 0 and g(yt)<q. Let k0=g(y1). Since
g(xi)[1,k01] and g(yj)[k0,q1] for each edge
xiyjE(G), so we have g(xi)+g(yj)[k0+1,k0+q2]. How-
ever, the set [k0+1,k0+q2] contains at most (q2) num-
bers, so [k0+1,k0+q2] (mod q)=[0,q2], which is con-
trary with [0,q1]=g(E(G)). If g(x1)=0 and g(yt)<q, then
we have g(xi)[0, k01] and g(yj)[k0, q1] for
xiyjE(G), and furthermore g(xi)+ g(yj)[k0+1,k0+q2].
However, [k0+1, k0+q2] (mod q)=[0, k02][k0, q1]
contradicts with the choice of the labelling g. The proof
of the lemma is complete.
Proof of Lemma 3. Let G be a (p,q)-graph described
in the theorem’s hypothesis, and let (X,Y) be the biparti-
tion of V(G), where X={xi: i[1,s]} and Y={yj: j[1,t]}
with s+t=p. G admits a set-ordered felicitous labelling g
with g(xi)<g(xi+1) for i[1,s1], g(xs)<g(y1), and
g(yj)<g(yj+1) for j[1,t1], and g(x1)=0 and g(yt)=q by
Lemma 2.
Let G' b e a copy of G with its bipartition (X',Y'), wher e
X'={ x'i: i[1,s]} and Y'={ y'j: j[1, t]} are the copies of X
and Y, and let g' be a copy of g with g'(x'1)=0 and g(y't)=q.
Joining the vertex x1XV(G) with its corresponding
vertex x'1X'V(G') together by an edge produces a bi-
partite graph H with its bipartition (XH, Y
H), where
XH=XY' and YH=X'Y. Let a=g(y1)=g'(y'1). Based on
two labellings g and g' we define a labelling f of H as:
(1) f(u)=g(u) for uX, f(v)=a+qg'(v) for vY';
(2) f(y)=qa+1+g(y), yY; f(x)=2q+1g'(x), xX'.
Notice that f(X)[0,a1],
f(Y')={a+qg'(u):uY'}[a,q],
f(Y)={qa+1+g(v):vY}[q+1,2qa+1], and f(X')={2q
+1g'(v): vX'}[2qa+2, 2q+1]. Hence, f(V(H))[0,
2q+1]. Therefore, f is proper and holds f(XH)<f(YH). For
each edge xiyjE(G)E(H), we have
q+1f(xi)+f(yj)=qa+1+g(xi)+g(yj)2q.
Correspondingly, for each edge x'iy'jE(G')E(H)
which corresponds to the edge xiyjE(G),
f(x'i)+f(y'j)=a+3q+1 [g'(x'i)+g'(y'j)], and furthermore
2q+2f(x'i)+f(y'j)3q+1. Clearly, f(xi)+f(yj)<f(x'i)+f(y'j) for
each edge xiyj and its corresponding edge x'iy'j in H. We
obtain fG=[q+1,2q] and fG'=[2q+2,3q+1]. Hence,
f(E(G))=[q+1,2q], f(E(G'))=[1,q]. Since
f(x1)+f(x'1)=g(x1)+2q+1 g'(x'1)=2q+1,
so f(x1x'1)=f(x1)+f(x'1)(mod 2q+1)=0. Thereby, f is
set-ordered felicitous because
f(E(H))= fG{f(x1x'1)}  fG' (mod 2q+1)=[0,2q].
It is noticeable, f(xi)+f(x'i)=g(xi)+2q+1g'(x'i)=2q+1,
which means f(xi)+f(x'i) (mod 2q+1)=0 for xiX and the
corresponding vertex x'iX'; and f(yj)+ f(y'j)=qa+1
+g(yj)+a+qg'(y'j)=2q+1, f(yj)+ f(y'j) (mod 2q+1)=0 for
yjY and the corresponding vertex y'jY'. So we can de-
lete the edge x1x'1 from H, and then join xix1 (resp. yj)
with its corresponding vertex x'i (resp. y'j) by an edge
together for i[2,s] (resp. j[1,t]) such that the resulting

Felicitous Labellings of Some Network Models
32
graphs are set-ordered felicitous. The lemma is covered.
Proof of Lemma 4. Let (Xi,Yi) be the bipartition of
vertices of a bipartite (pi,qi)-graph Gi for i=1,2, where
Xi={xi,j:j[1, si]}, and Yi={yi,j:j[1,ti]}, si+ti=pi. For i=1,2,
let fi be an optimal set-ordered felicitous labelling of Gi
with fi(xi,j)< fi(xi,j+1) for j[1, si1], fi(xi, si)< fi(yi,1), and
fi(yi,j)<fi(yi,j+1) for j[1, t
i1], and furthermore fi(xi,1)=0
and fi (yi, ti)=qi according to Lemma 2. Thereby, we have
fiGi={fi(x)+fi(y): xyE(Gi)}=[ai, a
i+q1], where ai=
fi(yi,1), i=1,2. Joining y1,t1Y1 with x2,1X2 by an edge
produces a new bipartite graph H having the bipartition
(X1 X2,Y1Y2). Clearly, |V(H)|=p1+p2, |E(H)|=q1+q2+1.
Let M=q1+q2. We extend the labellings f1, f2 to a labeling
f of H in the following way:
(1) f(x1,i)=f1(x1,i) for x1,i X1 and i[1,s1];
(2) f(x2,l)=f2(x2,l)+a1 for x2,l X2 and l[1,s2];
(3) f(y1,j)=f1(y1,j)+ a2 for y1,j Y1 and j[1,t1];
(4) f(y2,k)=f2(y2,k)+q1+1 for y2,k Y2 and k[1, t2].
Clearly, f(X1)={f1(x1,i): x1,iX1}[0,a11],
f(X2)={f2(x2,l)+a1: x2,l X2}[a1,a1+a21],
f(Y1)={f1(y1,j)+ a2: y1,j Y1}[a1+a2, a2+q1], and
f(Y2)={ f2(y2,k)+q1+1: y2,k Y2}[a2+q1+1,M+1].
More details, f(X1)<f(X2)<f(Y1)<f(Y2) in H, so f(X1X2)
<f(Y1Y2) and f(V(H))[0,M+1]. We will show
f(E(H))={f(u)+f(v)(mod M+1): uvE(H)}=[0, M]. Notice
that fG1={f(u)+f(v):uvE(G1)E(H)}=[a1+a2,a1+a2+q1
1], fG2={f(x)+f(y):xyE(G2)}=[a1+a2+q1+1,a1+a2+M],
f(y1,t)+f(x2,1)=f1(y1,t)+a2+f2(x2,l)+a1=f1(y1,t)+a1+a2=q1+a1
+a2. Therefore, fH=[a1+a2,a1+a2+M] with a1+a2=min
f(Y1Y2).
Case A1. a1+a2<q2. From a1+a2<M+1 and
a1+a2+q11< M+1, so f(E(G1))=fG1. Since
fG2=[a1+a2+q1+1, M] [M+1,a1+a2+M],
f(E(G2))=[a1+a2+ q
1+1,M][0,a1+a2 1]. Thereby, we
have
f(E(H))=f(E(G1))f(E(G2)){q1+a1+a2}=[0,M]. (1)
Case A2. a1+a2=q2. Then f(E(G1))=[q2,M1], f(E(G2))
=[0,q21]. Hence, we obtain (1).
Case A3. a1+a2=q2+1. For fG1=[a1+a2,a1+a2+q11]
=[q2+1,M], and f(E(G1))=[q2+1,M]. From fG2=
[a1+a2+q1+1,a1+a2+M]=[M+2,q2+1+M], we have f(E(G2))
={f(u)+f(v)(mod M+1):uvE(G2)}=[1,q2]. We obtain (1).
Case A4. a1+a2 q
2+2. Since fG1=[a1+a2,M]
[M+1,a1+a2+q11], we have f(E(G1))=[a1+a2,M][0,
a1+a2q22], and f(E(G2))=[a1+a2q2,a1+a21], which
means (1).
Based on the facts f(X1)<f(X2)<f(Y1)<f(Y2), fH (mod
M+1)=[0,M] and f(V(H)) [0,M+1], and by the assertion
(i) of Lemma 1 and by the definition of an optimal
set-ordered felicitous labelling, we conclusion that f is
optimal set-ordered felicitous.
The proof of Lemma 4 is complete.
REFERENCES
[1] J. A. Gallian. A Dynamic Survey of Graph Labeling. The
lectronic journal of combinatorics, 17 (2010), # DS6.
[2] Graham R J, Sloane N J A. On additive bases and harmo-
nious graphs. SIAM J Algebraic Discrete Mathods, 29(1)
(1980), 382-404.
[3] Rikio Ichishma and Akito Oshima. On partitional and
other related graphs. preprint.
[4] Li L., Alderson D., Tanaka R., Doyle J.C., and Willinger,
W. Towards A Theory Of Scale-Free Graphs: Definition,
Properties, And Implications. Internet Mathematics 2 (4)
(2005), 431-523.
[5] Bing Yao, Ming Yao, Hui Cheng, Jin-wen Li, Ji-guo Xie
and Zhong-fu Zhang. On Felicitous Labelling of Trees.
The proceeding of The 4th International Workshop on
Graph Labeling (IWOGL 2008), Harbin Engineering
University and University of Ballarat, Australia, January,
2008. pp5-8.
[6] Bing Yao, Xiang'en Chen, Ming Yao, Hui Cheng. On (k,
 )-magically total labeling of graphs. submitted to
JCMCC.
[7] Bing Yao, Hui Cheng, Ming Yao and MeiMei Zhao. A
Note on Strongly Graceful Trees. Ars Combinatoria 92
(2009), 155-169.
[8] Xiangqian Zhou, Bing Yao, Xiang'en Chen, and Haixia
Tao. A proof to the odd-gracefulness of all lobsters. Ars
Combinatoria, Volume CIII, January (2012),13-18.
[9] Bing Yao, Xiang'en Chen, Xiangqian Zhou,Jiajuan Zhang,
Xiaomin Zhang, Ming Yao, Mogang Li, Jianming Xie.
Graphs Related With Scale-free Networks. Proceeding of
The 2nd International Conference on Electronics, Com-
munications and Control (ICECC2012), October, 2012,
Zhoushan, China, 284-287.