Graph labelings with restrictive conditions

G aph labelings wi h es ic i e condi ions PhD Thesis Egye emi Dok o i (PhD) é ekezés Ve onika Halász Supe iso /Téma eze ő D . Zsol Tuza Uni e si y o Deb ecen PhD School in In o ma ics Deb eceni Egye em Te mésze udományi Dok o i Tanács In o ma ikai Tudományok Dok o i Iskola Deb ecen, 2015 Ezen é ekezés a Deb eceni Egye em Te mésze udományi Dok o i Tanács In o ma ikai Tudományok Dok o i Iskola Elméle i számí ás udomány, ada - édelem és k ip og á ia p og amja ke e ében készí e em a Deb eceni Egye- em e mésze udományi dok o i (PhD) okoza ának elnye ése céljából. Deb ecen, 2015. ................... Halász Ve onika Tanúsí om, hogy Halász Ve onika dok o jelöl 2011-2014 közö a en megne- eze Dok o i Iskola p og amjának ke e ében i ányí ásommal égez e mun- kájá . Az é ekezésben oglal e edményekhez a jelöl önálló alko ó e ékeny- ségé el megha á ozóan hozzájá ul . Az é ekezés el ogadásá ja asolom. Deb ecen, 2015. ................... D . Tuza Zsol éma eze ő G aph labelings wi h es ic i e condi ions É ekezés a dok o i (PhD) okoza megsze zése é dekében az in o ma ika udományágban í a: Halász Ve onika okle eles ma ema ikus Készül a Deb eceni Egye em In o ma ikai Tudományok Dok o i Iskolája Elméle i számí ás udomány, ada édelem és k ip og á ia p og amja ke e ében. Téma eze ő: D . Tuza Zsol A dok o i szigo la i bizo ság: elnök: D . ......................................... agok: D . ......................................... D . ......................................... A dok o i szigo la időpon ja: 2014. ................................. Az é ekezés bí álói: D . ......................................... D . ......................................... A bí álóbizo ság: elnök: D . ......................................... agok: D . ......................................... D . ......................................... D . ......................................... D . ......................................... Az é ekezés édésének időpon ja: 2015. .............................. Con en s I In oduc ion 1 II Theo y o dis ance-cons ained labeling 2 1 Ea lie esul s and backg ound 2 1.1 Some known bounds and exac alues o λ2,1,λj1,j2,λ3,2,1and λj1,j2,j3................... 6 1.1.1 T ees............................ 6 1.1.2 Pa hs ........................... 7 1.1.3 Cyles o o de n≥3................... 8 1.1.4 Wheels........................... 8 1.1.5 Plana g aphs....................... 9 1.1.6 Cho dal g aphs . . . . . . . . . . . . . . . . . . . . . . 10 1.1.7 Ca esian p oduc o g aphs . . . . . . . . . . . . . . . 12 1.1.8 The c oss-p oduc o pa hs and cycles . . . . . . . . . . 13 1.1.9 Gene alized Pe e sen g aphs . . . . . . . . . . . . . . . 14 1.2 Bounds on o he pa ame e s . . . . . . . . . . . . . . . . . . 15 1.2.1 Bounds om he ch oma ic numbe . . . . . . . . . . . 15 1.2.2 Bounds on he pa h co e ing numbe . . . . . . . . . . 15 1.3 Rela edp oblems......................... 16 1.3.1 Thesize.......................... 16 1.3.2 Theedgespan....................... 17 1.3.3 C i ical g aphs . . . . . . . . . . . . . . . . . . . . . . 18 1.3.4 (p, q)− o allabeling ................... 18 1.3.5 Algo i hmic complexi y . . . . . . . . . . . . . . . . . . 20 1.3.6 Radionumbe ....................... 21 III New heo e ical esul s in dis ance-cons ained labeling 23 2 Radio labeling o le el-wise egula ees 23 2.1 Lowe bounds om weigh ed powe s o g aphs . . . . . . . . . 25 2.2 Lowe bound o le el-wise egula ees . . . . . . . . . . . . . 27 2.3 Tigh ness o he lowe bound . . . . . . . . . . . . . . . . . . 30 2.4 A u he open p oblem . . . . . . . . . . . . . . . . . . . . . 34 2.5 In e nally egula ees s. comple e m−a y ees . . . . . . . 36 2.6 Algo i hm............................. 37 3L(j, j −1, ..., 2,1)–labeling o uni in e al g aphs 38 3.1 Ci cula L(j, j −1, ..., 2,1)−labeling o pa hs . . . . . . . . . . 38 3.2 An uppe bound o he L(j, j −1, ..., 2,1)−labeling numbe o uni in e al g aphs . . . . . . . . . . . . . . . . . . . . . . 39 IV Applica ion o Combina o ial Op imiza ion Me h- ods 43 4 New model o he equency assignmen p oblem 43 4.1 Linea p og amming and in ege p og amming . . . . . . . . . 43 4.2 Models o compu ing dis ance-cons ained labelings . . . . . . 44 4.2.1 In ege p og amming o mula ion o he L(j1, j2, ..., js)– p oblem .......................... 44 4.3 Newmodel ............................ 45 4.4 Tes ins ances .......................... 46 4.5 Fi s compu a ional expe imen s . . . . . . . . . . . . . . . . . 48 4.6 Model imp o emen s . . . . . . . . . . . . . . . . . . . . . . . 50 4.6.1 Reducing he alue o M................. 50 4.6.2 S eng hening he model . . . . . . . . . . . . . . . . . 53 V Ano he ype o g aph pa i ion 57 5 Edge decomposi ions 57 5.1 Thep oblems ........................... 57 5.2 Ea lie esul s........................... 58 5.3 Thenew esul s.......................... 59 6 Summa y 67 1.1 Some known bounds and exac alues o λ2,1,λj1,j2,λ3,2,1and λj1,j2,j3 1.1.1 T ees De ini ion A cycle is a closed walk wi h no epe i ions o e ices and edges, o he han he epe i ion o he s a ing and ending e ex. De ini ion A g aph is called a ee i i con aines no cycles. In a ee any wo o i s e ices a e connec ed by exac ly one simple pa h. •∆+1≤λ2,1(T)≤∆+2[2] In [9] Chang and Kuo p esen an algo i hm o he decision be ween ∆+1 and ∆+2. This algo i hm is applicable o λj1,1(T), whose alue is be ween ∆ + j1−1and min{2∆ + j1−2,∆ + 2j1−2}[10]. Bu o ex end i o de e mine λj1,j2(T)wi h gene al j1and j2is NP-ha d. Howe e , Geo ges and Mau o [11] ga e he ollowing bounds: •j1+ (∆ −1)j2≤λj1,j2(T)≤j1+ (2∆ −2)j2, i j1 j2≥∆ In ano he pape [12] hey de e mined he alues o j1 j2<∆: •λj1,1,1(T) = ((∆ + j1−2) + ∆,i ∆ ≥j1 (∆ + j1−2) + j1,i ∆ < j1 . •I Tis an n−a y ee and i s heigh is a leas 3, hen λ3,2,1(T) = 2n+5. •2∆ + 1 ≤λ3,2,1(T)≤2∆ + 3. Lemma I Tis a oo ed ee wi h oo , hen he e is an ,(2∆ + 3) − L(3,2,1)−labeling o T, in which (u)≡d(u, ) (mod 2) o e e y u∈V(T). 6 1.1.2 Pa hs De ini ion A walk is a sequence 1,{ 1, 2}, 2,{ 2, 3}, 3, ..., { n−1, n}, n o e ices and edges be ween consecu i e e ices. De ini ion A pa h is an open walk wi h no epe i ions o e ices and edges. Pndeno es he pa h on n e ices. He e he mos impo an alues [6]: •λ2,1(Pn) =                0 2 3 4 i n= 1 i n= 2 i n= 3 o 4 i n≥5 . •λj1,j2(Pn) =                      0 j1 j1+j2 j1+ 2j2 2j1 i n= 1 i n= 2 i n= 3 o 4 i n≥5 and j1≥2j2 i n≥5 and j1≤2j2 . •λj1,1,1(Pn) =          j1 j1+ 1 j1+ 2 i n= 2 i n= 3 o 4 o he wise . •λ3,2,1(Pn) =            3,i n= 2 5,i n= 3 o 4 6,i n= 5,6 o 7 7,i n≥8 . 7 1.1.3 Cyles o o de n≥3 Cndeno es he cycle on n e ices. •[2] λ2,1(Cn) = 4. •[11] I j1 j2>2, hen λj1,j2(Cn) =                2j1 j1+ 2j2 2j1 j1+ 3j2 i nodd, n ≥3 i n≡0 (mod 4) i n≡2 (mod 4) and j1 j2≤3 i n≡2 (mod 4) and j1 j2>3 . •[11] I j1 j2≤2, hen λj1,j2(Cn) =          2j1 4j2 j1+ 2j2 i n≡0 (mod 3) i n= 5 o he wise . •[6] λj1,1,1(Cn) =            j1+ 2,i n≡0 (mod 4) j1+ 3,i n≡2 (mod 4),o n= 11 and j1= 2 6,i n= 7 and j1= 2 2j1o he wise . •[6] λ3,2,1(Cn) =                6,i n= 3 7,i ne en 8,i nodd and n6= 3; 7 9,i n= 7 . 1.1.4 Wheels De ini ion The wheel Wnis ob ained om Cnby adding a new e ex ad- jacen o all e ices in Cn. 8 •λ2,1(Wn) =    6 n+ 1 i n= 3 o 4 i n≥5 . 1.1.5 Plana g aphs De ini ion A g aph is called plana i i can be d awn in he plane in such a way ha no edges c oss each o he . De ini ion A g aph is called ou e plana i i is plana and i can be d awn in such a way ha all o i s e ices belong o he unbounded ace o he d awing. •[13] I Gis ou e plana , hen λ2,1(G)≤∆+8. •[14] The abo e bound was imp o ed o ∆+2 o ∆≥8and o 10 o he wise. •[13] I Gis ou e plana and cho dal (see de ini ion in he subsec ion “Cho dal g aphs”), hen λ2,1(G)≤∆+6. •[13] I Gis plana , hen λ2,1(G)≤3∆ + 28. •[15] λ2,1(G)≤8∆ −13, i ∆≥5. (I ∆≤8, hen 8∆ −13 <3∆ + 28 holds.) •[13] I Gis plana and cho dal, hen λ2,1(G)≤3∆ + 22. •[16] Gene al j1and j2: λj1,j2(G)≤         (2j2−1)∆ + 4j1+ 4j2−4,i g(G)≥7 (2j2−1)∆ + 6j1+ 12j2−9,i g(G)≥6 (2j2−1)∆ + 6j1+ 24j2−15,i g(G)≥5 , whe e g(G)deno es he gi h o G, he leng h o a sho es cycle con- ained in i . 9 1.1.6 Cho dal g aphs De ini ion A g aph is called cho dal i each induced cycle, con ained in i , has a mos h ee e ices. •[10] I Gis a cho dal g aph wi h maximum deg ee ∆, hen λj1,1(G)≤(2j1+∆−1)2 4. De ini ion A clique is a se o pai wise adjacen e ices in he g aph. A amous p ope y o cho dal g aphs [17] is ha hei e ex se has an o de ing V(G) = { 1, ..., n}such ha o any i, he neighbo s o iin { i+1, ..., n} o m a clique, Bi. And con e sely, g aphs wi h his p ope y a e p o ed o be cho dal. The men ioned o de ing is called simplicial o de o pe ec elimina ion o de . I is easy o see ha he ollowing g aph class is a subse o ha o he cho dal g aphs. De ini ion Gi en a posi i e in ege , − ees a e he g aphs ha a ise om a −clique (i.e. K ) by 0 o mo e i e a ions o adding a new e ex joined o a −clique in he g aph. [18] (A ee is a 1- ee.) •[10] I Gis a − ee wi h maximum deg ee ∆, hen λj1,1(G)≤(2j1−1+∆− )· . De ini ion A g aph is a pa ial − ee i i is a subg aph o a − ee. The eewid h o a g aph is he minimum alue o which he g aph is a pa ial − ee. Ano he de ini ion o eewid h can be in oduced as ollows. The wo de ini ions a e p o ed o be equi alen . De ini ion ee decomposi ion o a g aph G= (V, E)is a ee Twi h e - ices X1, ..., Xn, whe e each Xiis a subse o V, sa is ying he ollowing p ope ies: 10 •The union o all se s Xiequals V. Tha is, each g aph e ex is con- ained in a leas one ee e ex. •I Xiand Xlbo h con ain a e ex , hen all e ices Xko he ee in he (unique) pa h be ween Xiand Xlcon ain as well. Equi alen ly, he ee e ices con aining e ex o m a connec ed sub ee o T. •Fo e e y edge ( w)in he g aph, he e is a subse Xi ha con ains bo h and w. Tha is, e ices a e adjacen in he g aph only when he co esponding sub ees ha e a e ex in common. The wid h o a ee decomposi ion is he size o i s la ges se Ximinus 1. The eewid h w(G)o a g aph Gis he minimum wid h among all possible ee decomposi ions o G. In his de ini ion, he size o he la ges se is diminished by 1 in o de o make he eewid h o a ee equals 1. Equi alen ly, he eewid h o Gis 1 less han he size o he la ges clique in he cho dal g aph con aining Gwi h he smalles clique numbe . A cho dal g aph wi h his clique size may be ob ained by adding o Gan edge be ween e e y wo e ices ha bo h belong o a leas one o he se s Xi. •[13] Fo a g aph o eewid h , we ha e λ2,1≤(∆ + 2) · . De ini ion A e ex se is called independen i no wo o hem a e adjacen . De ini ion spli g aph is a g aph Gwhose e ex se can be spli in o wo se s Kand S, such ha Kinduces a clique and Sinduces an indepen- den se in G. (Spli g aphs a e cho dal.) •[13] I Gis a spli g aph, hen λ2,1(G)≤∆1,5+2∆+2, and o any ∆ he e is a spli g aph wi h λ2,1≥1 3·q2 3·∆1,5. (The essen ial poin o his esul is ha i gi es a nonlinea lowe bound.) De ini ion An n−sun is a cho dal g aph ha con ains a Hamil onian cy- cle (x1, y1, x2, y2, ..., xn, yn, x1) in which each xihas deg ee 2 and he e ices yi o m an n−clique. 11 Asun − ee (SF)/ odd −sun − ee (OSF)/ 3−sun − ee (3SF) cho dal g aph is a cho dal g aph con aining no n−sun wi h n≥3/ odd n≥3/n= 3 as an induced subg aph. •[10] I Gis an OSF-cho dal g aph, hen λj1,1≤j1·∆. •I Gis an SF-cho dal g aph, hen λj1,1≤∆ + (2j1−2)(χ(G)−1). De ini ion A g aph is called in e al g aph i i s e ices can be ep esen ed by an in e al o he eal line such ha wo e ices a e adjacen i and only i he wo co esponding in e als in e sec . Auni in e al g aph is an in e al g aph whose in e al ep esen a ion con- ains only in e als o he same leng h. The ollowing bounds a e known o uni in e al g aphs: •[19] λ2,1(G)≤2χ(G). •[20] λj1,j2(G)≤j1(χ(G)−1) + j2i j1>2j2, and 2j2·χ(G), i j1≤2j2. •[20]λj1,j2(G)≥max{j1(χ(G)−1), j2·λ1,1(G)}A linea - ime algo i hm is p oposed ha can L(j1, j2)−label a gi en uni in e al g aph using he la ges label no mo e han he bound abo e. 1.1.7 Ca esian p oduc o g aphs The Ca esian p oduc (GH) o he g aphs Gand His he g aph wi h e ex se V(GH) = V(G)×V(H)and edge se E(GH) = {(( , w),( 0, w0))| (( = 0)∧((w, w0)∈E(H))) ∨((( , 0)∈E(G)) ∧(w=w0))} F om [11] and [21] we ha e he ollowing s a emen s: Le Pibe a pa h o o de pi, o i= 1,2, ..., n, n ≥2.P:= P1P2...Pn. Then 12 •I pi≥3 o e e y i, and pi≥4 o a leas wo dis inc i-s, hen λ2,1(P) = 2n+ 2. •Suppose pn= 2 and pi≥3,1≤i≤n−1and i pi≥4 o a leas wo dis inc i-s, hen λ2,1(P) = 2n+ 1. •Suppose pi≥5 o each i. Then λj1,j2(P) = j1+ (4n−2)j2i j1 j2≥2n, and 2j1+ 2(n−1)j2≤λj1,j2(P)≤2j1+ (2n−1)j2i j1 j2<2n. Pis called an n−cube Qn, i pi= 2 o all i. We ha e he ollowing bounds o he L(2,1)−labeling numbe o Qn: •[2] λ2,1(Qn)≤2n+ 1. •[15] λ2,1(Qn)≥n+ 3. •Exac ly: λ2,1(Q3)=6,λ2,1(Q4)=7,λ2,1(Q5)=8. So he lowe bound is igh o n= 3,4and 5. •[21] λ2,1(Qn)≤2k−1 o n≤2k−k−1. •[21]λ2,1(Qn)≤2k+ 2k−q+1 −2 o 1≤q≤kand n≤2k−q. •[21] lim in λ2,1(Qn) n= 1. •[21] In gene al λ2,1(Qn)≤2n o all n≥2. (No ice ha his is an imp o emen o he esul om he i s one om [2].) •[2] 2n+ 3 ≤λ3,2,1(Qn)≤4n+ 3 i n≥3. 1.1.8 The c oss-p oduc o pa hs and cycles De ini ion The c oss-p oduc o he g aphs G1, G2, ..., Gkis he g aph, de- no ed by G1×G2×... ×Gk, wi h e ex se V(G1×G2×... ×Gk) = V(G1)×V(G2)×... ×V(Gk) 13 and edge se E(G1×G2×... ×Gk) = {(u1, u2, ..., uk)( 1, 2, ..., k)| ul, l∈V(Gl),(∀l: 1 ≤l≤k), (∃i: (ui i∈E(Gi)), (uj= j, i (j6=i)))}. Since he s uc u e o c oss-p oduc s o mos g aphs, in gene al hey a e no easy o deal wi h, he labeling p oblem has been s udied especially o pa hs and cycles, bu hese o gene al leng h. A lo o alues ha e been de e mined exac ly, he e he mos gene al ones a e p esen ed: •[22] λ3,2,1(P2×Pn) =          7i n= 2 8i n= 3; 4 9i n≥5 . •[22] λ3,2,1(Pm×Pn)≤11 i n≥m≥3, and λ3,2,1(P3×Pn)≤10 i n= 4 o 5. •[22] λ3,2,1(P3×Pn) =          9i n= 3 10 i n= 4; 5 11 i n≥6 . •[22] I n≥m≥4 hen λ3,2,1(Pm×Pn) = 11. •[23] λ3,2,1(Cm×Pn) = 11 i m≡0 (mod 4) and n≥3. •[23] λ3,2,1(Cm×Cn) = 11 i m≡0 (mod 4) and n≡0 (mod 12). 1.1.9 Gene alized Pe e sen g aphs The gene alized Pe e sen g aph o o de nis he 3- egula g aph wi h 2n (n≥3) e ices consis ing o wo disjoin n−cycles, called inne and ou e 14 cycles, such ha each e ex on he ou e cycle is adjacen o a (necessa ily unique) e ex on he inne cycle. This de ini ion was in oduced by Geo ges and Mau o. They ga e he ollowing bounds in [24]: •λ2,1(G)≤9, i Gis a gene alized Pe e sen g aph. •λ2,1(G)≤8, i Gis a gene alized Pe e sen g aph o o de g ea e han 12. •λ2,1(G)≤7, i Gis a gene alized Pe e sen g aph o o de 3≤n≤12 bu 6= 5. 1.2 Bounds on o he pa ame e s 1.2.1 Bounds om he ch oma ic numbe •[2] I Gis a g aph wi h n e ices, hen λ2,1(G)≤n+χ(G)−2. •[2] Fo any g aph G,λ2,1(G)≤∆2+ 2∆. •[2] I Gis a g aph wi h diame e 2, hen λ2,1(G)≤∆2. La e on some educ ions we e made on he second bound. These a e he ollowing in o de : ∆2+ ∆ in [9], ∆2+ ∆ −1in [25] and ∆2+ ∆ −2in [26]. A gene aliza ion o he same bound was gi en in [10], and his is he ollowing: λj1,1(G)≤∆2+ (j1−1)∆. 1.2.2 Bounds on he pa h co e ing numbe A pa h co e ing o G, deno ed by C(G), is a collec ion o e ex-disjoin pa hs in Gsuch ha each e ex in V(G)is inciden o a pa h in C(G). A minimum pa h co e ing o Gis a pa h co e ing o Gwi h minimum ca dinali y, and he pa h co e ing numbe c(G)o Gis he ca dinali y o a minimum pa h co e ing o G. We obse e ha he e exis s a Hamil onian pa h in Gi and 15 [43] and some Ca esian p oduc o some g aphs [44, 45, 46, 47, 48, 49]. A b ie summa y o he known esul s wi h he ela ed e e ences is gi en by he subsec ion 7.4 o he su ey [50]. In he p esen con ex he mos impo an ci a ions a e Liu’s pape [43] o a gene al lowe bound on he adio numbe o ees, and he wo k o Li, Mak ang Zhou [51] who de e mined he adio numbe o comple e m-a y ( oo ed) ees. 22 Pa III New heo e ical esul s in dis ance-cons ained labeling One s uc u e I deal wi h is he le el-wise egula ee. I ocused on he adio labeling o ees. The s uc u e o le el-wise egula ees is a o able o s udy since i helps ge ing sha p uppe bounds. I used exac ly his ea u e in o de o de e mine he alues ha I p esen wi h he associa ed p oo s in Sec ion 2. I used a simila ick o an o he g aph class as well, namely, o he uni in e al g aphs. Sec ion 3 is abou my esul s acco ding o hem. 2 Radio labeling o le el-wise egula ees Le el-wise egula ees As men ioned abo e, Li, Mak and Zhou de e - mined he adio numbe o comple e m-a y oo eed ees. E e y such ee has e en diame e , mo eo e he deg ee o i s oo is smalle (by 1) han ha o all he o he non-lea e ices. The e o e one o ou goals was o p o e a esul , analogous o he one o [51], o ees in which all in e nal e ices ha e he same deg ee and he diame e is un es ic ed. We es ablish his by conside ing a mo e gene al class o ees. In his way ou heo em also includes ha o o m≥3as a pa icula case. I is well known ha e e y ee T= (V, E)has a cen al e ex o a cen al edge 0 00, depending on he pa i y o he diame e diam(T). Se ing L0={ }i diam(T)=2his e en, and L0={ 0 00}i diam(T)=2h+ 1 is odd, e e y e ex o Tis a dis ance a mos h=1 2diam(T)apa om L0. De ine he le el se s o Tas Li={ ∈V|dis ( , L0) = i, o 1≤i≤h. The e ices ∈Liwill be e e ed o as i− e ices o i= 0,1,2, ..., h. The alue h ep esen s he heigh o he s uc u e wi h espec o he cen al 23 le el L0. This his ei he he adius o T(i diam(T) is e en) o he adius minus 1 (i diam(T) is odd). We say ha Tis le el-wise egula i all i− e ices ha e he same deg ee, say mi, o e e y i= 0,1,2, ..., h. In pa icula , a comple e m-a y ee is ep esen ed wi h he alues m0=m, m1=m2=... =mh−1=m+ 1 and mh= 1, while in e nally m− egula comple e ees a e ep esen ed wi h m0=m1=... =mh−1=mand mh= 1. No e ha all lea es a e a he same dis ance om L0in e e y le el-wise egula ee. We always ha e mh= 1 by de ini ion, hence a le el-wise egula ee o heigh his cha ac e ized by an o de ed h− uple (m0, m1, ..., mh−1). We use he no a ion T1 m0,m1,...,mh−1 o he ee uniquely iden i ied by (m0, m1, ..., mh−1) wi h |L0|= 1 (ha ing e en diame e 2h), and T2 m0,m1,...,mh−1 o he ee iden- i ied by (m0, m1, ..., mh−1) wi h |L0|= 2 (ha ing odd diame e 2h+ 1). In ei he case, he supe sc ip indica es he ca dinali y o L0. We de e mined he exac alue o λd,d−1,...,1(Tp m0,m1,...,mh−1)wi h p= 1,2 o e e y d≥1and o all le el-wise egula ees in which mi≥3holds o all 0≤i≤h−1whe e d= diam(T)and h=d 2. In pa icula , o in e nally egula comple e ees we ha e: Theo em 1 Le d≥3and m≥3be in ege s, and le h=d 2. Then o he in e nally (m+ 1)- egula comple e ees wi h diame e dand heigh h we ha e: (a) I d= 2h hen he comple e ee Twi h a cen al e ex and pa- ame e s m0=m+1 and m1=... =mh−1=mhas λd,d−1,...,1(T) = 1 + Pd 2−1 i=0 ((m+ 1) ·mi·(d−1−2i)) = mh+4mh+1−2hm2−4m+2h (m−1)2. (b) I d= 2h+ 1 hen he comple e ee Twi h a cen al edge and pa ame e s m0=m1=... =mh−1=mhas λd,d−1,...,1(T) = Pd−1 2 i=0 (2 ·mi·(d−2i)) −d= 2mh+6mh+1−2mh−(2h+1)m2−4m+2h+1 (m−1)2. I is in e es ing o compa e hese o mulas wi h he one de i ed in [51]; I shall pu some commen s o his kind in he concluding sec ion. 24 The ci ed esul s on pa hs and comple e bina y ees indica e ha allowing mi= 2 changes he p oblem in a subs an ial way and leads o di e en o - mulas. Ne e heless, we s a ed and p o ed he lowe bound unde he weake es ic ion mi≥2( ha is w i en in a la e pa ag aph), because some combi- na ions o la ge deg ees may s ill allow he o mula o be igh . I emains an open p oblem o u u e esea ch o analyze which h- uples (m0, m1, ..., mh−1) co espond o cases o equali y. 2.1 Lowe bounds om weigh ed powe s o g aphs The aim o he i s pa o his sec ion is o indica e a way how lowe bounds on n(G)and mo e gene ally on λj1,j2,...,jd(G)can be ob ained. The second pa applies he idea o le el-wise egula ees. In a la e sec ion i is p o ed ha he de i ed bounds a e igh in many cases. Le he o de ed d− uple j=(j1, j2, ..., jd) o in ege s be gi en, and le G= (V, E)be a g aph. The d h powe o g aph G, deno ed by Gd, is adi ionally de ined as he g aph whose e ex se is Vand wo e ices a e adjacen in Gdi and only i hei dis ance in Gis a mos d. Deno ing by Ed he edge se o Gd, we de ine he weigh unc ion wj:Ed→ {j1, j2, ..., jd}as wj(u, ) = ji⇐⇒ dis (u, ) = i o each edge (u )∈Ed. Hence, he edge weigh s p ecisely exp ess he lowe bounds on he di e ences be ween e ex labels, as p esc ibed by j. Once he alues o j1, j2, ..., jda e unde s ood, we shall simpli y he no- a ion om wj o wby w i ing Gd w= (V, Ed, w), and call Gd w he weigh ed powe g aph o G. In ac he p ecise e m would be “weigh ed d h powe g aph wi h espec o j1, j2, ..., jd” bu he pa ame e s a e assumed o be gi en h oughou . Lowe bounds o adio labeling The ele ance o Gd win he con ex o adio labeling is shown by he ollowing asse ion. P oposi ion 2 Fo e e y g aph G, he alue o n(G)is a leas as la ge as 25 he minimum weigh ed leng h o a Hamil onian pa h in Gd w, whe e dis he diame e o G. P oo Obse e ha in a adio labeling no wo e ices can ge he same label. Fo his eason, he weigh ed powe g aph o adio labeling is a comple e g aph equipped wi h posi i e edge weigh s. E e y adio labeling o Gde ines a o al o de on he e ex se by inc easing labels, and hence we ob ain a Hamil onian pa h o Gin a na u al way by his o de . Mo eo e , consecu i e e ices di e in hei labels by a leas as much as he weigh o he edge joining hem. I is impo an o no e ha equali y does no always hold. Fo ins ance, i P= 1 2 3 4 5is he pa h o leng h 4, hen n(P) = 10 holds as a pa icula case o he o mula n(P2k+1)=2k2+ 2 om [39] . On he o he hand, since he weigh o an edge ( i j)is equal o n− |i−j|, he Hamil onian pa h 3 5 1 4 2in P4 whas weigh 3+1+2+3=9. The poin is ha Hamil onian pa hs ake only he consecu i e e ex pai s in o accoun , while in a adio labeling on all pai s. Indeed, he subpa h 5 1 4has leng h 3, bu 5and 4 should di e by a leas 4 in label. We nex obse e ha he lowe bound in P oposi ion 2 can be e ined o a igh es ima e. P oposi ion 3 Fo e e y g aph G, he alue o n(G)is equal o he small- es possible weigh ed leng h o a longes di ec ed pa h aken o e all ansi i e o ien a ions o Gd w, whe e dis he diame e o G. P oo Le ϕ:V→ {0,1, ..., n(G)}be a minimum-span adio labeling o g aph G= (V, E). Since no wo e ices can ge he same label, ϕde ines a na u al o de ing on V. We index he e ices in he inc easing o de o labels, ha is 0 = ϕ( 1)< ϕ( 2)< ... < ϕ( n) = n(G). O ien ing each edge o Gd w om smalle index o la ge one, he weigh ed leng h o any o ien ed pa h is a mos he di e ence o labels o i s wo ends, he e o e no pa h 26 longe han n(G)can occu . Con e sely, le 1, 2, ..., nbe he e ex o de gene a ed by a ansi i e o ien a ion o Gd w, and suppose ha he maximum weigh ed leng h o a di ec ed pa h in his o ien a ion is `. De ine ϕ( 1) = 0 and compu e he e ex labels ecu si ely by he ule ϕ( i) = d+ 1 + max 1≤j≤i−1(ϕ( j)−dis ( i, j)) (3) o i= 2,3, ..., n. This is a adio labeling o Gbecause he sepa a ion con- s ain is espec ed be ween any wo e ices. Mo eo e , a pa h o weigh ed leng h ϕ( n)exis s; i can be iden i ied by back acking. Indeed, each iwi h i > 1a ains equali y in (3) o some j=ji< i, and he e o e making one such edge ( j, i) o each i, he e exis s a mono one dec easing pa h om n o 1. Consequen ly, we ha e n(G)≤ϕ( n)≤`. 2.2 Lowe bound o le el-wise egula ees Gi en an h- uple (m0, m1, ..., mh−1), le us use he simpli ied no a ion T1and T2 o he le el-wise egula ees T1=T1 m0,m1,...,mh−1,T2=T2 m0,m1,...,mh−1. Unde he s ic e assump ion mi≥3 o all 0≤i < h, P oposi ions 2 and 3 will u n ou o be equi alen o each T1and T2. Using hose p oposi ions, we de i e he ollowing gene al lowe bound: Theo em 4 I h≥1and m0, m1, ..., mh−1≥2, hen λd,d−1,...,1(T1)≥(d+1)(n−1)+1−2· h X i=1 (m0·i·Y 0<j<i (mj−1)) (4) and λd,d−1,...,1(T2)≥d(n−1)−4· h X i=1 (i·Y 0≤j<i (mj−1)) (5) 27 o d= 2hand d= 2h+ 1, espec i ely. P oo Al hough he ideas a e e y simila in he a gumen s o de en and odd, he e a e some di e ences and i is con enien o spli he p oo in o wo pa s acco ding o he pa i y o d. In ei he case, we deno e n= h X i=0 |Li|, he numbe o e ices. Case 1: d= 2h We ha e |L0|= 1 and |Li|=m0·Y 0<j<i (mj−1) o i= 1, ..., h. Mo eo e , he dis ance be ween an i0- e ex 0and an i00- e ex 00 has he uppe bound dis ( 0, 00)≤i0+i00,(6) he e o e he edge 0 00 in (T1)d whas weigh a leas d+1−(i0+i00). We de ine `( ) = `i=d+ 1 2−i=h+1 2−i o e e y i− e ex , o any i= 0,1, ..., h. Le P= 1 2... nbe any Hamil onian pa h o (T1)d. Due o inequali y (6), he weigh o any edge ( j j+1) o wo consecu i e e ices in Pis a leas `( j) + `( j+1). In e nal e ices o Poccu in wo such pai s, while he 28 wo ends occu in jus one pai each. Consequen ly, λd,d−1,...,1(T1)≥min 1 2... n ( n X j=1 2`( j)) −`( 1)−`( n) = ( h X i=1 (d+ 1 −2i)·|Li|)−`0−`1) = (d+ 1)n−d−2· h X i=1 (m0·i·Y 0<j<i (mj−1) whe e minimum in he i s line is aken o e all pe mu a ions ( 1, 2, ..., n) o he e ices. This comple es he p oo o (4). Case 2: d= 2h+ 1 In his case |Lo|= 2 and |Li|= 2 · i−1 Y j=0 (mj−1) o i= 1, ..., h. Mo eo e , since he deepes le el is Ld−1 2ins ead o Ld 2, also he uppe bound on he dis ance be ween an i0- e ex 0and an i00- e ex 00 is sligh ly di e en : dis ( 0, ”) ≤i0+i”+1,(7) he ”+1” e m being due o he cen al edge. Fo his eason, he edge ( 0 00) in (T2)d wnow has weigh a leas d−(i0+i00). We he e o e de ine `( ) = `i=d 2−i=h+1 2−i o e e y i- e ex , o any i= 0,1, ..., h. No ice ha he o mula is un- changed as a unc ion o h, bu i is somewha di e en when iewed as a 29 unc ion o d. The nex obse a ions a e analogous o hose o T1abo e. Le P= 1 2... nbe any Hamil onian pa h o (T2)d. Due o inequali y (7), he weigh o any edge ( j j+1) o wo consecu i e e ices in Pis a leas `( j)+`( j+1). In e nal e ices o Poccu in wo such pai s, while he wo ends occu in jus one pai each. No e ha we now ha e wo 0- e ices. Consequen ly, λd,d−1,...,1(T2) = min 1 2... n ( n X j=1 2`( j)) −`( 1)−`( n) ≥ h X i=0 (d−2i)·|Li|!−2`0 =dn −d−2· h X i=1 2i· i−1 Y j=0 (mj−1)! whe e minimum in he i s line is aken o e all pe mu a ions ( 1, 2, ..., n) o he e ices. This p o es (5) and also comple es he p oo o he heo em. 2.3 Tigh ness o he lowe bound This subsec ion is abou he p oo ha he lowe bounds p esen ed in he p e ious subsec ion can be a ained wi h equali y wi h a sui able pe mu a ion o he e ices, whene e a comple e ee does no con ain e ices o deg ee 2. P oo o igh ness Theo em 5 I mi≥3 o all 0≤i < h, hen equali y holds in he inequali- ies (4) and (5) o Theo em 4. P oo We cons uc sui able e ex o de s a aining equali y o bo h d e en and odd. In ac he case o e en dwill be c ucial, om which we can 30 build a pe mu a ion o odd d, oo. Wi h s anda d e minology, o an i- e ex ∈Li he unique neighbo o in Li−1is i s pa en (i 1≤i≤h) and i s neighbo s in Li+1 a e i s child en (i 0≤i≤h−1). We say ha a e ex uis an ances o o i uis on he pa h om o he oo . In pa icula , by his de ini ion, is conside ed o be an ances o o i sel , oo. We ecall ha `i=h+1 2−ihas been de ined in he p oo o Theo em 4; i is d+1 2−ii dis e en, and d 2−ii dis odd. Case 1: d= 2h We p o e ha he e exis s an o de o he e ices 1, 2, ..., nsuch ha he labeling ϕde ined wi h he ules ϕ( 1)=0, ϕ( i) = ϕ( i−1) + `( i−1) + `( i) o i= 2, ..., n (8) is an L(d, d −1, ..., 1)−labeling o T=T1 m0,m1,...,mh−1. The gene al scheme o he o de is L0−Lh−Lh−1−... −L2−L1. The c ucial poin is how o pe mu e he e ices inside each le el Liin a way ha he dis ance cons ain s a e espec ed by all e ex pai s. Viewing Tas a oo ed ee wi h oo L0, le us ma k he edges joining each ∈Li(1 ≤i≤h−1) o i s child en in Li+1 wi h he in ege s 0,1, ..., mi−2; om he oo o L1 he ma king anges om 0 o m0−1. Then each ∈Li (1≤i≤h) is ep esen ed by he sequence a( )=(ai−1, ai−2, ..., a1, a0) = (ai−1( ), ai−2( ), ..., a1( ), a0( )) o ma ks along he pa h om o L0. F om his, we deno e m0 0=m0and m0 i=mi−1 o i= 1, ..., h −1, and associa e wi h he numbe 31 he size o a (j−1)−sub ee is bounded. Thus, he numbe o s eps in he algo i hm is a mos C·λ(∆j)wi h an app op ia e cons an C. 3L(j, j−1, ..., 2,1)–labeling o uni in e al g aphs In e al g aphs and specially uni in e al g aphs ha e been in oduced in 1.1.6. Based on he p oo o hei L(2,1)−labeling numbe I ga e an uppe bound o hei L(j, j −1, ..., 2,1)−labeling numbe . In his chap e I p esen his esul . 3.1 Ci cula L(j, j −1, ..., 2,1)−labeling o pa hs Fo de e mining he bound o uni in e al g aphs an uppe bound o he ci cula L(j, j −1, ..., 2,1)−labeling numbe o pa hs is also needed. Ci - cula labeling means ha he possible labels a e he na u al numbe s on a ci cle om 0 o k−1(ac ually, he alue o kco esponds o 0), and he leng h o bo h sec ions on he ci cle be ween wo e ices and uha e o be a leas jdis (u, ). A p ope ci cula labeling o he g aph Gon he ci - cle o ci cum e ence kis called a k−ci cula L(j, j −1, ..., 2,1)−labeling o G.λC j,j−1,...,2,1(G)is he smalles k, o which Ghas a k−ci cula L(j,j −1, ..., 2,1)–labeling. P oposi ion 1 I jis odd hen λC j,j−1,...,2,1(P)≤(j+1)2 2and i jis e en hen λC j,j−1,...,2,1(P)≤j·(j+3) 2, whe e Pis a pa h o a bi a y leng h. P oo We ge a p ope k−ci cula labeling o G(k=(j+1)2 2o j·(j+3) 2) when gi ing labels o he e ices in sequence in such a way ha c( ) = c(le neighbo o ) + j(mod λ) o e e y e ex . 38 Fo showing he co ec ness o he abo e me hod we mus see ha he di e ence o labels o any wo e ices a dis ance xis a leas j+ 1 −x. The e a e se e al cases: 1. c( 2) = c( 1)+xj (no educ ion be ween 1and 2):x≥1=⇒x(j+1) ≥ j+ 1 =⇒xj ≥j+ 1 −x. 2. c( 2) = c( 1) + xj −kand xj < k:c( 2)< c( 1) =⇒ |c( 2)−c( 1)|= c( 1)−c( 2) = k−xj. I jis odd hen k=(j+1)2 2holds: j+1 2≥1 =⇒ j+1 2·(j+1−2x)≥j+1−2x=⇒(j+1)2 2−(j+1)x≥j+1−2x=⇒k−jx ≥ j+ 1 −x. I jis e en hen k=j·(j+3) 2=j2+3j 2>j2+2j+1 2=(j+1)2 2holds. Because o he inequali y o odd jalso he inequali y o e en jwill be co ec , namely in he las inequali y k−jx > (j+1)2 2−jx ≥j+ 1 −x. 3. k≤xj < 2k:c( 2) = c( 1) + xj −kholds also in his case, bu c( 2)≥c( 1) =⇒ |(c( 2)−c( 1)|=c( 2)−c( 1) = xj −k: I jis odd hen xj ≥(j+1)2 2=j2+2j+1 2=⇒x≥j+2+ 1 j 2holds, because x∈N=⇒x≥j+3 2=⇒x−j+1 2≥2 2= 1 =⇒x(j+1)−(j+1)2 2≥j+1 =⇒ xj −(j+1)2 2≥j+1−x. I jis e en hen xj ≥j·(j+3) 2=⇒x≥j+3 2holds. We use he inequali y o odd jagain, and he s a emen is p o ed. 4. xj ≥2k=⇒xj ≥(j+ 1)2and xj ≥j(j+ 3) =⇒x > j. In his case he e is no es ic ion. So he di e ence o he labels o each pai o e ices mee s he equi emen s. 3.2 An uppe bound o he L(j, j −1, ..., 2,1)−labeling numbe o uni in e al g aphs Uni in e al g aphs a e pe ec , so χ=ω. I am going o gi e a lowe and an uppe bound as a unc ion o χ. The lowe bound is he L(j, j−1, ..., 2,1)−labeling numbe o he comple e g aph Kχsince each uni in e al g aph wi h clique numbe ω=χcon ains 39 i as a subg aph, and Kχis a uni in e al g aph i sel ( his is impo an because o he igh ness). In his g aph any wo e ices a e adjacen , hence he di e ence is a leas jbe ween any wo labels, so he labeling numbe is j·(χ−1). Fo gi ing an uppe bound one migh examine a g aph ha con ains each uni in e al g aph wi h clique numbe χas a subg aph. The e exis s such a g aph, namely he uni in e al g aph in which each χ e ices in he simplicial o de o m a clique. In his g aph an a bi a y e ex is adjacen o hose ha a e a leas 1 and a mos (χ−1) away in he simplicial o de , i s second neighbo s a e he e ices a leas χand a mos (2χ−2) away, and in gene al i s i h neighbo s a e a leas (i−1)(χ−1) + 1 and a mos i·(χ−1) away om i . A p ope L(j, j −1, ..., 2,1)−labeling p ocedu e •Since uni in e al g aphs a e cho dal, he e exis s a simplicial o de o he e ices o all such g aphs. Fi s , di ide he simplicial o de in o sec ions which co e i o e lap- ee and comple ely. Each sec ion is o med by χo χ+ 1 e ices. I discuss below how many e ices a pa icula sec ion con ains. In each sec ion he labels a e in dec easing o de , he las label is a mos j2 2−1o (j−1)(j+2) 2−1depending on he pa i y o j. The di e ence o wo consecu i e labels is exac ly j2 2o (j−1)(j+2) 2. So, each sec ion co esponds o a esidue class o he L(j−1, j −2, ..., 2,1)−ci cula labeling numbe o he pa h o a bi a y leng h. Fo simplici y, le he ep esen a i e elemen o a esidue class be he smalles one. •A esidue class is assigned o each sec ion as ollows: The i s one shall belong o 0, he nex one o (j−1), and in gene al a sec ion belonging o xis ollowed by one belonging o (x+j−1) mod j2 2o (x+j−1) mod (j−1)(j+2) 2. 40 •The leng h o a sec ion: I he ep esen a i e ( he minimum) elemen o a esidue class belonging o a sec ion is g ea e han he one o ha belonging o he p e ious (say he mod ope a ion does no esul s in educ ion), hen le his sec ion con ain χ e ices, o he wise (when he mod ope a ion esul s in educ ion) χ+ 1 e ices. The bigges label used I is easy o see ha he bigges label used is abou j2 2·χo (j−1)(j+2) 2·χ, espec i ely. The de ia ion depends on wo hings: On he one hand, wha esidue classes occu , in o he wo ds which is he g ea es ep esen a i e elemen a all. On he o he hand, wha is he g ea es elemen ep esen ing a sec ion o leng h χ+ 1, since he g ea es label in his sec ion is he g ea es a all. This is ue, because he g ea es label o any sec ion o leng h χ+ 1 is g ea e han he g ea es elemen o any sec ion o leng h χ. I he co esponding ep esen a i e elemen is x, hen he g ea es label is j2 2·χ+xo (j−1)(j+2) 2·χ+x. Reduc ion occu s be ween wo sec ions i and only i he ep esen a i e elemen o he second one is smalle han j−1. Depending on he pa i y o j his is he ollowing: I jis odd: In his case 2|(j−1), so gcd(j−1,(j−1)(j+2) 2) = j−1 2, because j+2 2is no an in ege , while j−1 2is. Hence, he ep esen a i e elemen s o he occu ing esidue classes a e he in ege mul iplies o j−1 2.j−1 2i sel is he la ges one o hem, which is smalle han j−1. Consequen ly, he la ges label used is (j−1)(j+2) 2·χ+j−1 2. I jis e en: In his case 2-(j−1), so gcd(j−1,j2 2) = 1, hence each in ege be ween 0 and j2 2−1occu s as a ep esen a i e elemen . j−2is he la ges one o hem, which is smalle han j−1. So, he la ges label used is j2 2·χ+j−2. An example: L(3,2,1)−labeling Ou bound o he ci cula labeling numbe o a pa h is (3−1)(3+2) 2= 5. The labels o a uni in e al g aph wi h 41 ω=χa e he ollowing in he simplicial o de : 5χ−5 5χ−10 ... 0 5χ−3 5χ−8... 2 5χ−1 5χ−6... 4 χpcs Rc :0 χpcs Rc :2 χpcs Rc :4 5χ+ 1 5χ−4... 1 5χ−2 5χ−7... 3 5χ5χ−5... 0 χ+ 1 pcs Rc :1 χpcs Rc :3 χ+ 1 pcs Rc :0 I has o be shown ha he abo e labeling p ocedu e esul s in a p ope labeling, so he cons ain is me o each pai o e ices. This can be done as ollows: Le an a bi a y e ex be gi en, i has a label assigned o i . We check how a he e ices a e ha ha e labels di e ing by a mos j−1 om he label o he gi en e ex. Because o he symme y i is enough o examine only hose e ices, which come la e in he o de . I a e ex is he x h one in i s sec ion hen in any o he sec ion he e ex closes in label is he x h o he (x+1) h one. This smalles di e ence is equal o he di e ence o he ep esen a i e elemen s o he sec ions. I he wo sec ions a e he a h and he b h one, hen he e a e a leas (b−a)·χ−1 e ices be ween he wo examined e ices in he simplicial o de . The exac alue is depending on he numbe o educ ions be ween hem. In o he wo ds, i means ha he second e ex is he (b−a)·χ h ollowing one om he i s e ex in he simplicial o de . Since (b−a)·χ > (b−a)·(χ−1), he g aph dis ance o he e ices is g ea e han b−a. The ep esen a i e elemen s o hei sec ions ha e been selec ed so ha hei di e ence is a leas (j−1)+ 1−(b−a) = j−(b−a). So he di e ence is big enough. This a gumen is gene ally alid o all e ex pai s, hence he cons ain is me o any wo e ices. This e i ies he p ope y o he labeling scheme. 42 Pa IV Applica ion o Combina o ial Op imiza ion Me hods The dis ance-cons ained labeling p oblem in oduced so a is an in e es ing g aph heo e ical p oblem. Howe e , i canno model a p ac ical equency assignmen p oblem p ope ly because he disc e e g aph dis ances do no e lec he eal dis ances be ween ansmi e s. Hence i can only se e as a coa se app oxima ion. This ac was my mo i a ion o s udy he opic om he applica ion poin o iew. In he ollowing chap e I desc ibe my expe iences. 4 New model o he equency assignmen p ob- lem 4.1 Linea p og amming and in ege p og amming The ollowing in oduc ion o he wo combina o ial op imiza ion me hods a e based on he p esen a ion in [52]. The goal o a linea p og amming p oblem is o ind a ec o x∈Rn ha ul ills all gi en inequali ies in he sys em Ax ≤band maximizes a ce ain objec i e unc ion cTx, whe e Ais an m×nma ix and b∈Rmand c∈Rna e ec o s. This p oblem is deno ed as linea p og am (LP), i s s anda d o m is min cTx s. . Ax ≤b x∈Rn . 43 A ec o x∈Rn ha sa is ies Ax ≤b, is called a easible solu ion. A easible solu ion ha is maximal, is called an op imal solu ion. The di e ence be ween a linea p og amming p oblem and an in ege p og amming p oblem is small bu signi ican . Namely, he en ies o he solu ion ec o xha e o ake in ege alues ins ead o eals. Fo mally, an in ege p og amming p oblem (IP) consis s o inding a ec o x∈Zn ha ul ills all gi en inequali ies in he sys em Ax ≤band maximizes a ce ain objec i e unc ion cTx, ha is min cTx s. . Ax ≤b x∈Zn . The hi d condi ion is he in eg ali y cons ain . This makes he p oblem much ha de . The linea p og amming a ian is namely sol able in poly- nomial ime, while an in ege p og amming p oblem is in gene al NP-ha d [53]. Anyway, he e a e a ew exac and heu is ic algo i hms ha handle he p oblem qui e well, making some calcula ions possible. 4.2 Models o compu ing dis ance-cons ained label- ings He e I s a wi h an in ege p og amming model o he classical p oblem. Le he label o e ex be ep esen ed by he in ege a iable c( ). 4.2.1 In ege p og amming o mula ion o he L(j1, j2, ..., js)–p oblem The p oblem o inding an op imum L(j1, j2, ..., js)−labeling can be s a ed as ollows. min L 1. L−c( )≥0∀ ∈V(G) 44 2. |c( )−c(u)| ≥ jdis (u, )∀u, ∈V(G)wi h dis (u, )≤s 3. c( )≥0∀ ∈V(G) 4. c( )∈Z∀ ∈V(G) Inequali ies (1) model he min-max objec i e unc ion and so minλj1,j2,...,js(G) is compu ed. The dis ance cons ain s (2) o e ex pai s uand can be linea ized in he s anda d way wi h addi ional bina y a iables zu as c( )−c(u) + M·zu ≥jdis (u, )∀u, ∈V(G) wi h dis (u, )≤s c(u)−c( ) + M·(1 −zu )≥jdis (u, )∀u, ∈V(G) wi h dis (u, )≤s zu ∈ {0,1} ∀u, ∈V(G) The numbe Mhas o be chosen big enough. Ob iously M≥j1+ λj1,j2,...,js(G)has o hold. I no good uppe bound on λj1,j2,...,js(G)is known, we jus se M=n·j1. 4.3 New model A possibili y o making he model mo e p ac ical would be o inse a i icial e ices o inc ease he dis ance be ween e ices close o eali y. This way we p ese e he disc e e na u e o he model, bu he g aph size is inc eased. One could also allow eal alues as labels (lea ing he g aph and he dis- ance unchanged). Since p ope in ege solu ions emain easible, he mini- mum span is no bigge han in he classical model. Ac ually, his is he LP elaxa ion o he model abo e. I would be mos p ecise o conside he comple e g aph on he ansmi - e s and o ake he Euclidean dis ance be ween ansmi e s as edge weigh s. Since he g aph is ini e, he e is also only a ini e numbe o occu ing dis- ances, and cons ain s can be o mula ed as abo e ela i e o a sequence L(jdis 1, jdis 2, ..., jdis ). 45 Fo he Euclidean model we can basically adop he in ege model wi h wo li le changes. Fi s , he a iables c( )a e now con inuous. Second, he Euclidean dis ances ha e o be ans o med o sui able igh hand side alues o he inequali ies (2). This will be accomplished by a unc ion `(dis (u, )). The o mula ion o he Euclidean app oach is he ollowing. min L 1. L−c( )≥0∀ ∈V(G) 2. c( )−c(u) + M·zu ≥`(dis (u, )) ∀u, ∈V(G) wi h dis (u, )≤s 3. c(u)−c( )+M·(1−zu )≥`(dis (u, ))∀u, ∈V(G)wi hdis (u, )≤s 4. c( )≥0∀ ∈V(G) 5. zu ∈ {0,1} ∀u, ∈V(G). 4.4 Tes ins ances I am no awa e o any esea ch on sol ing dis ance-cons ained labeling p ob- lems o op imali y, so I ook own gene a ed benchma k p oblems. The goal was o es he g aph and he Euclidean model on ins ances which somehow esemble he p ac ical si ua ion o eal equency assignmen p oblems. In adio and mobile ne wo ks la ge a eas a e usually co e ed by polygons which oge he o m la ices. In p ac ice h ee la ices play a p ominen ole: hexagonal, iangula and squa e la ices. Expe imen s ha e shown ha he co e ing by hexagons is he mos economical one. In his case he ans- mi e s a e assumed o a he cen e s o he hexagons and wo ansmi e s a e adjacen in he g aph i and only i he co esponding hexagons sha e a common edge. The g aph cons uc ed his way is a iangula la ice. In ou expe imen s we pe o med compu a ions wi h he Euclidean model and wi h he g aph model o h ee p oblem ypes a ising om la ice g aphs. 46 The h ee la ice ypes shown in he igu e we e conside ed. Fo he g aph e sion he classical g aph dis ance was aken, (e.g., he dis ance be ween 0 and 21 in he iangula la ice is 5). Fo he Euclidean e sion co- o dina es we e gi en o he e ices such ha e e y edge shown in he igu e has leng h 1. So he coo dina es o he e ices 0, 1 and 2 a e (−√3 2,+3 2),(+√3 2,+3 2),(−√3,+1) in he hexagonal la ice, (−2,+2),(−1,+2), (0,+2) in he squa e la ice and (−2,+2),(−1,+2),(0,+2) in he iangula la ice. (E.g., he dis ance be ween 0 and 1 in he hexagonal la ice is √3.) The di e ence o he dis ance be ween wo e ices in he Euclidean and in he g aph model can be small o 0, bu also ela i ely high. Two e ices wi h g aph dis ance 4 could, o example, ha e Euclidean dis ance 4, √10 o √8. Wi h he help o he ans o ma ion unc ion `we ied o ha e a sim- ila ange o spans o he g aph and he co esponding Euclidean model. O cou se, `has o be mono onically dec easing. We expe imen ed wi h wo a ian s o `which in addi ion ha e he p ope y ha he alues o in ege dis ances a e p ese ed. i.e. `(dis (u, )) = jdis (u, ) o dis (u, ) in ege . E.g., his is sa is ied by de ining `(dis (u, )) = j+ 1 −dis (u, ) o L(j, j −1, ..., 1)-labelings. Since he g aph dis ances a e no smalle han 47 k·j2+ 2j1,..., (m−3)j2+ 2j1and hei sum is (Pm−3 i=1 i·j2) + 2(k−1)j2+ (2(m−k−1) + 1) ·j1. Since j1≥j2, an easy calcula ion shows ha he smalles sum is ob ained in case 2 and is equal o 1 2(m+ 1)(m−2) ·j2+j1. So o e e y e ex u∈V we can add i s associa ed s a inequali y c(u) + X i∈N(u) c(i)≥(deg(u) + 2)(deg(u)−1) 2·j2+j1 o he models (whe e N(u)deno es he se o neighbo s o uand deg(u)is he deg ee o u.) Subla ices A second possibili y is o associa e inequali ies wi h small subla ices o he la ices we conside ed in ou compu a ional expe imen s. We conside ed he iangles wi h side leng h 1, 2 and 3, he hexagons wi h side leng h 1 and 2, apezes as hal o a hexagon, squa es wi h side leng h 1, 2 and 3, and small squa e la ices wi h 4 and 9 e ices. Table 5 gi es he smalles sums o labels o hese subg aphs o he labelings L(2,1) and L(3,2,1). We examined he e ec o he addi ion o hese small subg aph inequal- i ies. The esul s a e p esen ed in Table 6 o he hexagonal, in Table 7 o he iangula , and in Table 8 o he squa e la ice. Fo he squa e la ice we only added non-o e lapping squa es which is only a small subse o possible squa es. Fo he hexagonal la ice we obse e a unning ime imp o emen o abou 10-20%. In he iangula case, ime educes o abou 50% in wo cases o he L(3,2,1)-labeling. Also in one case o he squa e la ice a conside able imp o emen is achie ed. 54 Subla ice `2(dis )=3−dis `3(dis ) = 4 −dis Hexagon wi h side leng h 1 16.6077 31.6077 Hexagon wi h side leng h 2 3 10.8231 T apeze wi h side leng h 1 7.0718 13.0718 T iangle wi h side leng h 1 6 9 T iangle wi h side leng h 2 3 6 T iangle wi h side leng h 3 0 3 Squa e 1×1 (4 nodes) 10.3431 16.3431 Squa e 2×2 (4 nodes) 2.68629 8.68629 Squa e 3×3 (4 nodes) 0 2 Squa e la ice 2×2 (9 nodes) 29.1922 59.4033 Squa e la ice 1×2 (6 nodes) 16.2273 30.283 Table 5 Minimum label sums o subla ices Hexagonal la ice `2(dis ) = 3 −dis `3(dis ) = 4 −dis Wi hou any subg aph-inequali y 1.69 30:38.7 Wi h he subg aph-inequali ies Hexagons wi h side leng h 1 1.37 26:28.7 Hexagons wi h side leng h 1 and 2 1.75 27:21.7 T apezes 1.77 25:29.2 Table 6 E ec o subg aph inequali ies o he hexagonal la ice 55 T iangula la ice `2(dis ) = 3 −dis `3(dis ) = 4 −dis Wi hou any subg aph-inequali y 10.96 1731:23.0 Wi h he subg aph-inequali ies T iangels wi h side leng h 1 12.59 782:13.0 T iangels wi h side leng h 1,2 and 3 10.02 1537:08.1 Hexagons wi h side leng h 1 11.9 706:52.0 Table 7 E ec o subg aph inequali ies o he iangula la ice Squa e la ice `2(dis )=3−dis `3(dis ) = 4 −dis Wi hou any subg aph-inequali y 4.92 463:13.8 Wi h he subg aph-inequali ies Squa es wi h side leng h 1 12.76 632:25.5 Squa es wi h side leng h 1,2 and 3 * 7.11 326:59.4 Rec angle wi h side leng h 1×2 6.22 476:52.8 * inequali ies added only o non-o e lapping squa es (subs an ially ewe han exis ing) Table 8 E ec o subg aph inequali ies o he squa e la ice 56 Pa V Ano he ype o g aph pa i ion 5 Edge decomposi ions So a I deal wi h he labeling o he e ices. The labeling gi es a pa i ion on he e ex se o he g aph. In he case o adio labeling his pa i ion is i ial, bu in gene al no necessa ily. This sec ion deals wi h a p oblem, in which he edge se o he g aph is pa i ioned in a speci ied way. In gene al, an edge decomposi ion o a g aph G= (V, E)is a collec ion o g aphs Gi= (Vi, Ei)such ha each Giis a subg aph o G, any wo Gi,Gj (i6=j) a e edge-disjoin , and hei union con ains all edges o G. The s udy o edge decomposi ions (as well as he heo y o balanced incomple e block designs and ela ed a eas, see [54] wi h mo e han 2200 e e ences) s a ed wi h he amous pape [55] o Ki kman in 1847. S ill, a e mo e han one and a hal cen u ies, qui e ecen ly Bondy and Szwa c i e [56] in oduced a na u al side condi ion which has led o an in e es ing new di ec ion. Among se e al esul s, we sol e one o he open p oblems s a ed in [56]. 5.1 The p oblems Gi en a g aph F, de e mine he maximum numbe ex∗(n, F )o edges in a g aph Go o de nsuch ha he edge se o Gcan be decomposed in o edge-disjoin induced subg aphs isomo phic o F. As men ioned abo e his issue was add essed in a pape o Bondy and Szwa c i e [56]. On he o he hand, nea ly h ee decades ea lie , wi h a e y di e en app oach, F ankl and Fü edi [57] conside ed a closely ela ed p oblem on hype g aph packing. They in oduced a unc ion (n, F)whose de ini ion is mo e echnical bu always sa is ies he inequali y (n, F )≤ 57 ex∗(n, F). Hence, lowe bounds on hei p oblem a e also lowe bounds on ex∗(n, F), while uppe bounds on ex∗(n, F )a e also uppe bounds o he p oblem o [57] . Fo some good easons, o be explained below, we s udied he comple- men a y unc ion ex∗(n, F) := n 2−ex∗(n, F). 5.2 Ea lie esul s The undamen al esul o Wilson [58] s a es ha e e y su icien ly la ge comple e g aph admi s an edge decomposi ion in o comple e subg aphs o gi en o de whene e wo ob ious necessa y di isibili y condi ions hold. Since e e y comple e subg aph necessa ily is induced, ex∗(n, Kp) = O(n)holds o e e y ixed p≥3, and ex∗(n, Kp)oscilla es be ween 0 and cn+O(1) o some c=c(p). (O cou se, ex∗(n, K2) = 0 holds o all n.) I is also easily obse ed (as no ed i s in [53]) ha i F0is ob ained om Fby adding an isola ed e ex, hen ex∗(n, F 0)≤ex∗(n−1, F)+ n−1, hus we lose a mos a linea addi i e e m i any ixed numbe o isola es a e added o F. Fo his eason we may assume ha Fdoes no ha e isola ed e ices. In gene al, Cohen and Tuza [59] p o ed ha ex∗(n, F) = o(n2) (1) holds o all non-edgeless g aphs Fas nge s la ge. Due o he connec ion be ween he p oblems [56] and [57], he same asymp o ic uppe bound can be deduced om he esul s o F ankl and Fü edi, oo. In compa ison, he me h- ods in [57] a e p obabilis ic, whils he esul s o [59] a e pa ly cons uc i e, applying he p ope ies o a ious classes o Knese g aphs. Because o (1), he main p oblem is o de e mine he o de o magni ude o ex∗(n, F) o a gi en Fas a unc ion o n. Se e al es ima es ha e been 58 p o ed in [56] and [59]: •ex∗(n, F) = Θ(n)i Fis a comple e equipa i e non-comple e g aph (and in pa icula i F=C4) o Fis a s a o F=K4−e([56]); •ex∗(n, F) = Θ(n3 2)i F= 2K2o F=C6(lowe bounds in [56], cons uc i e uppe bounds in [59]). In some cases, mo e p ecise o e en exac esul s a e known, bu he e we p e e o emphasize g ow h o de . 5.3 The new esul s We ga e a gene al lowe bound, namely, Theo em 1 The e exis s a cons an c > 0wi h he ollowing p ope y: I F is a g aph wi hou isola ed e ices, and Fis no a comple e mul ipa - i e g aph, hen ex∗(n, F)≥(c−o(1))n3 2as n→ ∞. P oo Le Fbe any isola e- ee g aph sa is ying he assump ions o he heo em. Deno e by p he numbe o e ices and by q he numbe o edges in F. Since Fis no comple e mu ipa i e, i con ains some e ex wand an edge (yz)such ha (wy)and (wz)a e non-edges. Indeed, he complemen o Fcon ains some connec ed componen o o de a leas 3 which is no a comple e g aph, and hen his componen con ains an induced pa h ywz ∼ = P3, a p ope choice o he h ee e ices named abo e in F. Le G= (V, E)be a g aph o o de n, which is ex emal o ex∗(n, F); and le H=Gi s complemen . By he heo em o Cohen and Tuza [59], o e e y  > 0 he e exis s n0=n0(, F)such ha , o e e y n>n0,Ghas mo e han (1 2−)n2edges. As a consequence, he edge se o Gis decomposed in o mo e han 1−2 2qn2copies o F. In each copy, e ex wis mapped o some 59 e ex o G. Le k deno e he numbe o copies o Fin which wis mapped o e ex ∈V. Then we ha e X ∈V k >1−2 2qn2. Choosing now =1 10, i ollows ha a leas n 5qamong he n e ms on he le side a e no smalle han n 5q. This speci ies a se X⊂Vsuch ha |X| ≥ n 5qand kx≥n 5q o all x∈X. The copies o he edge (yz)appea in he non-neighbo hoods o he copies o w. This equi es a leas kxdis inc edges in he complemen a y neighbo - hood NH(x), implying dH(x) 2≥kx; dH(x)>p2kx≥ 0.4n q o e e y x∈X. Consequen ly, ex∗(n, F) = |E(H)|=1 2X ∈V dH( )≥1 2X x∈X dH(x)>1 √10qn3 2. This inequali y p o es he heo em. Co olla y 2 E e y g aph Fcon aining he pa h P4o he ma ching 2K2o he paw K4−P3as an induced subg aph, sa is ies ex∗(n, F)≥cn3 2 o some cons an c > 0. Combining hese lowe bounds wi h he cons uc ions o [59], he ollowing cases sol e he p oblem o Bondy and Szwa z i e [56]. Co olla y 3 We ha e ex∗(n, P4) = Θ(n3 2)and ex∗(n, K4−P3) = Θ(n3 2). 60 Fo g aphs con aining an induced K4−P3, he lowe bound cn3 2 o a sligh ly di e en p oblem was p o ed in [57, P oposi ion 2.4]. Fo pa hs, un il now only a linea lowe bound was known in gene al, and Θ(n3 2)was p o ed only o egula g aphs decomposable in o induced copies o F(see [56]). We conjec u e ha no o he g ow h unc ion occu s as ex∗(n, F )which would lie s ic ly be ween Θ(n)and Θ(n3 2). Conjec u e 4 I Fis a comple e mul ipa i e g aph, hen ex∗(n, F) = O(n). As men ioned abo e, linea uppe bound was known p e iously o comple e equipa i e g aphs, o s a s and o K2,1,1. We p o e he ollowing u he cases. The i s one is e y simple, while he o he one is ou second main esul in his chap e . P oposi ion 5 I F=Ka,b wi h a≥2and b≥1, hen ex∗(n, F) = O(n). P oo I is easy o decompose Kab,ab in o induced copies o Ka,b, as ollows. We pa i ion he i s e ex class in o bdisjoin se s o size a, and he second e ex class in o adisjoin se s o size b. The combina ions o hose se s yield ab copies o Ka,b, which oge he pa i ion he edge se o Kab,ab. Suppose nex ha nis o he o m n=kab o some in ege k≥2. We eplace each edge o Kn ab wi h an independen se o ca dinali y ab, and subs i u e he abo e decomposi ion o Kab,ab in o he image o each edge o Kn ab . In his way a g aph o o de nis ob ained, which admi s a decomposi ion in o induced copies o Ka,b, and i s complemen has as ew as ab−1 2·nedges. Finally, i n≡ (mod ab), hen we make he same cons uc ion on n0:= n− e ices and inse isola es. This g aph is decomposable in o induced copies o Ka,b, and i s complemen has ewe han 3 2abn edges. Theo em 6 I F=Ka,b,c is a comple e ipa i e g aph, bu Fis no comp- le e, hen ex∗(n, F) = O(n). 61 P oo Le F=Ka,b,c. We ca y ou a cons uc ion in se e al s eps which will yield he comple e ipa i e g aph Ka2bc,ab2c,abc2. No alone his g aph, bu also he s eps leading o i , will be essen ial in he sense ha hey si- mul aneously main ain wo edge pa i ions: one in o copies o Ka,b,c and he o he in o copies o Kabc,abc, wi h a s ong in e ela ion be ween he wo. We s a wi h h ee disjoin se s A, B, C o equal ca dinali y |A|=|B|= |C|=abc, pa i ioned in o se s o ca dinali ies a,band c, espec i ely: A=∪b j=1 ∪c k=1 Aj,k, B =∪a i=1 ∪c k=1 Bi,k, C =∪a i=1 ∪b j=1 Ci,j. Ou app oach is o s a wi h an ini ial cons uc ion and ex end i inc emen- ally, making i dense in each s ep. •Packing o Ka,b,c in o Kabc,abc,abc. Fo e e y iple (i, j, k) wi h 1≤i≤a,1≤j≤b,1≤k≤c, de ine he e ex se Vi,j,k =Aj,k ∪Bi,k ∪Ci,j. We use each Vi,j,k o inse a copy o Ka,b,c wi h e ex classes Aj,k,Bi,k,Ci,j inside A∪B∪C. I is immedia e o e i y ha he copies de e mined by Vi,j,k and Vi0,j0,k0a e edge-disjoin o any wo o de ed iple s (i, j, k)6= (i0, j0, k0), because hey sha e e ices in a mos one e ex class. (Fo example, chang- ing he alue o imodi ies Vi,j,k in bo h Band C.) I we ix he i s subsc ip i o he momen , and le j un om 1 o b and also le k un om 1 o c, he co esponding c−elemen se s ha e a union o ca dinali y bc in C. Consequen ly, he subg aph be ween Band C, whose edges a e co e ed wi h he copies o Ka,b,c, is he e ex-disjoin union o a copies o Kbc,bc. Analogously, ixing he second subsc ip j, and le ing i, k un o e hei ange, we see ha he subg aph composed om he copies o Ka,b,c be ween Aand Cis he e ex-disjoin union o bcopies o Kac,ac. In he same way, 62 he edges, which a e co e ed be ween Aand B, o m he union o c e ex- disjoin copies o Kab,ab. Fo e e ence in he nex s ep, we deno e his cons uc ion by G[A, B, C]. •Sa u a ion o edges be ween Aand Bin a s a -like ex ension. We use copies o G[A, B, C]as building blocks in he ollowing way: We ake cg aphs isomo phic o G[A, B, C], deno ed as G[A, B, Ck0] (1 ≤k0≤c), whe e he se s C1, ..., Cca e mu ually disjoin , bu Aand Ba e common in all hose copies o G[A, B, C]. Mo eo e , he e ices o Aoccu in a di e en o de in each G[A, B, Ck0], in such a way ha he co esponding e ex se s de e mining he copies o Ka,b,c a e Vk0 i,j,k =Aj+k0−1,k ∪Bi,k ∪Ck0 j,k, whe e j+k0−1in he subsc ip o Ais mean cyclically modulo c. This yields he comple e bipa i e g aph Kabc,abc be ween Aand B. The edges om A o each Ck0 o m bdisjoin copies o Kac,ac ; and simila ly, om B o each Ck0we ha e adisjoin copies o Kbc,bc. I should be emphasized ha he second subsc ip s in he se s Aj,k ha e no been pe mu ed. As a consequence, he copies o Kac,ac be ween Aand any Ck0de ine he same e ex pa i ion o Ain o bse s o ca dinali y ac. This p ope y is essen ial o la e use. Fo e e ence in he nex s ep, we deno e his cons uc ion by G[A, B, C∗]. •Sa u a ion o edges be ween Aand C∗. He e we use copies o G[A, B, C∗]as building blocks. We s ick hem oge he on he se A∪C∗, c ea ing bcopies B1, ..., Bbo B, so ha he nex g aph 63 lémá . Ta almilag ké ész e osz ha ó a ejeze . Egy ész , e mésze esen adódik az igény e szőleges g á ok e szőleges ko lá ozó el é el melle i cím- kézésé e. Ehhez különböző kombina o ikus op imalizálási módsze eke hasz- nálha unk. Én a lineá is p og amozás álasz o am, mi el a p obléma meg- lehe ősen egysze űen o malizálha ó lineá is p og amozási elada kén , ille e meg elelő szo e el jó becsléseke , ső aká pon os é ékeke is kapha unk. A másik ké dés a gyako la i alkalmazáshoz kapcsolódik. A g á elméle i p ob- léma jól modellezi a ek enciakiosz ás , de nem p ecíz. Ugyanakko a p ecíz modellben csupán jó becsléseke is sokkal lassabban kapha unk. A alósághoz igazod a, az összehasonlí ások azon a 3 hálóg á on le ek el égez e, amelyek a ádióadók elhelyezkedésé ekin e a leginkább ele ánsak. Végül az a kö e kez e és kelle le onni, hogy a p ecizi ás á a úl nagy, ugyanis a szá- molások még a ja í ás célzó módosí ások u án is sokkal lassabban u o ak le, min az e ede i modell ese én. Az é ekezés u olsó egységében egy másik aj a pa íció ke ül a középpon - ba. A címkézés egy pa íció abban az é elemben, hogy egyes ek enciákon (azonos) sugá zó adóka áloga unk össze egy bizonyos ko lá ozó el é elnek meg elelően. Ez a ejeze azonban nem a csúcsok, hanem az élek pa ícioná- lásá ól szól. A ége edménynek úgy kell kinéznie, hogy minden halmaz egy elő e megha á ozo g á al izomo észg á élei a almazza. A ké dés pe- dig az, hogy leg eljebb hány éle lehe egy g á nak ahhoz, hogy azoka lehessen ilyen módon pa ícionálni. A 2-6. ejeze ek a hi a kozások ki é elé el csak új e edményeke a al- maznak, amelyek eljesen agy észben az én munkámból szüle ek. A 2. és a 6. ejeze a alma má el an ogad a publikálás a/publikál a an, a 4. ejeze ének közlése pedig kidolgozás ala áll. Végső kö e kez e éskén az mondha om, hogy a ki űzö céloka sike ül elé ni, őkén a címkézések ekin e ében, a g á pa íciók egy öbb szemszögből ö énő, á ogó izsgála á udom bemu a ni ebben az é ekezésben. 70 Acknowledgmen s I would like o hank my supe iso , Zsol Tuza, o his assis ance du ing my PhD s udies. He in oduced me in he ield o dis ance-cons ained labeling. I am g a e ul o he Resea ch G oup Disc e e and Combina o ial Op i- miza ion in he Rup ech -Ka ls-Uni e si y Heidelbe g whe e I go a lo o expe ience and whe e I always go help when I needed i . I would like o men ion by name Eka e ina Tikhonche a, whose wo k was a g ea help o me in ca ying ou he calcula ions discussed in Chap e 4. I would like o acknowledge he inancial suppo s, which made my s udies possible: The PhD schola ship p o ided by he Faul y o In o ma ics o he Uni e si y o Deb ecen and he Campus Hunga y Fellowship o he Balassi Ins i u . The esul s in Pa IV ha e been compu ed wi h ILOG CPLEX 12.4 (CPLEX Op imize , www.cplex.com). 71 Publica ions The hesis is based on he ollowing publica ions 1. Ve onika Halász, Zsol Tuza: Asymp o ically op imal induced decom- posi ions, Applicable Analysis and Disc e e Ma hema ics 8 (2014), pp. 320-329, DOI: 10.2298/AADM140718009H 2. Ve onika Halász, Zsol Tuza: Dis ance-cons ained labeling o com- ple e ees, Disc e e Ma hema ics 338 (2015), pp. 1398-1406, DOI: 10.1006/j.disc.2015.02.016 72 Re e ences [1] W. K. Hale, F equency assignmen : heo y and applica ion, P oc. IEEE, 68 (1980), 1497-1504. [2] J. R. G iggs, R. K. Yeh. Labeling g aphs wi h a condi ion a dis ance wo. SIAM J. Disc e e Ma h., 5 (1992), pp. 586-595 [3] T. Calamone i: The L(h, k)−labelling p oblem: An up- da ed su ey and anno a ed bibliog aphy. Compu . J. 54 (2011), 1344-1371. (A la e e sion is a ailable online a h p://wwwuse s.di.uni oma1.i /~calamo/PDF-FILES/su ey.pd ) [4] Z.-d. Shao and J.-z. Liu, The L(3,2,1)−labeling p oblem on g aphs, Ma h. Appl. 17 (2004), 596-602. [5] Z. Shao, The L(d1, d2, d3)−labeling on g aphs, J. Nanjing Uni . Ma h. Biqua . 21 (2004), 234-238. [6] J. Clippe on, J. Geh z, Zs. Szaniszló and D. To ko no, L(3,2,1)−labeling o simple g aphs, VERUM, Valpa iso Uni e e- si y, 2006. h p://www. alpo.edu/mcs/pd /zslabeling.pd [7] M.-L. Chia, D. Kuo, H.-Y. Liao, C.-H. Yang and R. K. Yeh, L(3,2,1)−labeling o g aphs, Taiwanese J. Ma h. 15 (2011), 2439-2457. [8] J. Geo ges, D. W. Mau o, M. Whi lesey. Rela ing pa h co e ing o e ex labelings wi h a condi ion a dis ance wo. Disc e e Ma h., 135 (1994), pp. 103-111 [9] G. J. Chang, D. Kuo. The L(2,1)-labeling on g aphs. SIAM J. Disc e e Ma h., 9 (1996), pp. 309-316 [10] G. J. Chang, W. -T. Ke, D. Kuo, D. D. -F. Liu, R. K. Yeh. On L(d,1)- labelings o g aphs. Disc e e Ma h., 220 (2000), pp. 57-66 73 [11] J. Geo ges, D. W. Mau o. Gene alized e ex labelings wi h a condi ion a dis ance wo. Cong . Nume ., 109 (1995), pp. 141-159 [12] J. P. Geo ges, D. W. Mau o. Labeling ees wi h a condi ion a dis ance wo. Disc e e Ma h., 269 (2003), pp. 127-148 [13] H. L. Bodlaende , T. Kloks, R. B. Tan, J. V. Leeuwen. λ−colo ing o g aphs. Lec u e No es in Compu e Science, ol. 1770, Sp inge , Be lin, Heidelbe g, 2000, pp. 395-406 [14] T. Calamone i, R. Pe eschi. L(h,1)-labeling subclasses o plana g aphs. J. Pa allel Dis ib. Compu ., 64 (2004), pp. 414-426 [15] K. Jonas. G aph colo ings analogues wi h a condi ion a dis ance wo: L(2,1)-labelings and lis −λ−labelings. Ph.D. Thesis, Depa men o Ma hema ics, Uni e si y o Sou h Ca olina, Columbia, SC, USA, 1993 [16] W. -F. Wang, K. -W. Lih. Labeling plana g aphs wi h condi ions on gi h and dis ance wo. SIAM J. Disc e e Ma h., 17 (2003), pp. 264-275 [17] M. C. Golumbic. Algo i hmic G aph Theo y and Pe ec G aphs. Aca- demic P ess, New Yo k (1980) [18] D. B. Wes . In oduc ion o G aph Theo y (second ed.) P en ice-Hall, Englewood di s., NJ (2001) [19] D. Sakai. Labeling cho dal g aphs wi h a condi ion a dis ance wo. SIAM J. Disc e e Ma h., 7 (1994), pp. 133-140 [20] A. A. Be ossi, M. C. Pino i, R. Rizzi. Channel assignmen on s ongly- simplicial g aphs. IEEE P oceedings o he In e na ional Pa allel and Dis ibu ion P ocessing Symposium, 2003 [21] M. Whi lesey, J. Geo ges, D. W. Mau o. On he λ−numbe o Qnand ela ed g aphs. SIAM J. Disc e e Ma h., 8 (1995), pp. 499-506 74 [22] H. W. Chang, H. W. Chou, D. Kuo and C. L. Lin, Labeling g aphs wi h wo dis ance cons ain s, Disc. Ma h. 308 (23) (2008), 5645-5655. [23] S. H. Chiang and Y. H. Yan, On L(d, 1)−labeling o Ca esian p oduc o a cycle and a pa h, Disc. Appl. Ma h. 156(15) (2008), 2867-2881. [24] J. P. Geo ges, D. W. Mau o. On gene alized Pe e sen g aphs labeled wi h a condi ion a dis ance wo. Disc e e Ma h., 259 (2003), pp. 311- 318 [25] D. K ál’, R. Šk eko ski. A heo em abou channel assignmen p oblem. SIAM J. Disc e e Ma h., 16 (2003), pp. 426-437 [26] D. Goncal es. On he L(p,1)-labelling o g aphs. Disc. Ma h. 308, 1405- 1414 (2008) [27] J. Geo ges, D. W. Mau o. On he size o g aphs labeled wi h a condi ion a dis ance wo. J. G aph Theo y, 22 (1996), pp. 47-57 [28] R. K. Yeh. The edge span o dis ance wo labelings o g aphs. Taiwanese J. Ma h., 4 (2000), pp. 675-683 [29] P. C. Fishbu n, F. S. Robe s. Minimum o bidden g aphs o L(2,1)- colo ings. DIMACS Technical Repo 2000-32, 2000 [30] F. Ha e , M. -L. Yu. (p,1)- o al labelling o g aphs. Disc. Ma h. 308, 496-513 (2008) [31] F. Bazza o, M. Mon assie , A. Raspaud. (d,1)- o al labelling o plana g aphs wi h la ge gi h and high maximum deg ee. Disc. Ma h. 307, 2141-2151 (2007) [32] S. Fio ini. On he ch oma ic index ou e plana g aphs. J. Combin. The- o y Se . B18, 35-38 (1975) 75 [33] T. Hasunuma, T. Ishii, H. Ono, Y. Uno. The (p,q)- o al labeling p oblem o ees. Disc. Ma h., 312 (8), 1407-1420 (2012) [34] H. L. Bodlaende , T. Kloks, R. B. Tan, J. an Leeuwen. App oxima ions o λ−colo ing o g aphs. The Compu e Jou nal 47, 193-204 (2004) [35] J. Fiala, P. A. Golo ach, J. K a och íl. Dis ance cons ained labelings o g aphs o bounded eewid h. P oc. 32 h ICALP, 360-372 (2005) [36] N. Eggemann, F. Ha e , S. D. Noble. k-L(2,1)-labelling o plana g aphs is NP-comple e o k≥4. Disc. Appl. Ma h., 158 (16), 1777-1788 (2010) [37] J. Fiala, J. K a och íl. On he compu a ional complexi y o he L(2,1)- labeling p oblem o egula g aphs. P oceedings o 11 h I alian Con . on Theo e ical Compu e Science (ICTCS ’05), Siena, I aly, 12-14 Oc obe , pp. 228-236, Lec u e No es in Compu e Science 3701, Sp inge Ve lag, Be lin [38] G. Cha and, D. E win, F. Ha a y and P. Zhang, Radio Labelings o g aphs, Bull. Ins . Combin. Appl. 33 (2001), 77-85. [39] D. D.-F. Liu and X. Zhu, Mul i-le el dis ance labelings o pa hs and cycles, SIAM J. Disc e e Ma h. 19 (2005), 610-621). [40] D. D.-F. Liu and M. Xie, Radio numbe o squa e o cycles, Cong . Nume . 169 (2004), 105-125. [41] D. D.-F. Liu and M. Xie, Radio numbe o squa e pa hs, A s Combin. 90 (2009), 307-319. [42] B. Soo yana ayana, M. Vishu Kuma and K. Manjula, Radio numbe o cube o a pa h, In e na ional J. Ma h. Combin. 1 (2010), 05-29. [43] D. D.-F. Liu, Radio numbe o ees, Disc e e Ma h. 308 (2008), 1153- 1164. 76 [44] M. Kchikech, R. Khennou a and O. Togni, Radio k−labelings o Ca e- sian p oduc s o g aphs, Discuss. Ma h. G aph Theo y 28 (2008), 165- 178. [45] S. R. Kola and P. Panig ahi, An imp o ed lowe bound o he adio k−ch oma ic numbe o he hype cube Qn, Compu e s Ma h. Appl. 60 (2010), 2131-2140. [46] M. Mo is-Ri e a, M. Tomo a, C. Wyels and A. Yeage , The adio num- be o p oduc s o cycles. A s Combin., o appea . [47] R. Khennou a and O. Togni, The adio an ipodal and adio numbe s o he hype cube, A s Comb. 102 (2011), 447-461. [48] J. Flo es and K. A. Lewis, Radio numbe s o ladde g aphs, pos e , Augus 2008, h p:// acul y.csuci.edu/cyn hia.wyels/ eu/2008wo k/ 08Aug08%20Final%20Ladde %Pos e .pd [49] H. Wang, X. Xu, Y. Yang, B. Zhang, M. Luo and G. Wang, Radio numbe o ladde g aphs, In . J. Compu . Ma h. 88 (2011), 2026-2034. [50] J. A. Gallian, A dynamic su ey o g aph labeling, Elec onic Jou nal o Combina o ics, (2014) #DS6, 308 pages. [51] X. Li, V. Mak and S. Zhou, Op imal adio labellingso comple e m−a y ees, Disc e e Applied Ma h. 158 (2010), 507-515. [52] M. G ö schel, L. Lo ász, A. Sch ij e , Geome ic algo i hms and com- bina o ial op imiza ion. Sp inge . Be lin, 1988. ISBN 978-0387136240. Pages 11 and 12. [53] M. R. Ga ey, D. S. Johnson, Compu e s and in ac abili y, a guide o he heo y o NP-comple eness. A se ies o books in he ma hema ical sciences. W. H. F eeman, 1979. ISBN 978-0716710455. Page 18. 77 [54] C. J. Colbou n and J. H. Dini z (eds.), Handbook o ícombina o ial Designs , 2nd edi ion, Chapman & Hall /CRC, 2007 [55] T. P. Ki kman, On a p oblem in combina ions, Camb idge and Dublin Ma h. J. 2 (1847), 191-204. [56] J. A. Bondy and J. L. Szwa c i e , Induced decomposi ions o g aphs, Jou nal o G aph Theo y 72 (2013), 462-477. [57] P. F ankl and Z. Fü edi, Colo ed packing o se s, Annals o Disc e e Ma hema ics 34 (1987), 165-178. [58] R. M. Wilson, Decomposi ions o comple e g aphs in o subg aphs iso- mo phic o a gi en g aph, P oc. 5 h B i ish Combina o ial Con e ence, Cong essus Nume an ium XV (1976), 647-659. [59] N. Cohen and Zs. Tuza, Induced decomposi ions o highly dense g aphs, submi ed (2012). 78 Index A algo i hmic complexi y, 20 ances o , 31 lowes common ances o , 32 asymp o ic uppe bound, 58 B balanced incomple e block designs, 57 bina y a iables, 45 C Ca esian p oduc , 12 cen al edge, 23 cen al e ex, 21 child, 31 cho dal g aph, 10 ch oma ic index, 19 ch oma ic numbe , 4 classical model, 45 clique, 10 −clique, 10 colo ing models, 2 combina o ial op imiza ion, 67 complemen , 16 complemen a y neighbo hood, 60 comple e bipa i e, 63 comple e equipa i e, 59 comple e g aph, 24, 26 comple e m -a y ee, 22 comple e mul ipa i e, 59 comple e ipa i e, 61 componen , 3 connec ed g aph, 4 c i ical g aph, 18 cube n–cube, 13 cycle, 6 D degene a e g aph s–degene a e g aph, 19 dense induced packing, 65 descendan s, 37 diame e , 5 disconnec ed g aph, 3 dis ance ma ix, 52 E edge decomposi ions, 57 edge span, 17 edge-disjoin , 57 Euclidean dis ance, 45 Euclidean model, 46 ex emal, 59 F easible solu ion, 44 equency assignmen , 1 79