Paper Menu >>
Journal Menu >>
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) Copyright © 2013 SciRes. 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. Email: yy}918@163.com 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 n2 (mod 4); Km,n when m,n>1; P2C2n+1; P2C2n; P3C2n+1; SmC2n+1; Kn if and only if n4; Pn+Km; the friendship graph (3) n C for n odd; PnC3; PnCn+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>m0. 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 uvE(G) is defined as f(uv)=f(u)+f(v) (mod q). If the edge label set {f(uv): uvE(G)}=[0,q1], then we say both G and f to be felicitous. For the purpose of simplicity, we write f(S)={f(x): xSV(G)} and f(E(G))={f(uv): uvE(G)}={f(u)+f(v) (mod q): uvE(G)} and fG={f(u)+f(v): uvE(G)} for a felicitous labelling f of a (p,q)-graph G throughout this paper. Very often, the labelling h(x)=qf(x) for each verte xV(G) is called the dual labelling of the labelling f. The notation S (mod q) stands for the set {x (mod q): xS} 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):vY}, 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): uX}<min{f(v): vY}, 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 fG=[b,b+q1] and fG (mod q)=[0,q1]. *This research is supported by the National Natural Science Foundation of China (No. 61163 054 and No. 61163037). Felicitous Labellings of Some Network Models Copyright © 2013 SciRes. JSEA 30 Let Gi be the ith copy of a (p,q)-graph G with p3 for i[1,n], n2. Every vertex u0V(G) has its correspond- ing vertices 0 i uV(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 vjV(H0) with one u^0jV(Gj) for j[1,n] is called an edge-symmetric graph, denoted as H1=H0,G. Clearly, the graph H1E(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+1E(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=TG such that H contains T and n edge-disjoint copies Gi of G with |E(HE(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) fG=[ , +q1] and fG (mod q)=[0,q1], where =min fG. (ii) The dual labelling g of f is also felicitous, and g(xy)=qf(xy) for each edge xyE(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 uV(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 uV(G1) and vV(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=TG is felicitous. In general, a near-symmetric graph TG 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 fK2,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)=i1 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,q1 such that V(Sk)=XkYk, 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,1V(Sk,1) and yk,1V(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)=[Mk(q+1)+1, Mk(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,1V(Sk) with xkV(T), and yk,1V(Sk) with x2nk+1V(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=TG 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) fK2,3=[2,5]; (b) fK3,3=[3,11]; (c) fK2,3=[4,9]; (d) fT=[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 Copyright © 2013 SciRes. JSEA 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 xyE(G) and uvE(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 fG=E<qEq, where E<q={f(x)+f(y)<q: xyE(G)} and Eq=fG\E<q. So min E<q= =min fG. By Defin ition \refdefn:definition11, fG (mod q)=[0,q1]. On the other hand, f(E(G))=E<qEq (mod q)=[0,q1], which implies fG=[ , +q1]. If Eq(mod q)[0,1], then | E <qEq (mod q)|q1; a contradiction. So we have E<q=[ , q1] and Eq (mod q)= [0, 1]. We show the assertion (ii). Notice that the dual label- ling g of f is defined as g(x)=qf(x) for xV(G). For every edge xyE(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,q1] according to f(E(G))=[0, q1]. For xyE(G), f(xy)=f(x)+f(y) if f(x)+f(y)q1, 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]=qf(xy). Therefore, g(xy)=g(x)+g(y) (mod q)=qf(xy) for xyE(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 fG=[b,b+q1] with b=min f(Y). Hence, gG=[2q(b+q1),2qb]=[qb+1,2qb], how- ever, qb +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,s1], g(xs)<g(y1), and g(yj)<g(yj+1) for j[1,t1] 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,k01] and g(yj)[k0,q1] for each edge xiyjE(G), so we have g(xi)+g(yj)[k0+1,k0+q2]. How- ever, the set [k0+1,k0+q2] contains at most (q2) num- bers, so [k0+1,k0+q2] (mod q)=[0,q2], which is con- trary with [0,q1]=g(E(G)). If g(x1)=0 and g(yt)<q, then we have g(xi)[0, k01] and g(yj)[k0, q1] for xiyjE(G), and furthermore g(xi)+ g(yj)[k0+1,k0+q2]. However, [k0+1, k0+q2] (mod q)=[0, k02][k0, q1] 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,s1], g(xs)<g(y1), and g(yj)<g(yj+1) for j[1,t1], 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 x1XV(G) with its corresponding vertex x'1X'V(G') together by an edge produces a bi- partite graph H with its bipartition (XH, Y H), where XH=XY' 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 uX, f(v)=a+qg'(v) for vY'; (2) f(y)=qa+1+g(y), yY; f(x)=2q+1g'(x), xX'. Notice that f(X)[0,a1], f(Y')={a+qg'(u):uY'}[a,q], f(Y)={qa+1+g(v):vY}[q+1,2qa+1], and f(X')={2q +1g'(v): vX'}[2qa+2, 2q+1]. Hence, f(V(H))[0, 2q+1]. Therefore, f is proper and holds f(XH)<f(YH). For each edge xiyjE(G)E(H), we have q+1f(xi)+f(yj)=qa+1+g(xi)+g(yj)2q. Correspondingly, for each edge x'iy'jE(G')E(H) which corresponds to the edge xiyjE(G), f(x'i)+f(y'j)=a+3q+1 [g'(x'i)+g'(y'j)], and furthermore 2q+2f(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 fG=[q+1,2q] and fG'=[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))= fG{f(x1x'1)} fG' (mod 2q+1)=[0,2q]. It is noticeable, f(xi)+f(x'i)=g(xi)+2q+1g'(x'i)=2q+1, which means f(xi)+f(x'i) (mod 2q+1)=0 for xiX and the corresponding vertex x'iX'; and f(yj)+ f(y'j)=qa+1 +g(yj)+a+qg'(y'j)=2q+1, f(yj)+ f(y'j) (mod 2q+1)=0 for yjY and the corresponding vertex y'jY'. So we can de- lete the edge x1x'1 from H, and then join xix1 (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 Copyright © 2013 SciRes. JSEA 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, si1], fi(xi, si)< fi(yi,1), and fi(yi,j)<fi(yi,j+1) for j[1, t i1], and furthermore fi(xi,1)=0 and fi (yi, ti)=qi according to Lemma 2. Thereby, we have fiGi={fi(x)+fi(y): xyE(Gi)}=[ai, a i+q1], where ai= fi(yi,1), i=1,2. Joining y1,t1Y1 with x2,1X2 by an edge produces a new bipartite graph H having the bipartition (X1 X2,Y1Y2). 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,iX1}[0,a11], f(X2)={f2(x2,l)+a1: x2,l X2}[a1,a1+a21], 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(X1X2) <f(Y1Y2) and f(V(H))[0,M+1]. We will show f(E(H))={f(u)+f(v)(mod M+1): uvE(H)}=[0, M]. Notice that fG1={f(u)+f(v):uvE(G1)E(H)}=[a1+a2,a1+a2+q1 1], fG2={f(x)+f(y):xyE(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, fH=[a1+a2,a1+a2+M] with a1+a2=min f(Y1Y2). Case A1. a1+a2<q2. From a1+a2<M+1 and a1+a2+q11< M+1, so f(E(G1))=fG1. Since fG2=[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,M1], f(E(G2)) =[0,q21]. Hence, we obtain (1). Case A3. a1+a2=q2+1. For fG1=[a1+a2,a1+a2+q11] =[q2+1,M], and f(E(G1))=[q2+1,M]. From fG2= [a1+a2+q1+1,a1+a2+M]=[M+2,q2+1+M], we have f(E(G2)) ={f(u)+f(v)(mod M+1):uvE(G2)}=[1,q2]. We obtain (1). Case A4. a1+a2 q 2+2. Since fG1=[a1+a2,M] [M+1,a1+a2+q11], we have f(E(G1))=[a1+a2,M][0, a1+a2q22], and f(E(G2))=[a1+a2q2,a1+a21], which means (1). Based on the facts f(X1)<f(X2)<f(Y1)<f(Y2), fH (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. |