Univerzitet u Kragujev u Prirodno-matemati~ki fakultet Tatjana Aleksi} GRAFOVI ^IJA JE NAJMAWA KARAKTERISTI^NA VREDNOST MINIMALNA U NEKIM KLASAMA GRAFOVA Doktorska diserta ija Kragujeva , 2012. IDENTIFIKACIONA STRANICA DOKTORSKE DISERTACIJE I. Autor Ime i prezime: Tatjana Aleksi} Datum i mesto ro|ewa: 17.06.1982.Kragujeva Sada{we zaposlewe: asistent na Prirodno-matemati~kom fakultetu, Univerzitet u Kragujev u II. Doktorska diserta ija Naslov: Grafovi ~ija je karakteristi~na vrednost minimalna u nekim klasama grafova Broj strani a: 101 Broj slika: 29 Broj bibliografskih podataka: 49 Ustanova i mesto gde je rad izra|en: Prirodno-matemati~ki fakultet, Univerzitet u Kragujev u Nau~na oblast (UDK): Matematika (Spektralna teorija grafova) Mentor: Dr Miroslav Petrovi} III. O ena i odbrana Datum prijave teme: 10.06.2011. Broj odluke i datum prihvatawa doktorske diserta ije: Komisija za o enu podobnosti teme i kandidata: Dr Miroslav Petrovi} - redovni profesor Prirodnomatemati~kog fakulteta u Kra- gujev u Dr Slobodan Simi} - nau~ni savetnik Matemati~kog instituta u Beogradu Dr Ivan Gutman - redovni profesor Prirodnomatemati~kog fakulteta u Kragujev u Dr Mirko Lepovi} - vanredni profesor Prirodnomatemati~kog fakulteta u Kragu- jev u Dr Bojana Borovi}anin - do ent Prirodnomatemati~kog fakulteta u Kragujev u Komisija za o enu i odbranu doktorske diserta ije: Dr Miroslav Petrovi} - redovni profesor Dr`avnog univerziteta u Novom Pazaru Dr Slobodan Simi} - nau~ni savetnik Matemati~kog instituta u Beogradu Dr Ivan Gutman - redovni profesor Prirodnomatemati~kog fakulteta u Kragujev u Dr Mirko Lepovi} - vanredni profesor Prirodnomatemati~kog fakulteta u Kragu- jev u Dr Bojana Borovi}anin - do ent Prirodnomatemati~kog fakulteta u Kragujev u Datum odbrane diserta ije: 08.10.2012. 1 Predgovor Ova doktorska diserta ija je proistekla kao rezultat vi{egodi{weg rada pod mentorstvom dr Miroslava Petrovi}a, redovnog profesora na Prirodno-matemati~kom fakultetu Univerziteta u Kragujev u. Tema istra`ivawa doktorske diserta ije je karakteriza ija ekstremal- nih grafova u razli~itim klasama povezanih grafova. Pod ekstremalnim grafovima podrazumevaju se grafovi sa minimalnom najmawom karakteri- sti~nom vredno{}u, maksimalnim indeksom ili maksimalnim rasponom u odre|enim klasama grafova. U ovoj doktorskoj diserta iji rezultati su do- bijeni u klasama povezanih grafova sa fiksiranim brojem ~vorova i grana (u klasama uni ikli~nih, bi ikli~nih, tri ikli~nih, tetra ikli~nih i penta ikli~nih grafova), u klasi kaktusa sa fiksiranim brojem ~vorova i fiksiranim brojem kontura kao i u klasi kaktusa sa fiksiranim brojem ~vorova. U periodu od 2007. do 2011. godine rezultati ovog istra`ivawa obja- vqeni su u okviru projekta Teorija grafova i matemati~ko programirawe sa primenama u hemiji i tehni~kim naukama (finansiranog od strane Mi- nistarstva nauke Republike Srbije) pod rukovodstvom akademika Drago{a Cvetkovi}a, a zatim od 2011. godine u okviru projekta Teorija grafova i matemati~ko programirawe sa primenama u hemiji i ra~unarstvu (finan- siranog od strane Ministarstva prosvete i nauke Republike Srbije) pod rukovodstvom profesora dr Slobodana Simi}a. Ovom prilikom posebno se zahvaqujem svom mentoru dr Miroslavu Pe- trovi}u na stru~noj pomo}i i velikoj podr{ i koju mi je svakodnevno pru`ao od po~etka na{e saradwe. Zahvalnost dugujem i akademiku dr Ivanu Gutmanu na saradwi u toku doktorskih studija, koja mi je zna~ajno pomogla u razumevawu ~itave oblasti. elim da se zahvalim akademiku dr Drago{u Cvetkovi}u i dr Slobodanu Simi}u sa kojima sam imala izuzetnu saradwu u okviru seminara SANU, na projektima pod wihovim rukovodstvom. Tako|e, zahvaqujem se dr Mirku Lepovi}u i dr Bojani Borovi}anin na odli~noj saradwi, pomo}i i korisnim sugestijama tokom doktorskih studija. Na kraju, najiskrenije se zahvaqujem svojoj porodi i, prijateqima i meni dragim qudima koji su od prvog dana verovali u mene, na strpqewu, po`rtvovanosti i qubavi koje su mi nesebi~no pru`ali svih ovih godina. Kragujeva , april 2012. Tatjana Aleksi} 2 Sadr`aj Predgovor 2 Lista slika 5 Lista tabela 6 1 Uvod 8 2 Spektar grafa 12 3 O grafovima ~ija je najmawa karakteristi~na vrednost minimalna 20 3.1 Struktura ekstremalnih grafova . . . . . . . . . . . . . . . . . 21 3.2 Struktura ekstremalnih bipartitnih grafova . . . . . . . . . 28 4 Grafovi sa malim brojem kontura i minimalnom najmawom karakte- risti~nom vredno{}u 37 4.1 Uni ikli~ni grafovi fiksiranog reda . . . . . . . . . . . . . 38 4.1.1 Bipartitni uni ikli~ni grafovi . . . . . . . . . . . . 39 4.1.2 Nebipartitni uni ikli~ni grafovi . . . . . . . . . . 40 4.1.3 Struktura ekstremalnog uni ikli~nog grafa . . . . . . 41 4.2 Bi ikli~ni grafovi fiksiranog reda . . . . . . . . . . . . . . 42 4.2.1 Bipartitni bi ikli~ni grafovi . . . . . . . . . . . . . 43 4.2.2 Nebipartitni bi ikli~ni grafovi . . . . . . . . . . . 47 4.2.3 Struktura ekstremalnog bi ikli~nog grafa . . . . . . 47 4.3 Tri ikli~ni, tetra ikli~ni i penta ikli~ni grafovi fiksiranog reda . . . . . . . . . . . . . . . . . . . . . 49 4.3.1 Nebipartitni grafovi sa malim brojem kontura . . . . 49 4.3.2 Struktura ekstremalnog grafa sa malim brojem kontura 53 5 Ekstremalni kaktusi 56 5.1 Ekstremalni grafovi u klasi kaktusa sa fiksiranim brojem ~vorova i fiksiranim brojem kontura . . . . . . . . . . 57 5.2 Ekstremalni grafovi u klasi kaktusa sa fiksiranim brojem ~vorova . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3 SADRAJ 6 Grafovi sa malim brojem kontura i maksimalnim rasponom 73 A Dodatne tabele 86 A.1 Povezani grafovi sa 2 do 5 ~vorova . . . . . . . . . . . . . . . 86 A.2 Povezani bi ikli~ni grafovi sa 6 ~vorova . . . . . . . . . . . 90 B Summary 93 Literatura 95 Biografija 99 4 Lista slika 2.1 GrafoviG i G∗ . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 GrafWn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 Grafovi A i B . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1 Lan~ani graf visine 1 . . . . . . . . . . . . . . . . . . . . . . . 29 3.2 Lan~ani graf visine 2 . . . . . . . . . . . . . . . . . . . . . . . 30 3.3 Lan~ani grafoviD1 i Dk+1 . . . . . . . . . . . . . . . . . . . . 34 3.4 Lan~ani graf G = D(1, m2, m3;n1, n2, n3) . . . . . . . . . . . . 35 4.1 Uni ikli~ni graf U1 . . . . . . . . . . . . . . . . . . . . . . . . 39 4.2 Uni ikli~ni graf U2 . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3 Bi ikli~ni grafovi B1, B2 i B3 . . . . . . . . . . . . . . . . . 43 4.4 Osnova G0 bi ikli~nog grafa . . . . . . . . . . . . . . . . . . . 44 4.5 GrafH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.6 Bi ikli~ni graf B4 . . . . . . . . . . . . . . . . . . . . . . . . 47 4.7 Graf Gq za q > 0 i i < j . . . . . . . . . . . . . . . . . . . . . . 50 4.8 Kanoni~ki graf grafa Gq za q > 0 i i < j . . . . . . . . . . . . 50 4.9 Graf G0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.1 Sve`aw G(C1, . . . , Ck; r) . . . . . . . . . . . . . . . . . . . . . . 57 5.2 Sve`aw Bk,s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.3 GrafoviG1, G2 i G3 . . . . . . . . . . . . . . . . . . . . . . . . 58 5.4 Dijagram 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 6.1 Uni ikli~ni grafovi U1 i U2 . . . . . . . . . . . . . . . . . . . 75 6.2 Grafovi B4 i B ′ 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.3 Grafovi B6, B ′ 6 i B ′′ 6 . . . . . . . . . . . . . . . . . . . . . . . . 76 6.4 Graf B5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6.5 Graf G0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 6.6 Graf B0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 6.7 Graf B2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 A.1 Povezani grafovi reda 2 6 n 6 5 . . . . . . . . . . . . . . . . . 88 A.2 Povezani bi ikli~ni grafovi reda 6 . . . . . . . . . . . . . . 91 5 Lista tabela 4.1 Vrednosti parametara t1 i n0 za 0 6 k 6 4 . . . . . . . . . . . . 55 5.1 Najmawe sopstvene vrednosti, indeksi i rasponi sve`weva Bk,s za 3 6 n 6 14 i 1 6 k 6 1 2 (n− 1) . . . . . . . . . . . . . . . 72 6.1 Rasponi grafova B2 i B4 za 5 6 n 6 27 . . . . . . . . . . . . . . 84 A.1 Najmawe sopstvene vrednosti, indeksi i rasponi povezanih grafova reda 2 6 n 6 5 . . . . . . . . . . . . . . . . . . . . . . . 89 A.2 Najmawe sopstvene vrednosti, indeksi i rasponi povezanih bi ikli~nih grafova reda 6 . . . . . . . . . . . . . . . . . . . . 92 6 Priroda je ogromna kwiga u kojoj je napisana nauka. Ona je stalno otvorena pred na{im o~ima, ali je ~ovek ne mo`e razumeti ukoliko prethodno ne nau~i jezik i slova kojim je napisana. A napisana je ona jezikom matematike.  Galileo Galilej  Glava 1 Uvod Grafovi predstavqaju sveprisutne modele, kako prirodnih struktura, tako i struktura koje je kreirao ~ovek. Oni se mogu koristiti za predsta- vqawe razli~itih vrsta rela ija i dinami~kih pro esa u fizi i, hemiji, biologiji, ekonomiji, so iolo{kim mre`ama. Nemogu}e je utvrditi kada su qudi po~eli da koriste dijagrame, koje danas nazivamo grafovima, za mode- lirawe razli~itih sistema iz realnog `ivota. Matemati~ari su, me|utim, tek pre nekoliko vekova po~eli da se bave wima, tako da je teorija grafova relativno mlada nauka. Leonhard Euler je 1736. godine objavio rad Sedam mostova Konigsberga ∗ , koji se smatra prvim radom u istoriji teorije gra- fova. Kao posebna matemati~ka dis iplina teorija grafova je zasnovana 1936. godine kada je Denes Ko¨nig objavio kwigu Teorija kona~nih i bes- kona~nih grafova † i tada po~iwu prva ve}a istra`ivawa u ovoj teoriji. Svoj intenzivni razvoj, veliku popularnost i primenu, teorija grafova je do`ivela sa pove}awem upotrebe ra~unara, u drugoj polovini dvadesetog veka. Od pomo}nog dijagrama za slikovit opis problema, graf postaje jedan od osnovnih matemati~kih pojmova. Pre nekoliko de enija, matemati~ari su uvideli mogu}nost da se rezul- tati linearne algebre, koja ukqu~uje teoriju matri a, iskoriste u teoriji grafova i wenim primenama. Tada, uvo|ewem novih na~ina rezonovawa, do{lo je do nastanka spektralne teorije grafova, koja se danas smatra po- sebnom matemati~kom teorijom. Osobine grafa danas se izu~avaju pomo}u sopstvenih vrednosti, odnosno spektra matri e pridru`ene grafu, kao i wenih sopstvenih vektora i sopstvenih potprostora. Pokazano je da spek- tar grafa daje mno{tvo informa ija o strukturi grafa, {to je dovelo do wegove velike primene, po~ev od primene u hemiji, biologiji, medi ini, pa sve do primene u ekonomiji, opera ionim istra`ivawima, elektrotehni ii sve prisutnije primene u informati i. Najzna~ajniji rezultati ove teorije sumirani su u monografijama [10, 11, 13]. ∗Seven Bridges of Ko¨nigsberg †Theorie der endlichen und unendlichen Graphen 8 1. UVOD Jedna od interesantnih tema u spektralnoj teoriji grafova je izu~avawe grafova sa ekstremalnim (maksimalnim ili minimalnim) indeksom, ekstre- malnom najmawom karakteristi~nom vredno{}u ili maksimalnim raspo- nom ‡ me|u grafovima posmatrane klase. Grafove sa pomenutim osobinama nazivamo ekstremalnim grafovima. Problem odre|ivawa ekstremalnih grafova uveli su Collatz i Sinogovitz 1957. godine [8] bave}i se problemom indeksa stabala. Lovasz i Pelikan [28] su, zatim, pokazali da me|u stablima sa fiksiranim brojem ~vorova najve}i indeks ima zvezda, a najmawi indeks ima put. Do danas je poznato mnogo rezultata o grafovima koji su ekstremalni u smislu indeksa. Odre|eni su, na primer, grafovi sa maksimalnim indeksom me|u povezanim grafo- vima [3], me|u grafovima sa fiksiranim brojem grana [36], bi ikli~nim grafovima fiksiranog obima [48] kao i grafovi sa minimalnim indeksom u raznim klasama grafova [34, 46, 47]. U vezi sa najmawom karakteristi~nom vredno{}u jo{ uvek nije objavqeno mnogo rezultata. Istra`ivawa se uglav- nom svode na odre|ivawe grafa ~ija je najmawa karakteristi~na vrednost minimalna u odre|enoj klasi. Prvi radovi na ovu temu se pojavquju 2008. godine. Rezultati su dobijeni za uni ikli~ne grafove [16], komplemente stabala [17], bi ikli~ne grafove [33], kaktuse [32], grafove sa artikula io- nim ~vorovima [43], itd. Ova diserta ija se najve}im delom bavi grafovima koji su ekstremalni u smislu minimalne najmawe karakteristi~ne vredno- sti u odre|enim klasama, tako da su neki od pomenutih rezultata sadr`ani u diserta iji. Pored toga, prikazani su i rezultati o grafovima koji imaju maksimalni raspon u nekim klasama grafova. Diserta ija se sastoji iz {est glava i dodatka. Prva glava je uvodnog karaktera. U woj je predstavqen kratak istori- jat spektralne teorije grafova kao i motiva ija za rad sa ekstremalnim grafovima. U drugoj glavi ove diserta ije uvedeni su osnovni pojmovi i karakte- ristike grafova, polinoma i matri a i definisan je pojam spektra grafa i wegove osobine. Navedene su leme koje su zatim kori{}ene u dokazima rezultata ostalih poglavqa. U tre}oj glavi su predstavqeni rezultati u vezi sa strukturom grafa koji ima minimalnu najmawu karakteristi~nu vrednost u klasi povezanih grafova fiksiranog reda i veli~ine. Ova glava je inspirisana radovima ~iji su autori Bell, Cvetkovi}, Rowlinson i Simi} [4, 5] a koji su fun- damentalni za ovu tematiku. Tako|e, predstavqeni su rezultati koje je A. Sawikowska [37] dobila bave}i se sli~nom tematikom. Na kraju pogla- vqa, posebna pa`wa je posve}ena ekstremalnim bipartitnim grafovima pomenute klase, baziranim na rezultatima rada [31]. ^etvrta glava diserta ije se bavi ekstremalnimgrafovima u klasama po- vezanih grafova sa malim iklomati~nim brojem. Dobijeni su jedinstveni ‡ Raspon grafa se defini{e kao razlika izme|u najve}e i najmawe karakteristi~ne vred- nosti grafa. 9 1. UVOD grafovi koji imaju minimalnu najmawu karakteristi~nu vrednost me|u uni- ikli~nim i bi ikli~nim grafovima a zatim je izvr{eno uop{tewe re- zultata na sve c ikli~ne grafove za vrednosti 1 6 c 6 5. Ovo poglavqe se oslawa na radove [16, 31, 33], pri ~emu su u nekim rezultatima tehnike dokazivawa izmewene. U petoj glavi, koja sadr`i rezultate radova [2] i [32] predstavqeni su ekstremalni grafovi u klasi kaktusa. Naime, me|u svim kaktusima fik- siranog reda sa fiksiranim brojem kontura opisana je struktura kaktusa sa maksimalnim indeksom, kaktusa sa minimalnom najmawom sopstvenom vredno{}u i kaktusa sa maksimalnim rasponom. Neki rezultati su zatim pro{ireni na klasu svih kaktusa fiksiranog reda. Pokazano je da dobijeni kaktusi imaju oblik sve`wa. [esta glava je bazirana na radovima [1, 6, 12, 16, 31, 32, 33] i bavi se grafovima koji su ekstremalni u smislu maksimalnog raspona. Ovaj pro- blem je re{en u klasama povezanih uni ikli~nih i bi ikli~nih grafova, kao i u klasama tri ikli~nih, tetra ikli~nih i penta ikli~nih grafova dovoqno velikog reda. Kako je problem odre|ivawa maksimalnog raspona u bliskoj vezi sa problemom odre|ivawa maksimalnog indeksa i minimalne najmawe karakteristi~ne vrednosti u datoj klasi grafova, u ovom poglavqu su kori{}eni rezultati prethodnih poglavqa. Dodatak A ove diserta ije sadr`i slike svih povezanih grafova sa ma- we od {est ~vorova i tabelu wihovih indeksa, najmawih karakteristi~nih vrednosti i raspona. Tako|e, prikazani su i svi povezani bi ikli~ni grafovi sa {est ~vorova i wihovi indeksi, najmawe karakteristi~ne vred- nosti i rasponi. Neke od ovih vrednosti kori{}ene su u dokazima rezultata u prethodnim glavama. U dodatku B, na kraju doktorske diserta ije, na engleskom jeziku su ukratko sumirani svi prethodno prikazani rezultati. Najva`niji doprinos autora u ovoj diserta iji ogleda se u slede}im rezultatima: • karakteriza ija grafova ~ija je najmawa karakteristi~na vrednost minimalna u klasi povezanih bipartitnih grafova fiksiranog reda i veli~ine (sek ija 3.2, teoreme 4 i 5, prema rezultatima rada [31]); • karakteriza ija grafova ~ija je najmawa karakteristi~na vrednost minimalna u klasi povezanih bi ikli~nih grafova (sek ija 4.2, prema rezultatima rada [33]); • karakteriza ija grafova ~ija je karakteristi~na vrednost minimalna u klasi povezanih grafova sa malim iklomati~nim brojem (sek ija 4.3, prema rezultatima rada [31]); • karakteriza ija grafova ~ija je najmawa karakteristi~na vrednost minimalna u klasi kaktusa fiksiranog reda sa fiksiranim brojem kontura (sek ija 5.1, prema rezultatima rada [32]); 10 1. UVOD • karakteriza ija grafova ~ija je najmawa karakteristi~na vrednost minimalna u klasi kaktusa fiksiranog reda (sek ija 5.2, prema rezul- tatima rada [32]); • karakteriza ija grafova ~iji je raspon maksimalan u klasi kaktusa fiksiranog reda sa fiksiranim brojem kontura (sek ija 5.1, prema rezultatima rada [2]); • karakteriza ija grafova ~iji je raspon maksimalan u klasama poveza- nih grafova sa malim brojem kontura (glava 6, prema rezultatima rada [1]). 11 Glava 2 Spektar grafa Graf G se mo`e definisati kao ure|eni par (V,E), gde je V kona~an neprazan skup elemenata koji se nazivaju ~vorovi grafa, a E skup dvo~lanih podskupova skupa V koji se nazivaju grane grafa G. Ovako definisan graf je kona~an, neorijentisan, bez petqi i vi{estrukih grana i nazivamo ga prostim grafom. Graf se naziva netrivijalnim ako sadr`i bar dva ~vora. Za grafG ka`emo da je reda n = |V | i veli~inem = |E|. Dva ~vora grafaG su susedna ukoliko postoji grana koja ih spaja. Broj ~vorova koji su susedni sa ~vorom v naziva se stepen ~vora v i ozna~ava sa d(v). Graf reda n ~iji su svi ~vorovi stepena n− 1 nazivamo kompletnim grafom i ozna~avamo sa Kn. ^vorovi stepena 0 i 1 u grafu nazivaju se izolovani i vise}i ~vorovi, respektivno. Za proizvoqan ~vor v grafa G, sa N(v) ozna~avamo skup svih suseda ~vora v u grafu G. Grafu G = (V,E) sa skupom ~vorova V = {v1, v2, . . . , vn} se na prirodan na~in mo`e pridru`iti (0, 1)-matri a susedstva A(G) = (aij)n×n koja se defini{e na slede}i na~in (2.1) aij = { 1, ako vivj ∈ E 0, ako vivj 6∈ E . Po{to je A(G) simetri~na matri a wene karakteristi~ne vrednosti su re- alni brojevi i nazivamo ih karakteristi~nim (sopstvenim) vrednostima (engl. eigenvalues) grafaG. Bez gubitka op{tosti, karakteristi~ne vredno- sti grafa G mo`emo pisati u nerastu}em poretku kao λ1(G) > λ2(G) > · · · > λn(G). Najve}u sopstvenu vrednost grafa G ozna~avamo sa ρ(G) i nazivamo je in- deksom ili spektralnim radijusom grafa G (engl. index, spectral radius). Najmawu sopstvenu vrednost grafa G ozna~avamo sa λ(G). Raspon grafa (engl. spread) predstavqa razliku izme|u najve}e i najmawe karakteristi~ne vrednosti grafa i ozna~ava se sa s(G) = ρ(G) − λ(G). Skup svih karak- teristi~nih vrednosti grafa nazivamo spektrom grafa (engl. spectrum). 12 2. SPEKTAR GRAFA Karakteristi~ni polinom grafa G (engl. eigenpolynomial) se defini{e kao det(λI −A(G)) i ozna~ava sa φ(G, λ). Povezan grafCn sa n ~vorova kod koga su svi ~vorovi stepena 2 nazivamo konturom du`ine n (engl. cycle). Povezani grafovi koji ne sadr`e konture su stabla (engl. trees) i ozna~avamo ih sa Tn, gde je n broj ~vorova stabla. Stablo sa n ~vorova kod koga je jedan ~vor stepena n−1 a svi ostali ~vorovi stepena 1 nazivamo zvezdom (engl. star), u ozna i S1,n−1. ^vor stepena n − 1 naziva se entar zvezde. Povezan grafPn san ~vorova koji ne sadr`ikonture i u kome nijedan ~vor nije stepena ve}eg od 2 nazivamo putem (engl. path). Lema 1 ([11]). Spektar puta Pn se sastoji iz brojeva oblika 2 cos pi n+1 k gde je k = 1, . . . , n. Povezan graf G je bipartitan ako se wegovi ~vorovi mogu podeliti u dva disjunktna skupa U i V tako da svaka grana u grafu G povezuje ~vor iz skupa U sa ~vorom iz skupa V . Bipartitan grafG je kompletan bipartitan (engl. complete bipartite) ako je svaki ~vor iz skupa U susedan sa svakim ~vorom iz skupa V . Kompletan bipartitan graf ozna~avamo sa Kp,q, gde je p broj elemenata skupa U a q broj elemenata skupa V . Zvezda S1,q je tako|e kompletan bipartitan graf K1,q. Graf G = G1∇G2 je kompletan proizvod (engl. join) dva disjunktna grafa G1 i G2 ako va`i V (G) = V (G1) ∪ V (G2) i E(G) = E(G1) ∪ E(G2) ∪ E, gde je E = {uv | u ∈ V (G1), v ∈ V (G2)}. Neka je G nepovezan graf sa komponentama povezanosti G1, G2, . . . , Gk, koje mo`emo posmatrati i kao samostalne grafove. Neka su A1, A2, . . . , Ak matri e susedstva redom grafova G1, G2, . . . , Gk. Tada je matri a susedstva grafa G oblika A(G) =  A1 0 · · · 0 0 A2 · · · 0 . . . . . . . . . . . . 0 0 · · · Ak  . O~igledno, karakteristi~ni polinom grafa G je (2.2) φ(G, λ) = φ(G1, λ) · φ(G2, λ) · . . . · φ(Gk, λ), odakle zakqu~ujemo da se spektar grafa G dobija objediwavawem spektara wegovih komponenti povezanostiG1, G2, . . . , Gk. Neka je X = (x1, x2, . . . , xn) T vektor kolona u R n i G graf sa ~vorovima v1, v2, . . . , vn. Tada seX mo`e posmatrati kao funk ija definisana na skupu ~vorova grafa G koja proizvoqni ~vor vi preslikava u element xi = X(vi). Ka`emo da je xi vrednost ~vora vi data funk ijomX . Mo`e se pokazati da je (2.3) XTA(G)X = 2 ∑ vivj∈E(G) xixj 13 2. SPEKTAR GRAFA i da je λ karakteristi~na vrednost grafaG koja odgovara karakteristi~nom vektoruX ako i samo ako je X 6= 0 i (2.4) λxi = ∑ vivj∈E(G) xj (i = 1, 2, . . . , n). Jedna~ine (2.4) nazivaju se (λ,X)karakteristi~ne jedna~ine grafa G. Tako|e, za proizvoqni jedini~ni vektor X = (x1, x2, . . . , xn) T ispuwena je nejednakost λ(G) 6 XTA(G)X. Jednakost se posti`e ako i samo ako je X karakteristi~ni vektor matri e A(G) koji odgovara najmawoj karakteristi~noj vrednosti λ(G) (videti [13]). Stoga, (2.5) λ(G) = min ‖X‖=1 XTA(G)X = min ‖X‖=1 2 ∑ vivj∈E(G) xixj . Sli~no, (2.6) ρ(G) = max ‖X‖=1 XTA(G)X = max ‖X‖=1 2 ∑ vivj∈E(G) xixj . Spektralni radijus povezanog grafa je prosta karakteristi~na vrednost i postoji jedinstveni karakteristi~ni vektor koji joj odgovara i ~ije su sve koordinate pozitivne. Ovaj karakteristi~ni vektor se naziva Peronov vektor grafa G. Lema 2 ([44]). Neka je G proizvoqan graf reda n i X jedini~ni vektor iz Rn. Ako je ρ(G) = XTA(G)X , tada je A(G)X = ρ(G)X . Lema 3 ([44]). Neka je G povezan graf reda n i ρ(G) wegov spektralni radijus. Neka su u, v dva ~vora grafa G i d(v) stepen ~vora v. Pretpostavimo da v1, v2, . . . , vs ∈ N(v) \ N(u) (1 6 s 6 d(v)) i da je X = (x1, x2, . . . , xn)T Peronov vektor grafa G, gde koordinata xi odgovara ~voru vi (1 6 i 6 n). Neka je G∗ graf dobijen iz grafa G uklawawem grana vvi i dodavawem grana uvi (1 6 i 6 s). Ako je xv 6 xu, tada je ρ(G) < ρ(G ∗). Dokaz. Primetimo da je XT (A(G∗)− A(G))X = 2 s∑ i=1 xi(xu − xv) > 0. Sada je na osnovu (2.6) (2.7) ρ(G∗) = max ||Y ||=1 Y TA(G∗)Y > XTA(G∗)X > XTA(G)X = ρ(G), 14 2. SPEKTAR GRAFA odnosno ρ(G) 6 ρ(G∗). Da bismo dokazali teoremu pretpostavimo suprotno, tj. ρ(G∗) = ρ(G). Tada u rela iji (2.7) svuda va`e jednakosti i ρ(G∗) = XTA(G∗)X. Na osnovu leme 2 sledi da je A(G∗)X = ρ(G∗)X , pa dobijamo (2.8) ρ(G∗)xv = (A(G∗)X)v = ∑ vi∈NG∗ (v) xi. Tako|e, kako je A(G)X = ρ(G)X , onda je (2.9) ρ(G)xv = (A(G)X)v = ∑ vi∈NG(v) xi = ∑ vi∈NG∗ (v) xi + s∑ i=1 xi. Po{to je X Peronov vektor grafa G sve wegove koordinate su pozitivne, pa je i ∑s i=1 xi > 0. Iz (2.8) i (2.9) sada dobijamo ρ(G∗)xv < ρ(G)xv. Odavde je ρ(G∗) < ρ(G), {to je nemogu}e. Neka su G1 i G2 dva razli~ita povezana grafa i neka su u i v wihovi ~vorovi, pri ~emu u ∈ V (G1) i v ∈ V (G2). Za graf G ka`emo da predsta- vqa koales en iju (engl. coalescence) korenskih grafova G1 i G2, i pi{emo G = G1(u) · G2(v), ukoliko je G dobijen iz grafova G1 i G2 preklapawem wihovih korena u i v. PSfrag repla ements v1 v2 u G1 G2 G PSfrag repla ements v1 v2 u G1 G2 G∗ Slika 2.1. GrafoviG i G∗ Lema 4 ([16]). Neka su G1 i G2 dva razli~ita netrivijalna povezana grafa i v1, v2 ∈ V (G1), u ∈ V (G2). Neka je G = G1(v1) · G2(u) i G∗ = G1(v2) · G2(u) (slika 2.1). Ako jeX karakteristi~ni vektor koji odgovara karakteristi~noj vrednosti λ(G) i |xv1 | 6 |xv2 |, tada je λ(G∗) 6 λ(G). Jednakost je ispuwena ako i samo ako je X karakteristi~ni vektor koji odgovara karakteristi~noj vrednosti λ(G∗), xv1 = xv2 i ∑ w∈NG2 (u) xw = 0. 15 2. SPEKTAR GRAFA Dokaz. Pretpostavimo da je X jedini~ni vektor i da je xv2 > 0. Neka je α = ∑ w∈NG2(u) xw. Neka je daqe E1 = {v1w ∈ E(G) | w ∈ NG2(u)} i E2 = {v2w ∈ E(G∗) | w ∈ NG2(u)}. Razmotrimo slede}a dva slu~aja, ozna~a- vaju}i ~vor vi kra}e sa i. 1◦ xv1 > 0 Kada je α 6 0, dobijamo 1 2 λ(G∗) 6 1 2 XTA(G∗)X = ∑ ij∈E(G∗) xixj = ∑ ij∈E(G∗)\E2 xixj + ∑ ij∈E2 xixj = ∑ ij∈E(G∗)\E2 xixj + xv2α 6 ∑ ij∈E(G)\E1 xixj + xv1α = ∑ ij∈E(G)\E1 xixj + ∑ ij∈E1 xixj = ∑ ij∈E(G) xixj = 1 2 XTA(G)X = 1 2 λ(G). Ako je λ(G∗) = λ(G), tada je X tako|e karakteristi~ni vektor grafa G∗ koji odgovara najmawoj karakteristi~noj vrednosti λ(G∗). Razmatrawem jednakosti (2.4) za λ(G∗) i vektor X , za proizvoqni ~vor iz NG2(u) i za ~vor v2, dobijamo da je xv1 = xv2 i α = 0, respektivno. Da su dati uslovi dovoqni za jednakost λ(G∗) = λ(G) lako se proverava kori{}ewem gorwih nejednakosti. Ako je α > 0, saX∗ ozna~imo vektor koji se dobija iz vektoraX zamenom svake koordinate xw sa−xw zaw ∈ V (G2)\{u}, dok ostale koordinate ostaju nepromewene. Sada imamo 1 2 λ(G∗) 6 1 2 (X∗)TA(G∗)X∗ = ∑ ij∈E(G∗) x∗ix ∗ j = ∑ ij∈E(G∗)\(E2∪E(G2−u)) x∗ix ∗ j + ∑ ij∈E2 x∗ix ∗ j + ∑ ij∈E(G2−u) x∗ix ∗ j . Kako je ∑ ij∈E2 x∗ix ∗ j = xv2 · (−α) 6 xv1 · α = ∑ ij∈E1 xixj i ∑ ij∈E(G2−u) x∗ix ∗ j = ∑ ij∈E(G2−u) xixj , dobijamo 1 2 λ(G∗) 6 ∑ ij∈E(G) xixj = 1 2 XTA(G)X = 1 2 λ(G). Ako je λ(G∗) = λ(G), onda je X∗ karakteristi~ni vektor grafa G∗ koji odgovara λ(G∗). Razmatrawem jednakosti (2.4) za λ(G∗) i X∗ za ~vor v2, dobijamo da je α = 0, {to je nemogu}e. Dakle, va`i da je λ(G∗) < λ(G). 16 2. SPEKTAR GRAFA 2◦ xv1 < 0 Ako je α 6 0 (α > 0) dokaz je veoma sli~an kao u slu~aju 1◦ za α 6 0 (α > 0). U oba slu~aja se pokazuje da jednakost ne mo`e biti ispuwena. Za grafH = (V1, E1) za koji va`i V1 ⊆ V i E1 ⊆ E ka`emo da je podgraf grafa G = (V,E) (engl. subgraph). Graf H je indukovani pograf grafa G (engl. induced subgraph) ako skup E1 sadr`i sve grane iz E koje povezuju ~vorove iz skupa V1. Lema 5 ([11]). Neka su λ1 > λ2 > · · · > λn karakteristi~ne vrednosti grafa G i µ1 > µ2 > · · · > µm karakteristi~ne vrednosti wegovog indukovanog podgrafa H . Tada va`e nejednakosti λn−m+i 6 µi 6 λi (i = 1, . . . , m). Ozna~imo sa G − v graf koji se dobija iz grafa G uklawawem ~vora v ∈ V (G). Slede}e rezultate }emo koristiti za nala`ewe karakteristi~nih polinoma grafova. Lema 6 ([38]). Neka je v ~vor grafaG i C(v) skup svih kontura uG koje sadr`e ~vor v. Tada va`i φ(G, λ) = λφ(G− v, λ) − ∑ uv∈E(G) φ(G− u− v, λ)− 2 ∑ Z∈C(v) φ(G− V (Z), λ), gde jeG−V (Z) grafdobijen od grafaG, uklawawem svih ~vorova koji pripadaju skupu Z. Lema 7 ([38]). Neka su H i G dva korenska grafa sa korenima v1 i v2, respek- tivno. Neka jeH ·G koales en ija grafovaH iG. Karakteristi~ni polinom koales en ije H ·G zadovoqava rela iju φ(H ·G, λ) = φ(H − v1, λ)φ(G, λ) + φ(H, λ)φ(G− v2, λ) − λφ(H − v1, λ)φ(G− v2, λ). Ozna~imo sada sa Gu,v graf dobijen iz povezanog grafa G podelom grane uv ∈ E(G), odnosno dodavawemnovog ~voraw i granawu iwv u grafG−uv. Hoffman i Smith u radu [20] defini{u unutra{wi put grafa G kao {etwu v0v1 . . . vs (s > 1) takvu da su ~vorovi v0, v1, . . . , vs razli~iti, d(v0) > 2, d(vs) > 2 i d(vi) = 2, za svako 0 < i < s. Ovde je s du`ina unutra{weg puta. Unutra{wi put je zatvoren ako je v0 = vs. Oni su dobili slede}i rezultat. PSfrag repla ements Slika 2.2. GrafWn 17 2. SPEKTAR GRAFA Lema 8 ([20]). Neka je uv grana u povezanom grafu G koji sadr`i n ~vorova. (i) Ako grana uv ne pripada unutra{wem putu u G i G 6= Cn, tada je ρ(Gu,v) > ρ(G). (ii) Ako grana uv pripada nekom unutra{wem putu u G i G 6=Wn, gde jeWn graf prikazan na sli i 2.2, tada je ρ(Gu,v) < ρ(G). Lema 9. Neka je G povezan korenski graf sa najmawe dva ~vora i korenom v. Ako su A i B grafovi sa slike 2.3, tada je: (i) ρ(A) < ρ(B), (ii) λ(A) > λ(B), (iii) s(A) < s(B). Dokaz. Neka je G povezan korenski graf sa najmawe dva ~vora i korenom v. (i) Ozna~imo sa u entralni ~vor zvezde S1,n+1, a sa w1, . . . , wn i v wene ~vorove stepena 1 (slika 2.3). Tako|e, ozna~imo sa v1, . . . , vs susede ~vora v u grafu G. Neka je X Peronov vektor grafa A sa slike 2.3, a xu i xv wegove koordinate koje odgovaraju ~vorovima u i v, redom. Ako je xu > xv ozna~imo sa G ∗ graf dobijen iz grafa G uklawawem grana vvi i dodavawem grana uvi (i = 1, . . . , s). Ako je pak xu < xv, neka je G∗ graf dobijen iz grafa G uklawawem grana uwj i dodavawem grana vwj (j = 1, . . . , n). U oba slu~aja dobijeni graf G∗ je graf B sa slike 2.3 i na osnovu leme 3 va`i da je ρ(A) < ρ(B). (ii) Neka je H1 = S1,n+1, H2 = S1,n i G1 graf indukovan skupom ~vorova V (G) ∪ {u}. Neka je daqe X karakteristi~ni vektor grafa A sa slike 2.3, koji odgovara sopstvenoj vrednosti λ(G), a xu i xv wegove koordinate koje odgovaraju redom ~vorovima u i v. Ako je |xu| > |xv| graf A mo`emo posmatrati kao koales en iju grafova H1(v) i G(v), tj. A = H1(v) · G(v). Neka je G∗ = H1(u) · G(v). Ako je pak |xu| < |xv|, graf A mo`emo posmatrati kao koales en iju A = H2(u) ·G1(u). Neka je sadaG∗ = H2(u) ·G1(v). U oba slu~aja dobijeni grafG∗ je grafB sa slike 2.3 i na osnovu leme 4 je λ(A) > λ(B). PSfrag repla ements A B n+ 1 vv u GG w2w1 wn Slika 2.3. Grafovi A i B 18 2. SPEKTAR GRAFA (iii) Direktnom primenom nejednakosti (i) i (ii) dolazimo do zakqu~ka da za grafove A i B sa slike 2.3 va`i s(A) < s(B). Nejednakosti (i) i (ii) iz prethodne leme dokazali su Simi} [39], odnosno Fan, Wang i Gao [16], respektivno. U wihovim dokazima kori{}ena je druga~ija tehnika nego u dokazima predstavqenim u ovoj tezi. Kao posledi u leme 9 dobijamo slede}u lemu. Lema 10. Neka jeG netrivijalan povezan graf, Tk stablo reda k i S1,k−1 zvezda reda k sa entrom w. Neka je G1 = G(u) · Tk(v) i G2 = G(u) · S1,k−1(w), za proizvoqne ~vorove u ∈ V (G) i v ∈ V (Tk). Ako je Tk 6= S1,k−1, tada je: (i) ρ(G1) < ρ(G2), (ii) λ(G1) > λ(G2), (iii) s(G1) < s(G2). Defini{imo sada, u skupu ~vorova V grafa G, binarnu rela iju ekvi- valen ije ∼ na slede}i na~in: ~vorovi u i v su ekvivalentni ako i samo ako imaju iste susede. Neka je V/∼ = {V1, V2, . . . , Vr} odgovaraju}i koli~nik skup. PodskupoviV1, V2, . . . , Vr (karakteristi~nipodskupovi grafaG) imaju slede}u osobinu: svaka dva ~vora iz istog podskupa su nesusedna, a svaka dva podskupa su kompletno susedna ili kompletno nesusedna u grafu G. Indukovani podgraf G ′ dobijen izborom po jednog ~vora iz svakog ka- rakteristi~nog podskupa naziva se kanoni~ki graf (engl. canonical graph) grafa G. Neka je daqe η(G) algebarska vi{estrukost nule u spektru grafa G, a η(G) broj od nule razli~itih sopstvenih vrednosti grafa G, ra~unaju}i i wihove algebarske vi{estrukosti. O~igledno, η(G) + η(G) = n, gde je n red grafa G. Lema 11 ([41, 42]). Ako je G graf i G ′ wegov kanoni~ki graf, tada je η(G) = η(G ′ ), tj. grafovi G i G ′ imaju isti broj nenula karakteristi~nih vrednosti. 19 Glava 3 O grafovima ~ija je najmawa karakteristi~na vrednost minimalna U spektralnoj teoriji grafova prou~avawe indeksa grafa je va`na i interesantna tema. Postoji mnogo rezultata u literaturi koji se ti~u in- deksa prostih grafova. Prou~avani su grafovi sa maksimalnim indeksom u odre|enim klasama grafova, zatim grafovi sa minimalnim indeksom, po- redak grafova prema wihovim indeksima, primena indeksa grafa u hemiji, ra~unarstvu, ekonomiji i drugim oblastima nauke, itd. Jednakointeresantna tema jeste izu~avawenajmawekarakteristi~ne vred- nosti grafa. Za bipartitne grafove, neke rezultate u vezi sa indeksom grafa mo`emo preneti i na najmawu karakteristi~nu vrednost. Naime, za svaki bipartitan graf G va`i λ(G) = −ρ(G). Mnogo mawe je, me|utim, poznato u vezi sa najmawom karakteristi~nom vredno{}u ostalih grafova. Znamo da najmawa karakteristi~na vrednost grafa nije pozitivna vrednost. Ona je jednaka nuli jedino kod grafova koji se sastoje samo od izolovanih ~vorova. U suprotnom, kod grafova koji sadr`e bar jednu granu ova vrednost je mawa ili jednaka −1. To se mo`e zakqu~iti na osnovu leme 5 imaju}i na umu da takav graf sadr`i put P2 kao indukovani podgraf. Za kompletne grafove va`i da im je najmawa karakteristi~na vrednost jednaka −1, kao i za nepo- vezane grafove ~ije su sve komponente kompletni grafovi. Kod svih ostalih grafova ova vrednost je mawa ili jednaka −√2 po{to oni sadr`e graf S1,2 kao indukovani podgraf. Grafovi ~ija je najmawa karakteristi~na vred- nost jednaka −2 detaqno su prou~avani u monografiji [14] ~iji su autori Cvetkovi}, Rowlinson i Simi}. U vezi sa najmawom karakteristi~nom vredno{}u grafova najvi{e re- zultata je dobijeno o gorwim i dowim grani ama ove vrednosti. Jo{ 1985. 20 3.1. STRUKTURA EKSTREMALNIH GRAFOVA godine, Constantine [9] dokazuje da za graf G reda n va`i nejednakost − √⌊n 2 ⌋ ⌈n 2 ⌉ 6 λ(G), pri ~emu je jednakost ispuwena ako i samo ako je G kompletan bipartitan graf K⌊n 2 ⌋,⌈n 2 ⌉. Zatim, Powers [35] objavquje jo{ jednu dowu grani u −√m 6 λ(G), gde jem veli~ina grafaG. Kasnije su dobijene jo{ neke grani e za najmawu karakteristi~nu vrednost nekompletnih povezanih grafova reda n, kao na primer (3.1) −n 2 6 λ(G) < −1 2 ( 1 + √ 1 + 4n− 12 n− 1 ) . Pored navedenih rezultata, jedna od va`nijih tema u spektralnoj teoriji grafova jeste izu~avawe grafova sa maksimalnim ili minimalnim indek- som, odnosno maksimalnom ili minimalnom najmawom karakteristi~nom vredno{}u me|u povezanim grafovima odre|ene klase. U ovom poglavqu prikazani su rezultati u vezi sa najmawom karakteri- sti~nom vredno{}u grafova fiksiranog reda i veli~ine. Naime, opisana je struktura grafova ~ija je najmawa karakteristi~na vrednost minimalna u ovoj klasi grafova. Tako|e, odre|eni su jedinstveni grafovi sa minimal- nom najmawom karakteristi~nom vredno{}u u klasi bipartitnih grafova reda n i veli~ine n+ k (n > k + 4) za 0 6 k 6 4. 3.1 Struktura ekstremalnih grafova Neka jeG prost graf reda n i veli~inem i neka jeX jedini~ni sopstveni vektor grafa G koji odgovara najmawoj karakteristi~noj vrednosti λ(G). Ozna~imo sa G′ graf dobijen iz grafa G pomerawem jedne grane u pozi iju gde prethodno nije bilo grane, a sa A(G′) wegovu matri u susedstva. Na osnovu nejednakosti (2.5) dobijamo λ(G′)− λ(G) = min ‖Y ‖=1 Y TA(G′)Y −XTA(G)X 6 XT (A(G′)− A(G))X. (3.2) Lema 12 ([4]). Neka je G′ graf dobijen iz grafa G rota ijom grane rs (oko ~vora r) u pozi iju rt gde prethodno nije bilo grane. Tada je: (i) λ(G′) < λ(G) ako je xr < 0 i xs 6 xt, ili xr = 0 i xs 6= xt, ili xr > 0 i xs > xt; (ii) λ(G′) 6 λ(G) ako je xr = 0 i xs = xt. 21 3.1. STRUKTURA EKSTREMALNIH GRAFOVA Dokaz. Iz rela ije (3.2) dobijamo (3.3) λ(G′)− λ(G) 6 XT (A(G′)− A(G))X = 2xr(xt − xs). U zavisnosti od vrednosti koordinate xr razmotrimo slede}a dva slu~aja. 1◦ xr = 0 U ovom slu~aju je λ(G′) 6 λ(G). [tavi{e, ukoliko je xs 6= xt, onda je λ(G′) < λ(G). U suprotnom, za λ(G′) = λ(G) = λ iz nejednakosti (3.3) vidimo da je XTA(G′)X = XTA(G)X , pa X mora biti karakteristi~ni vektor grafa G′ koji odgovara karakteristi~noj vrednosti λ. Odatle, za graf G′ (kao i za graf G) va`i λxr = ∑ vr∈E(G′) xv. Ovo je nemogu}e kada je xs 6= xt po{to je ~vor r u grafu G susedan sa ~vorom s, a u grafu G′ susedan sa ~vorom t, dok su svi ostali susedi ~vora r isti. 2◦ xr 6= 0 U ovom slu~aju, bez gubitka op{tosti, mo`emo pretpostaviti da je xr > 0 (u suprotnom, zamenimo xr sa −xr). Ako je xt < xs onda iz (3.3) sledi da je λ(G′) < λ(G). Pretpostavimo zato da je xt = xs. Tada je λ(G′) 6 λ(G). Ukoliko je λ(G′) = λ(G) = λ, onda, kao i u slu~aju 1◦, vektor X mora biti karakteristi~ni vektor grafaG′ koji odgovara karakteristi~noj vrednosti λ. Otuda, jednakost λxs = ∑ us∈E(G) xu va`i za grafove G i G ′ . Ovo nije mogu}e po{to su ~vorovi s i r susedni u grafu G, ali ne i u grafu G′. Lema 13 ([4]). Neka je G′ graf dobijen iz grafa G preme{tawem grane ab u pozi iju cd gde prethodno nije bilo grane, pri ~emu je {a, b} ∩ {c, d} = ∅. Tada va`i: (i) λ(G′) < λ(G) ako je xcxd < xaxb; (ii) λ(G′) 6 λ(G) ako je xcxd = xaxb. Jednakost se posti`e jedino kada je xa = xb = xc = xd = 0. Dokaz. Iz rela ije (3.2) dobijamo λ(G′)− λ(G) 6 XT (A(G′)− A(G))X = 2(xcxd − xaxb). Odavde sledi da je λ(G′) < λ(G) kada je xcxd < xaxb. Pretpostavimo sada da je xcxd = xaxb. Tada je, o~igledno, λ(G ′) 6 λ(G). Sli~no kao i u prethodnom dokazu, ako je λ(G′) = λ(G) = λ onda vek- tor X mora biti karakteristi~ni vektor grafa G′ koji odgovara karak- teristi~noj vrednosti λ. Sada vidimo da sve karakteristi~ne jedna~ine λxu = ∑ vu∈E(G) xv va`e i za graf G i za graf G ′ jedino u slu~aju kada je xa = xb = xc = xd = 0. 22 3.1. STRUKTURA EKSTREMALNIH GRAFOVA Prethodne leme podse}aju na lemu 3 koja opisuje promene indeksa grafa nakon rota ija grana u wemu. U lemama 12 (ii) i 13 (ii), me|utim, nije utvr|eno da li se mo`e javiti stroga nejednakost. U nastavku, sa G }e biti ozna~en netrivijalan povezan graf reda n i veli~ine m ~ija je najmawa karakteristi~na vrednost minimalna u ovoj klasi grafova. Graf G se kra}e zove ekstremalni graf i bi}e dokazano da on ima strogo odre|enu strukturu. S tim u vezi, prvo se mora definisati pojam stepenastog grafa. Graf H se naziva stepenasti graf (engl. nested split graph) ako wegovi ~vorovi mogu biti ure|eni tako da jq ∈ E(H) uslovqava ip ∈ E(H), za svako i 6 j i p 6 q. Ovakvom grafu odgovara stepenasta matri a susedstva. Struktura ekstremalnog grafa G je opisana u slede}oj teoremi. Teorema 1 ([4]). Neka je G povezan graf ~ija je najmawa karakteristi~na vrednost λ(G) minimalna me|u povezanim grafovima reda n i veli~ine m( m < ( n 2 )) . Tada je G (i) bipartitan graf, ili (ii) kompletan proizvod dva stepenasta grafa (od kojih nisu oba potpuno nepovezana). Pokazuje se da je struktura grafaG uslovqena znakom koordinata karak- teristi~nog vektora koji odgovara karakteristi~noj vrednosti λ(G). Dokaz ove teoreme zasnovan je na lemama koje su date u nastavku. Neka je X = (x1, x2, . . . , xn) T sopstveni vektor koji odgovara sopstve- noj vrednosti λ(G). Defini{imo podelu skupa ~vorova V (G) indukovanu podelom koordinata vektora X na negativne, nula i pozitivne, na slede}i na~in: V −(X) = {u ∈ V (G) | xu < 0} − skup negativnih ~vorova, V 0(X) = {u ∈ V (G) | xu = 0} − skup nula ~vorova, V +(X) = {u ∈ V (G) | xu > 0} − skup pozitivnih ~vorova. Lema 14 ([4]). Ako je V 0(X) 6= ∅ onda je d(u) = n− 1 za svaki ~vor u ∈ V 0(X). Dokaz. Pretpostavimo suprotno, tj. da postoji ~vor r iz skupa V 0(X) takav da je d(r) < n − 1. Neka je Sr = {s ∈ V (G) | sr ∈ E(G)} skup svih wegovih suseda u grafu G i Tr skup svih ~vorova koji nisu susedni sa r u grafu G, tj. Tr = {t ∈ V (G) | tr 6∈ E(G), t 6= r}. Primetimo da je Sr 6= ∅, po{to je graf G povezan i netrivijalan. Tako|e, Tr 6= ∅. Neka su s ∈ Sr i t ∈ Tr dva proizvoqna ~vora. Rotirajmo sada granu rs u grafu G u pozi iju rt i tako dobijeni graf ozna~imo sa G′. Pretpostavimo prvo, da je graf G′ povezan za svaki izbor ~vorova s i t. Ako je xs 6= xt, za neko s i t, onda primenom leme 12 (i) dobijamo da je λ(G′) < λ(G), {to je u kontradik iji sa izborom grafa G. Sledi da je xs = xt za svaki izbor ~vorova s i t. Stoga, xv = c za proizvoqan ~vor 23 3.1. STRUKTURA EKSTREMALNIH GRAFOVA v 6= r grafaG, gde je c realna konstanta. Sada je λ(G)xr = ∑ v∈Sr xv = d(r)c. Po{to je d(r) 6= 0 i xr = 0, zakqu~ujemo da je c = 0 i otuda X = 0, {to je nemogu}e. Sada pretpostavimo da je za neki izbor ~vorova s i t graf G′ nepovezan. Tada grana rsmorabitimost u grafuG, a ~vorovi si t se nalaze u razli~itim komponentama Gs i Gt grafa G ′ , respektivno. Pretpostavimo da postoji ~vor t′ ∈ Gs (t′ 6= s). Tada t′ ∈ Tr, jer u suprotnom slu~aju bi u grafu G postojao put od ~vora r do ~vora s koji izbegava most rs. Ako je xs 6= x′t, tada dobijamo kontradik iju primenom gorwih argumenata na ~vor t′ umesto na ~vor t. Primetimo da je odgovaraju}i graf G′ u ovom slu~aju povezan. Zato neka je xu = xs za svaki ~vor u ∈ V (Gs). Pomo}u (λ,X)karakteristi~nih jedna~ina ~vora s, primewenih u grafu G, dobijamo λ(G)xs = (d(s) − 1)xs, odakle je xs = 0. Zbog toga Gt mora da sadr`i ~vor u takav da je xu 6= 0. Ozna~imo sada saG′′ graf dobijen iz grafaG rota ijom grane sr u pozi iju su. Graf G′′ je povezan i primenom leme 12 (i) dolazimo do kontradik ije λ(G′′) < λ(G). Ako pomenuti ~vor t′ ne postoji, tada je ~vor s stepena 1 i na osnovu karakteristi~nih jedna~ina za ~vor s zakqu~ujemo da je xs = xr = 0. Prema tome, graf Gt sadr`i ~vor u za koji je xu 6= 0. I u ovom slu~aju, sa G′′ ozna~imo graf dobijen iz grafa G rota ijom grane sr u pozi iju su. Graf G′′ je povezan, pa na osnovu leme 12 (i) dobijamo λ(G′′) < λ(G), {to je nemogu}e. Lema 15 ([4]). Neka je G povezan graf ~ija je najmawa karakteristi~na vred- nost minimalna me|u povezanim grafovima reda n i veli~ine m < ( n 2 ) . Tada je λ(G) prosta karakteristi~na vrednost grafa G. Dokaz. Pretpostavimoda karakteristi~na vrednostλ(G) ima vi{estrukost bar 2. Tada za svaki ~vor u ∈ V (G) postoji karakteristi~ni vektorX ~ija je u-ta koordinata jednaka nuli. Dakle, u ∈ V 0(X) i V 0(X) 6= ∅. Po{to G nije kompletan graf, mo`emo izabrati ~vor u tako da je d(u) < n− 1, {to je u kontradik iji sa lemom 14. Kao direktna posledi a prethodne leme izvodi se zakqu~ak da akoG nije kompletan graf onda je parti ija skupa V (G), koja je indukovana znakom ko- ordinata proizvoqnog karakteristi~nog vektora koji odgovara karakteri- sti~noj vrednostiλ(G), jedinstvena (primetimoda se samo uloga pozitivnih i negativnih ~vorova mo`e promeniti). Shodno tome, pretpostavimo da je m < ( n 2 ) i V (G) = V + ∪ V 0 ∪ V −. Ozna~imo sa 〈U〉 podgraf grafaG indukovan ~vorovima skupaU ⊆ V (G), a sa G∇H kompletan proizvod grafova G i H . Kori{}ewem leme 14 mo`e se opisati struktura grafa G. Ako je V 0 6= ∅, onda je K = 〈V 0〉 kompletan graf i G = K∇H , gde je H = 〈V + ∪ V −〉. Fokusirajmo se, u nastavku, na grafH . Neka jeH− = 〈V −〉 iH+ = 〈V +〉. PodgrafoviH− iH+ grafaG postoje, po{to su sopstveni prostori za λ(G) 24 3.1. STRUKTURA EKSTREMALNIH GRAFOVA i ρ(G) me|usobno ortogonalni, a sopstveni prostor koji odgovara indeksu ρ(G) je razapet pozitivnim karakteristi~nimvektorom. SkupV 0 mo`e biti i prazan. Lema 16 ([4]). Grafovi H+ i H− su stepenasti grafovi. Dokaz. Neka je V + = {1, 2, . . . , k} pri ~emu va`i x1 6 x2 6 · · · 6 xk. Treba dokazati da ako graf G sadr`i granu jq, onda on sadr`i i granu ip za svako 1 6 i 6 j 6 k i 1 6 p 6 q 6 k. Pretpostavimo suprotno, tj. neka jq ∈ E(G) i ip /∈ E(G) za 1 6 i 6 j 6 k i 1 6 p 6 q 6 k. U grafu G premestimo granu jq u pozi iju ip i novi graf ozna~imo sa G′. Kako je najmawa karakteristi~na vrednost grafa G minimalna u posmatranoj klasi, onda va`e slede}e nejednakosti 0 6 λ(G′)− λ(G) 6 2(xixp − xjxq) = 2(xi − xj)xp + 2(xp − xq)xj 6 0. Odavde zakqu~ujemo da je xi = xj i xp = xq, kao i da je X karakteristi~ni vektor koji odgovara karakteristi~noj vrednosti λ(G′) = λ(G). Ako posta- vimo karakteristi~ne jedna~ine za ~vor q u grafovima G i G′, o~igledno se dolazi do kontradik ije, po{to je ~vor q izgubio jednog suseda u grafu G′. Dakle, H+ je stepenasti graf. Analogno se dokazuje i da je graf H− stepenasti graf. Lema 17 ([4]). Ako skup V + ili V − indukuje granu ij, onda grafG sadr`i granu pq za sve p ∈ V − i q ∈ V +. Dokaz. Pretpostavimo da neki od skupova V + ili V − indukuje granu ij i da ne va`i tvr|ewe leme. Tada granu ij mo`emo da premestimo u pozi iju pq (p ∈ V −, q ∈ V +). Kako je xixj > 0, a xpxq < 0, primenom leme 13 (i) dolazimo do kontradik ije. Na osnovu leme 17 dolazi se do slede}eg zakqu~ka. Lema 18 ([4]). Ako bar jedan od grafova H+ ili H− nije potpuno nepovezan, onda je H = H+∇H−. U suprotnom, H je bipartitan graf (ne obavezno kompletan bipartitan). U vezi sa strukturom grafa G va`e i slede}i rezultati. Lema 19 ([4]). Ako je V 0 6= ∅, onda je H = H+∇H−. Dokaz. Pretpostavimo da jeH 6= H+∇H−. Izaberimo ~etiri ~vora u grafu G na slede}i na~in: a ∈ V 0, b ∈ V + ∪ V −, c ∈ V + i d ∈ V −, pri ~emu su ~vorovi c i d nesusedni. Na osnovu leme 14, ~vorovi a i b su susedni u grafu G i grana ab nije most. [tavi{e, va`i da je xaxb > xcxd. Primetimo jo{ da ~vor b ne mo`e biti stepena 1, jer se u tom slu~aju dobija da b ∈ V 0. Ako sada granu ab zamenimo granom cd, dobi}emo povezani graf G′. Primenom leme 13 vidimo da je λ(G′) < λ(G), {to dovodi do kontradik ije. Dakle, svaki ~vor grafaH+ susedan je sa svakim ~vorom grafa H−. 25 3.1. STRUKTURA EKSTREMALNIH GRAFOVA Iz lema 14 i 19 sledi da ako je V 0 6= ∅, onda posmatrani graf G ima oblikK∇L, gde suK i L stepenasti grafovi, ~vorovi izK su nenegativni, a ~vorovi iz L su nepozitivni. Dakle, VK = V + ∪ X i VL = V − ∪ Y , gde je X ∪ Y proizvoqna parti ija skupa V 0. Ovo zapa`awe u kombina iji sa lemom 18 daje dokaz teoreme 1. Teorema 1 je jedna od kqu~nih teorema u izu~avawu minimalne najmawe karakteristi~ne vrednosti nekih klasa grafova. Ona nam daje informa ije o strukturi posmatranog grafa G, gde je G povezani graf. Ako, me|utim, u obzir uzmemo i nepovezane grafove sa n ~vorova im grana, i daqe }emo mo}i da iskoristimo teoremu 1. Naime, pokazuje se da ekstremalni graf sadr`i najvi{e jednu netrivijalnu komponentu povezanosti u kojoj se upravo i po- sti`e minimalna najmawa karakteristi~na vrednost. Na ovu komponentu mo`emo primeniti teoremu 1 i ostale rezultate koji se odnose na pove- zane grafove. Do ovog zakqu~ka se dolazi na osnovu postupka opisanog u nastavku. Neka je G proizvoqni graf reda n i veli~ine m ~ije su netrivijalne komponente povezanosti G1, G2, . . . , Gk (k > 1). Na osnovu rela ije (2.2) vidimo da je najmawa karakteristi~na vrednost grafa G u stvari najmawa karakteristi~na vrednost neke od komponentiGi (i = 1, . . . , k). Kako su gra- fovi Gi (i = 1, . . . , k) podgrafovi grafa G, na osnovu leme 5, za proizvoqne dve razli~ite komponente Gi i Gj (i, j ∈ {1, . . . , k} i k > 2) va`i (3.4) λ(Gi ·Gj) 6 min{λ(Gi), λ(Gj)} = λ(Gi ∪Gj). Ako sada Gi ∪ Gj u grafu G zamenimo sa (Gi · Gj) ∪ K1 dobijamo graf G′, koji ostaje u istoj klasi, a za koji je λ(G′) 6 λ(G). Ako isti postupak primenimo na graf G′, a zatim postupak ponavqamo sve dok ne dobijemo graf sa samo jednom netrivijalnom komponentom, na kraju }emo dobiti graf G∗ sa osobinomλ(G∗) 6 λ(G). Prema tome, potraga za ekstremalnim grafom se mo`e suziti na povezane grafove, {to mo`emo napisati pre iznije u vidu tvr|ewa koje sledi. Neka je H(n,m) skup svih grafova reda n i veli~ine m. Defini{imo sada veli~ine f(n,m) = min{λ(G) | G ∈ H(n,m)}, i g(n,m) = min{λ(G) | G ∈ H(n,m) i G je povezan}. Lema 20 ([4]). f(n,m) = min{ g(k,m) | k 6 n i skup H(k,m) sadr`i bar jedan povezan graf}. Dakle, teorema 1 se u kombina iji sa lemom 20 mo`e primeniti i na nepovezane grafove. Ova teorema dosta pojednostavquje problem nala`ewa ekstremalnog grafa u klasi grafova fiksiranog reda i veli~ine. Ona nas dovodi do dve potklase: klase bipartitnih grafova i klase grafova koji 26 3.1. STRUKTURA EKSTREMALNIH GRAFOVA predstavqaju kompletan proizvod dva stepenasta grafa, sa kojima je daqe lak{e raditi. U tome se, upravo, i ogleda va`nost ove teoreme. Do sli~nog rezultata je do{la i A. Sawikovska [37] u svojoj doktorskoj diserta iji, izu~avaju}i grafove reda n i veli~inem, ne obavezno povezane. Teorema 2 ([37]). Neka je G graf ~ija je najmawa karakteristi~na vrednost λ(G) minimalna me|u grafovima reda n i veli~ine m. Tada je G (i) bipartitan graf kod koga neki ~vorovi mogu biti izolovani, ili (ii) kompletan proizvod dva grafa. Dokaz. Neka je G graf ~ija je najmawa karakteristi~na vrednost λ(G) mi- nimalna me|u grafovima reda n i veli~inem i neka jeX = (x1, x2, . . . , xn) T karakteristi~ni vektor koji odgovara najmawoj sopstvenoj vrednosti λ(G). Bez gubitka op{tosti, pretpostavimo da je x1 6 x2 6 · · · 6 xn. Kako je A(G) > 0 a λ(G) < 0, da bi va`ilo A(G)X = λ(G)X , karakteri- sti~ni vektorX mora imati i negativne i pozitivne koordinate. Zbog toga je x1 < 0, a xn > 0. Neka je p prirodan broj takav da su sve koordinate xi < 0 za i 6 p, a sve koordinate xi > 0 za i > p. To zna~i da sopstveni vektor X mo`emo predstaviti u obliku X = ( x(1) x(2) ) , gde je x(1) vektor dimenzije p ~ije su sve koordinate negativne, a x(2) vektor dimenzije n− p ~ije su sve koordinate nenegativne. Sli~no, matri u susedstva A(G) mo`emo napisati kao A(G) = ( A11 A12 AT12 A22 ) , gde jeA11 kvadratna matri a dimenzije p, aA22 kvadratnamatri a dimenzije n− p. Razmotrimo sada proizvodXTA(G)X . Naime, (3.5) XTA(G)X = x(1)TA11x (1) + x(2)TA22x (2) + 2x(1)TA12x (2). Na osnovu (2.5), vidimo da je λ(G) = min ‖Y ‖=1 Y TA(G)Y = XTA(G)X . Kako su svi sabir i u prva dva izraza proizvoda (3.5) nenegativni, matri eA11 iA22 moraju biti 0-matri e ili svi elementi matri e A12 moraju biti jedini e. Zaista, ukoliko matri a A12 (a time i A T 12) sadr`i nule, onda na wihovo mesto mo`emo premestiti simetri~no postavqene jedini e iz A11 ili A22. Na taj na~in dobijamo novu matri u A′ = A(G′) koja predstavqa matri u susedstva odgovaraju}eg grafa G′, pri ~emu je graf G′ tako|e graf reda n i 27 3.2. STRUKTURAEKSTREMALNIH BIPARTITNIH GRAFOVA veli~ine m. Sada, proizvod XTA(G′)X ima mawu vrednost od proizvoda (3.5). Dakle λ(G′) < λ(G), {to je u kontradik iji sa izborom grafa G. Ako su matri eA11 iA22 0-matri e, grafG je bipartitan, pri ~emu neki wegovi ~vorovi mogu biti izolovani. Ako su, pak, svi elementi matri e A12 jedini e onda grafG predstavqa kompletan proizvod dva grafa, ~ija je struktura odre|ena matri ama A11 i A22. Lema 21 ([37]). Neka je G graf ~ija je najmawa karakteristi~na vrednost λ(G) minimalna me|u grafovima reda n i veli~ine m, za m 6 n 2 4 , m = fg (f, g ∈ N), f + g 6 n. Tada se graf G sastoji od kompletnog bipartitnog grafa i (mogu}e) nekih izolovanih ~orova. Vidimo da su u teoremi 1 i teoremi 2 dobijeni sli~ni rezultati. Zna~aj teoreme 2 se ogleda u tome {to ona obuhvata grafove reda n i veli~ine m, bez ograni~ewa za broj grana i povezanost grafa. U slu~aju (ii), me|utim, ne dobijamo nikakvu informa iju o strukturi grafova H1 i H2 koji ~ine kompletan proizvodG = H1∇H2. Sa druge strane, teorema 1 daje pre iznije informa ije o strukturi tra`enog grafa G, mada je broj grana ograni~en( m < ( n 2 )) i tek u kombina iji sa lemom 20 se mo`e primeniti na nepovezane grafove. 3.2 Struktura ekstremalnih bipartitnih grafova Neka jeG povezan bipartitan graf, koji sadr`i rne i bele ~vorove. Sa U ozna~imo skup rnih ~vorova, a sa V skup belih ~vorova grafa G. Graf G nazivamo lan~anim grafom (engl. double nested graph ili chain graph) ukoliko postoje parti ije U = U1 ∪˙U2 ∪˙ · · · ∪˙Uh i V = V1 ∪˙V2 ∪˙ · · · ∪˙Vh, takve da je skup suseda za svaki ~vor iz Ui skup V1 ∪˙V2 ∪˙ · · · ∪˙Vh−i+1 (i = 1, 2, . . . , h). Ozna~imo sa G = D(m1, m2, . . . , mh; n1, n2, . . . , nh) lan~ani graf kod koga je |Ui| = mi (i = 1, 2, . . . , h) i |Vi| = ni (i = 1, 2, . . . , h). Parametar h jo{ nazivamo i visinom lan~anog grafa G. O~igledno, za lan~ani graf G va`e jednakosti n(G) = m1 +m2 + · · ·+mh + n1 + n2 + · · ·+ nh,(3.6) m(G) = m1(n1 + · · ·+ nh) +m2(n1 + · · ·+ nh−1) + · · ·+mhn1.(3.7) Spe ijalno, ako je visina h = 1, tada jeG kompletan bipartitni grafKm1,n1 i wegov karakteristi~ni polinom je (3.8) φ(G, λ) = λn−2(λ2 −m(G)). 28 3.2. STRUKTURAEKSTREMALNIH BIPARTITNIH GRAFOVA Za h = 2, graf G = D(m1, m2;n1, n2) je prikazan na sli i 3.1, a wegov ka- noni~ki graf jeG′ = D(1, 1; 1, 1). Na osnovu leme 11 va`i η(G) = η(G′) = 4, pa je η(G) = n−4. Neka jeX = (x1, . . . , xm1 , y1, . . . , yn1, z1, . . . , zm2 , t1, . . . , tn2) karakteristi~ni vektor koji odgovara nenula karakteristi~noj vrednosti grafa G. Koordinate ovog vektora odgovaraju redom ~vorovima v1, . . . , vm1 , u1, . . . , un1, vm1+1, . . . , vm1+m2 , un1+1, . . . , un1+n2 . PSfrag repla ements m1 m2 n1 n2 Slika 3.1. Lan~ani graf visine 1 Koriste}i (λ,X)karakteristi~ne jedna~ine (2.4) grafa G, zakqu~ujemo da je x1 = · · · = xm1 , y1 = · · · = yn1 , z1 = · · · = zm2 i t1 = · · · = tn2 i koordinate x1, y1, z1 i t1 zadovoqavaju jednakosti λx1 = n1y1 + n2t1, λy1 = m1x1 +m2z1, λz1 = n1y1, λt1 = m1x1. Dobijeni homogeni sistem jedna~ina ima netrivijalna re{ewa (po x1, y1, z1 i t1) ako i samo ako je wegova determinanta jednaka nuli, odnosno (3.9) ∣∣∣∣∣∣∣∣ λ −n1 0 −n2 −m1 λ −m2 0 0 −n1 λ 0 −m1 0 0 λ ∣∣∣∣∣∣∣∣ = 0. Dakle, nenula sopstvene vrednosti grafa G zadovoqavaju jedna~inu (3.9), a razvojem posledwe determinante dobijamo karakteristi~ni polinom (3.10) φ(G, λ) = λn−4(λ4 −m(G)λ2 +m1m2n1n2). Za h = 3 graf G = D(m1, m2, m3;n1, n2, n3) je prikazan na sli i 3.2. Ko- riste}i postupak koji je sli~an postupku u slu~aju h = 2, dobija se da je karakteristi~ni polinom grafa G φ(G, λ) = λn−6(λ6 −m(G)λ4 + (m2m3n1n2 +m1m2(n1 + n2)n3 +m1m3n1(n2 + n3))λ 2 −m1m2m3n1n2n3).(3.11) Pokazuje se da lan~ani grafovi imaju istu ulogu u skupu bipartitnih grafova (u odnosu na indeks), kao stepenasti grafovi u skupu nebipartitnih grafova (u odnosu na najmawu karakteristi~nu vrednost). 29 3.2. STRUKTURAEKSTREMALNIH BIPARTITNIH GRAFOVA PSfrag repla ements m1 m2 n1 n2 n3m3 Slika 3.2. Lan~ani graf visine 2 Teorema 3 ([5]). Ako je G graf za koji je λ(G) minimalno (odnosno ρ(G) mak- simalno) me|u svim povezanim bipartitnim grafovima reda n i veli~ine m, onda je G lan~ani graf. Dokaz prethodne teoreme je zasnovan na lemi 3 i lemama koje navodimo u nastavku. Poznato je da za svaki bipartitni graf G va`i da je λ(G) = −ρ(G). Otuda, problem minimalne najmawe karakteristi~ne vrednosti ekvivalen- tan je sa problemom maksimalnog indeksa u ovoj klasi grafova, tako da }emo se u nastavku fokusirati na indekse odgovaraju}ih grafova. Slede}a lema je veomakorisna kada se susretnemo samostomu grafu~iji je indeks po pretpostav i maksimalan. Neka su P = Pu iQ = Qv dva korenska grafa sa korenima u i v, a G graf dobijen iz unije P ∪˙Q dodavawem grane uv. Neka je G′ graf formiran od koales en ije grafova Pu i Qv dodavawem slobodne grane na ~vor dobijen poistove}ivawem ~vorova u i v. Lema 22 ([5]). U skladu sa navedenim oznakama, ako su P i Q netrivijalni povezani grafovi, onda va`i da je ρ(G′) > ρ(G). Dokaz. Neka je X = (x1, x2, . . . , xn) T Peronov vektor grafa G. Bez gubitka op{tostimo`emo pretpostavitida je xu 6 xv. Neka jeNP (u) = {w1, . . . , wk} skup svih ~vorova susednih sa ~vorom u u grafu P . Kako je P netrivi- jalan graf o~igledno je NP (u) 6= ∅. Graf G′ mo`emo dobiti iz grafa G preme{tawem grana uwi (i = 1, . . . , k) u pozi ije vwi. Na osnovu leme 3 sledi da je ρ(G) < ρ(G′). U nastavku pretpostavimo da graf G ima maksimalni indeks u skupu povezanih bipartitnih grafova fiksiranog reda i veli~ine. Lema 23 ([5]). Neka graf G zadovoqava navedene pretpostavke i neka je X = (x1, x2, . . . , xn) T Peronov vektor grafaG. Ako su v i w ~vorovi iste boje takvi da je xv > xw, onda je d(v) > d(w). Dokaz. Pretpostavimo suprotno. Neka je xv > xw i d(v) < d(w). Tada va`i da je 1 < d(w), odnosno postoji ~vor u ∈ U koji je susedan sa w a nije susedan sa v. Ako u grafu G granu uw rotiramo u polo`aj uv, na osnovu leme 3 dobijamo graf G′ za koji je ρ(G) < ρ(G′). Ako je grana uw most onda iz 30 3.2. STRUKTURAEKSTREMALNIH BIPARTITNIH GRAFOVA leme 22 vidimo da je d(u) = 1. Dakle, graf G′ je u svakom slu~aju povezan. Dolazimo do kontradik ije sa pretpostavkom da je ρ(G) maksimalno. Neka je u posmatranom bipartitnom grafuG skup belih ~vorova ozna~en sa U = {u1, u2, . . . , up} a skup rnih ~vorova sa V = {v1, v2, . . . , vq}, gde je xu1 > xu2 > · · · > xup i xv1 > xv2 > · · · > xvq . Na osnovu prethodne leme mo`e se zakqu~iti da ovakvom ure|ewu koordinata vektoraX odgovara isto ure|ewe stepena ~vorova u obe klase. Slede}a lema daje neke posledi e prethodnih lema. Lema 24 ([5]). Neka graf G zadovoqava navedene pretpostavke ukqu~uju}i i one koje se odnose na ure|ewe ~vorova grafa. Tada va`i: (i) ~vorovi u1 i v1 su susedni; (ii) ~vor u1 je susedan sa svim ~vorovima iz klase V i ~vor v1 je susedan sa svim ~vorovima iz klase U; (iii) ako je ~vor u susedan sa ~vorom vk, onda je u susedan i sa svim ~vorovima vj za j < k. Sli~no, ako je ~vor v susedan sa ~vorom uk, onda je v susedan i sa svim ~vorovima uj za j < k. Dokaz. Razmotrimo prvo mostove u grafu G. Na osnovu leme 22 svi mostovi u grafu moraju biti vise}e grane (ina~e bismo do{li do kontradik ije sa maksimalno{}u indeksa ρ(G)). Pomo}u leme 3 zakqu~ujemo da su svi vise}i ~vorovi susedni sa ~vorom w za koji va`i da je xw maksimalno u karakteristi~nom vektoru X . Bez umawewa op{tosti, pretpostavimo da je xu1 > xv1 i w = u1. Sledi da rezultat va`i ako je G stablo, tj. G je zvezda. Pretpostavimo daqe da G nije stablo. (i) Da bismo dokazali ovo tvr|ewe pretpostavimo suprotno, tj. da ~vorovi u1 i v1 nisu susedni. Tada je v1 susedan sa nekim drugim ~vorom u ∈ U i uv1 nije most. Sada mo`emo rotirati granu uv1 u polo`aj u1v1 i dobiti povezan bipartitan graf G′. Na osnovu leme 3 dobijamo da je ρ(G) < ρ(G′), {to dovodi do kontradik ije. (ii) Pretpostavimo da je u ∈ U ~vor koji nije susedan sa v1. Na osnovu (i), zakqu~ujemo da je u 6= u1, uv1 nije most i ~vor u je susedan sa nekim ~vorom v ∈ V (v 6= v1). Granu uv mo`emo rotirati u polo`aj uv1 i dobiti kontradik iju kao u slu~aju (i). Sli~no, pretpostavimo da je v ∈ V ~vor koji nije susedan sa u1. Ponovo, na osnovu (i) va`i da je v 6= v1, grana vu1 nije most i ~vor v je susedan sa nekim ~vorom u ∈ U . Rota ija grane oko ~vora v dovodi do kontradik ije. (iii) Pretpostavimo da je ~vor u susedan sa nekim ~vorom vk ∈ V i isto- vremeno nije susedan sa vj za neko j < k. Iz (ii) sledi da je u 6= u1 i grana uvk nije most. Prema tome, granu uvk mo`emo rotirati u polo`aj uvj , ~ime 31 3.2. STRUKTURAEKSTREMALNIH BIPARTITNIH GRAFOVA dolazimo do kontradik ije. Sli~no, pretpostavimo da je ~vor v susedan sa nekim ~vorom uk ∈ U i istovremeno nije susedan sa uj , za neko j < k. U ovom slu~aju vuk nije most, po{to je k > 1. Rota ija grane vuk u polo`aj vuj dovodi do kontradik ije. Dokaz teoreme 3 sada sledi direktno iz leme 24 i defini ije lan~anog grafa. U nastavku, pa`wa }e biti posve}ena povezanim bipartitnim grafovima sa n ~vorova i n + k grana (k > 0). Primetimo da su za k = −1 u pitawu stabla, pa je zvezda S1,n−1 (K1,n−1) ekstremalni graf u ovoj klasi grafova (videti [15]). Imaju}i na umu teoremu 3, bi}e odre|en jedinstveni graf sa minimalnom najmawom karakteristi~nom vredno{}u me|u svim povezanim bipartitnim grafovima reda n i veli~ine n+k, gde je 0 6 k 6 4 i n > k+4. Da bismo formulisali i dokazali glavnu teoremu ovog poglavqa, neop- hodno je dokazati slede}u lemu. Lema 25. Neka su n1, n2, m2, m3 i k prirodni brojevi i neka je n1 > 2. Tada va`i implika ija (n1 − 1)(m2 +m3) + n2m2 6 k + 1 ⇒ n1 + n2 +m2 +m3 6 k + 3. Dokaz. Koriste}i zakon kontrapozi ije dovoqno je dokazati implika iju n1 + n2 +m2 +m3 > k + 3 ⇒ (n1 − 1)(m2 +m3) + n2m2 > k + 1. Primetimo da je za svaka dva prirodna broja a, b > 1 ispuwena nejednakost (3.12) ab > a + b− 1. Pretpostavimo da je n1+n2+m2+m3 > k+3. Koriste}i nejednakost (3.12) dobijamo da je (n1 − 1)(m2 +m3) + n2m2 > n1 − 1 +m2 +m3 − 1 + n2 +m2 − 1 > n1 + n2 +m2 +m3 − 2 > k + 1, ~ime je dokaz leme kompletiran. Teorema 4. Neka jeG graf koji ima maksimalni indeks ρ(G) me|u svim poveza- nim bipartitnim grafovima reda n i veli~ine n+ k (k > 0, n > k+4). Graf G je lan~ani graf D(m1, m2, . . . , mh;n1, n2, . . . , nh) sa slede}im osobinama: (i) h > 1; (ii) ta~no jedan od parametara m1 i n1 je jednak 1; (iii) ako za graf G va`i da je h = 2, tada je G = D(1, 1; k + 2, n− (k + 4)); (iv) h 6= 3. Dokaz. Sa G ozna~imo graf koji ima maksimalni indeks ρ(G) me|u svim povezanim bipartitnim grafovima redan i veli~inen+k (k > 0, n > k+4). Na osnovu teoreme 3 zakqu~ujemo da je G lan~ani graf D(m1, m2, . . . , mh; n1, n2, . . . , nh) (h > 1). 32 3.2. STRUKTURAEKSTREMALNIH BIPARTITNIH GRAFOVA (i) Da bismo dokazali ovu osobinu pretpostavimo suprotno, tj. da je h = 1. Tada je G kompletan bipartitan grafKt,n−t (2 6 t 6 ⌊n2 ⌋), pri ~emu je m = t(n− t) > 2(n− 2). Odatle dobijamo k = m− n > n− 4 > k, {to je o~igledno kontradik ija. (ii) Neka je G = D(m1, m2, . . . , mh;n1, n2, . . . , nh) (h > 2), m1 > 2 i n1 > 2. Na osnovu defini ije lan~anog grafa zakqu~ujemo da broju grana najvi{e doprinose prvih m1 belih i n1 rnih ~vorova. Zato, koriste}i jednakost (3.7), vidimo da su zadovoqene slede}e rela ije m(G) > m(D(2, m1 +m2 − 2, . . . , mh;n1, . . . , nh)) i m(G) > m(D(m1, . . . , mh; 2, n1 + n2 − 2, . . . , nh)). Ako je h = 2, tada iz prethodnih nejednakosti i (3.7) imamo m(G) > m(D(2, m1 +m2 − 2; 2, n1 + n2 − 2)) = 2n− 4. Tako|e, koriste}i iste nejednakosti i (3.7), za h > 3 dobijamo m(G) > m(D(2, m1 +m2 − 2, . . . , mh; 2, n1 + n2 − 2, . . . , nh)) = 2(n1 + n2 + · · ·+ nh) + (m1 +m2 − 2)(n1 + n2 + · · ·+ nh−1) +m3(n1 + n2 + · · ·+ nh−2) + · · ·+mhn1 = (m1 +m2)(n1 + n2 + · · ·+ nh−1) +m3(n1 + n2 + · · ·+ nh−2) +m4(n1 + · · ·+ nh−3) + · · ·+mhn1 + 2nh > (m1 +m2)(n1 + n2 + · · ·+ nh−1) +m3 +m4 + · · ·+mh + 2nh = 2n+ (m1 +m2)(n1 + · · ·+ nh−1)− 2(m1 +m2 + n1 + · · ·+ nh−1). Po{to jem1 +m2 > 3 i n1 + · · ·+ nh−1 > 3 sledi da je (m1 +m2)(n1 + · · ·+ nh−1)− 2(m1 +m2 + n1 + · · ·+ nh−1) > −3. Odatle jem(G) > 2n− 4. U oba slu~aja dobijamo kontradik iju k = m− n > n− 4 > k, {to zna~i da je najmawe jedan od parametaram1 i n1 jednak 1. Pretpostavimo sada da jem1 = 1 i n1 = 1, odnosnoG = D(1, m2, . . . , mh; 1, n2, . . . , nh). Ako je h = 2, tada je graf G stablo, {to je nemogu}e. Za h > 3, na osnovu leme 3 imamo ρ(G) < ρ(D(m2 + 1, m3, . . . , mh + nh; 1, n2, . . . , nh−1)) ili ρ(G) < ρ(D(1, m2, . . . , mh−1;n2 + 1, n3, . . . , mh + nh)), {to je u kontradik iji sa ~iweni om da ρ(G) mora biti maksimalno. Na ovaj na~in smo dokazali da je ta~no jedan od parametaram1 i n1 jednak 1. 33 3.2. STRUKTURAEKSTREMALNIH BIPARTITNIH GRAFOVA (iii) Neka je G = D(m1, m2;n1, n2). Koriste}i osobinu (ii) pretpostavimo da je m1 = 1 i n1 > 1. Dakle, G = D(1, m2;n1, n2). Tada na osnovu (3.6) i (3.7) imamo n = m2 + n1 + n2 + 1 im = n1 + n2 + n1m2. Kako je m = n + k, va`i slede}a jednakost (3.13) m2(n1 − 1) = k + 1. Ako je k = 0, onda jem2 = 1 i n1 = 2 i grafD(1, 1; 2, n−4) je jedini lan~ani graf za h = 2. Pretpostavimo daqe da je k > 1. Ako je m2 = 1 tada iz (3.13) dobijamo n1 = k + 2 i n2 = n − (k + 4). Sli~no, ako je m2 = k + 1 tada je n1 = 2 i n2 = n− (k+4). Neka jeD1 = D(1, 1; k+2, n− (k+4)) iDk+1 = D(1, k+1; 2, n − (k + 4)) (slika 3.3). Uporedimo karakteristi~ne polinome ova dva grafa. Iz (3.10) dobijamo φ(D1, λ) = λ n−4(λ4 −m(D1)λ2 + (k + 2)(n− (k + 4))), φ(Dk+1, λ) = λ n−4(λ4 −m(Dk+1)λ2 + 2(k + 1)(n− (k + 4))). PSfrag repla ements n− (k + 4) n− (k + 4) D1 Dk+1 k + 2 k + 1 vv Slika 3.3. Lan~ani grafoviD1 i Dk+1 Dakle, za λ > 0 va`i φ(D1, λ) − φ(Dk+1, λ) = −k(n − k − 4)λn−4 < 0, pa zakqu~ujemo da je ρ(Dk+1) < ρ(D1). Ako je k+1 prost broj, tada su grafoviD1 iDk+1 jedini lan~ani grafovi i dokaz je kompletiran. Pretpostavimo daqe da je k + 1 slo`en broj. Neka je m2 wegov delila takav da je 1 < m2 < k + 1. Tada je 2 < n1 < k + 2. Tako|e, vidimo da va`i m2 + n1 < k + 3⇔ m2 + n1 < m2(n1 − 1) + 2 ⇔ 1 2 m2(3− n1) + 1 2 (n1 − 1)(2−m2) < 1.(3.14) Po{to je u (3.14) posledwa nejednakost o~igledno ispuwena, dobijamo da je m2 + n1 < k + 3. Odatle je n2 = n − 1 −m2 − n1 > n − k − 4. Neka je sada Dm2 = D(1, m2;n1, n− (m2 + n1 + 1)). Tada je na osnovu (3.10) φ(Dm2 , λ) = λ n−4(λ4 −m(Dm2)λ2 +m2n1(n− (m2 + n1 + 1))). 34 3.2. STRUKTURAEKSTREMALNIH BIPARTITNIH GRAFOVA Kako za λ > 0 va`i φ(D1, λ)− φ(Dm2 , λ) = λn−4((k + 2)(n− k − 4)−m2n1n2) < λn−4((k + 2)(n− k − 4)−m2n1(n− k − 4)) = −(m2 − 1)(n− k − 4)λn−4 < 0, to je ρ(D1) > ρ(Dm2). Ovim je dokaz osobine (iii) kompletiran. (iv) Ako je G lan~ani graf visine h = 3, tada je na osnovu osobine (ii) G = D(1, m2, m3;n1, n2, n3) gde je n1 > 2. Iz jednakosti (3.6) i (3.7) sledi da parametrim2, m3, n1 i n2 zadovoqavaju jednakost (3.15) (n1 − 1)(m2 +m3) + n2m2 = k + 1. Koriste}i lemu 25 zakqu~ujemo da n1 + n2 + m2 + m3 6 k + 3. Otuda, n3 = n− (n1 + n2 +m2 +m3 + 1) > n− (k + 4).PSfrag repla ements v m2 m3 n3 n1 n2 Slika 3.4. Lan~ani graf G = D(1, m2, m3;n1, n2, n3) Posmatrajmo graf G = D(1, m2, m3;n1, n2, n3) sa slike 3.4 kao koale- s en iju zvezde H = S1,n−(k+4) i grafa G1 = D(1, m2, m3; n1, n2, n3), gde je n3 = n3 − n + k + 4. Primetimo da je n3 > 0, |G1| = k + 4 i parame- tri grafa G1 zadovoqavaju osobinu (3.15). Tako|e, posmatrajmo graf D1 = D(1, 1; k+2, n−(k+4)) (slika 3.3) kao koales en iju grafovaH = S1,n−(k+4) i G2 = K2,k+2. Na sli i 3.4 i sli i 3.3 sa v je ozna~en ~vor dobijen prekla- pawem korena grafa H sa korenima grafova G1 i G2, respektivno. Dakle, kako je G = H ·G1 i D1 = H ·G2, na osnovu leme 7, sledi φ(G, λ)− φ(D1, λ) = λn−k−5 ( λ(φ(G1, λ)− φ(G2, λ)) − (n− k − 4)(φ(G1 − v, λ)− φ(G2 − v, λ)) ) . (3.16) Koriste}i rela ije (3.10) i (3.11) vidimo da je φ(G1, λ) = λ k−2(λ6 −m(G1)λ4 + (m2m3n1n2 +m2(n1 + n2)n3 +m3n1(n2 + n3))λ 2 −m2m3n1n2n3) i φ(G1 − v, λ) = λk(λ4 −m(G1 − v)λ2 +m2n1n2). 35 3.2. STRUKTURAEKSTREMALNIH BIPARTITNIH GRAFOVA Sli~no, iz (3.8) imamo φ(G2, λ) = φ(K2,k+2λ) = λ k+2(λ2 − 2(k + 2)) i φ(G2 − v, λ) = φ(K1,k+2λ) = λk+1(λ2 − (k + 2)). Odavde, pomo}u (3.16) dobijamo φ(G, λ)− φ(D1, λ) = λn−6 ( (m2m3n1n2 +m2(n1 + n2)n3 +m3n1(n2 + n3) + (n− k − 4)(m(G1 − v)−m(G2 − v)))λ2 −m2m3n1n2n3 ) . Kako grafG sadr`i zvezdu S1,n3 kao indukovani podgraf, onda na osnovu leme 5 va`i ρ(G) > √ n3. Za vrednost razlike φ(G, λ)− φ(D1, λ) dobijamo funk iju koja je rastu}a za pozitivno λ. Prema tome, za λ > √ n3 imamo φ(G, λ)− φ(D1, λ) > φ(G,√n3)− φ(D1,√n3) = n n−4 2 3 (m2(n1 + n2)n3 +m3n1(n2 + n3) + (n− k − 4)(m(G1 − v)−m(G2 − v))) > 0. Odavde zakqu~ujemoda jeρ(G) < ρ(D1), {to je u kontradik iji sa ~iweni om da ρ(G) mora biti maksimalno. Teorema 5. Ako je 0 6 k 6 4, tada je graf D(1, 1; k + 2, n− k − 4), prikazan na sli i 3.3, jedinstven graf sa maksimalnim indeksom me|u svim povezanim bipartitnim grafovima reda n i veli~ine n+ k (n > k + 4). Dokaz. Neka je G graf sa maksimalnim indeksom ρ(G) me|u svim povezanim bipartitnim grafovima reda n i veli~ine n + k (0 6 k 6 4, n > k + 4). Na osnovu teoreme 3 zakqu~ujemo da je graf G lan~ani graf D(m1, m2, . . . , mh; n1, n2, . . . , nh). Koriste}i osobinu (ii) teoreme 4 vidimo da je ta~no jedan od parametaram1 i n1 jednak 1. Ako je h > 3, tada je graf D0 = D(1, 1, 1, 1; 2, 1, 1, 1) podgraf grafa G i dolazimo do kontradik ije k = m(G)− n(G) > m(D0)− n(D0) = 5. Tvr|ewe teoreme sledi direktno iz teoreme 4. U teoremi 4 dokazano je da za fiksirano k i dovoqno veliko n maksi- malni indeks, odnosno minimalnu najmawu karakteristi~nu vrednost, me|u povezanim bipartitnim grafovima ima ili jedinstveni grafD1 (slika 3.3) ili neki lan~ani graf ~ija je visina ve}a od 3. Najverovatnije je da ovaj drugi slu~aj nije mogu}. To je i dokazano za k 6 4, u teoremi 5. Za k > 5 kompjuterska izra~unavawa potvr|uju ovu hipotezu ali ona jo{ uvek nije dokazana. 36 Glava 4 Grafovi sa malim brojem kontura i minimalnom najmawom karakteristi~nom vredno{}u Neka je G graf reda n i veli~ine m sa t komponenti povezanosti. Broj c = m − n + t naziva se iklomati~ni broj (engl. cyclomatic number) grafa G. Ako je G povezan graf, wegov iklomati~ni broj je c = m − n + 1. Za graf sa iklomati~nim brojem c ka`e se da je c− ikli~ni graf. Spe ijalno, za c = 1, 2, 3, 4, 5 radi se o uni ikli~nim, bi ikli~nim, tri ikli~nim, te- tra ikli~nim i penta ikli~nim grafovima, respektivno. Ako jeG povezan graf za koji je c = 0, onda je graf G stablo. Karakteristika grafova sa malim iklomati~nim brojem jeste da sadr`e mali broj kontura. Prema tome, ovi grafovi imaju jednostavniju strukturu nego grafovi ~iji je iklomati~ni broj veliki. Zbog te osobine, za wih je ispitan veliki broj spektralnih invarijantni. Jo{ 1987. godine S. Simi} objavquje prve rezultate u vezi sa spektralnim radijusom uni ikli~nih gra- fova [39], a zatim1989. godineibi ikli~nih grafova [40]. Poredindeksa, do danas su dobijeni rezultati u vezi sa energijom ovih grafova, glavnim karak- teristi~nim vrednostima, Laplasovim spektrom, Laplasovim spektralnim radijusom, Zagreb indeksom, Randi}evim indeksom i mnogim drugim karak- teristikama ovih grafova [19, 23, 24, 25, 49]. Nakon jednostavnijih klasa, spektralne invarijante i wihove osobine se ispituju i za slo`enije klase grafova, kao {to su tri ikli~ni, tetra ikli~ni, a zatim i svi povezani grafovi [3, 21, 29]. Osnovna tema ovog poglavqa je najmawa karakteristi~na vrednost gra- fova sa malim iklomati~nim brojem. Naime, prvo }e biti predstavqeno re{ewe problema minimalne najmawe karakteristi~ne vrednosti u klasi uni ikli~nih grafova fiksiranog reda. Istom tematikom bavili su se i Fan, Wang i Gao [16], ali je ovde prikazana druga~ija tehnika za re{avawe ovog problema. Zatim, ista tema }e biti razmatrana u klasi povezanih bi ikli~nih grafova sa n ~vorova. Bi}e opisana struktura grafa ~ija je 37 4.1. UNICIKLI^NI GRAFOVI FIKSIRANOG REDA najmawa karakteristi~na vrednost minimalna u ovoj klasi i pokazano da je taj graf jedinstven. Na kraju, problem }e biti pro{iren na sve povezane grafove reda n i veli~ine n+k za 0 6 k 6 4. Opisana je jedinstvena tehnika za odre|ivawe ekstremalnog grafa u svim pomenutim klasama grafova. Pod ekstremalnim grafom smatra}emo povezani graf reda n i veli~ine n + k ~ija je najmawa karakteristi~na vrednost minimalna u posmatranoj klasi grafova, odnosno ~iji je indeks maksimalan ukoliko se radi o bipartitnim grafovima. Da bismo do{li do navedenih rezultata, u nastavku }emo koristiti slede}e jednostavno tvr|ewe. Lema 26. Neka su n i k nenegativni eli brojevi takvi da je 0 6 k 6 4 i n > k + 4. Tada za svaki prirodan broj s takav da je 2 6 s 6 n − 2 va`i nejednakost s(n− s) > n+ k. Dokaz. Nejednakost s(n − s) > n + k je ekvivalentna sa nejednako{}u s2−ns+n+ k < 0. Posmatrajmo kvadratnu funk iju f(s) = s2−ns+n+ k. Ova funk ija ima dva pozitivna korena s1 = n−√n2 − 4(n+ k) 2 i s2 = n + √ n2 − 4(n+ k) 2 , pri ~emu je s1 < 2, a s2 > n− 2. Zbog toga, za svaki prirodan broj s takav da je 2 6 s 6 n − 2 va`i nejednakost f(s) = s2 − ns + n + k < 0, ~ime je lema dokazana. Spe ijalno, za k = 0, odnosno k = 1 dobijamo slede}a tvr|ewa. Posledi a 1. Neka je n prirodan broj ve}i od 4. Tada za svaki prirodan broj s, takav da je 2 6 s 6 n− 2, va`i nejednakost s(n− s) > n. Posledi a 2. Neka je n prirodan broj ve}i od 5. Tada za svaki prirodan broj s, takav da je 2 6 s 6 n− 2, va`i nejednakost s(n− s) > n + 1. 4.1 Uni ikli~ni grafovi fiksiranog reda Ozna~imo sa U(n) klasu povezanih uni ikli~nih grafova sa n ~vorova. Grafovi ove klase su veli~ine n. Klasa U(n) se mo`e posmatrati kao unija dve potklase, klase povezanih bipartitnih uni ikli~nih grafova sa n ~vo- rova i klase povezanih nebipartitnih uni ikli~nih grafova sa n ~vorova. Imaju}i u vidu teoremu 1, pomo}u ekstremalnih grafova ove dve potklase mo`e se odrediti ekstremalni graf u klasi U(n), {to }e u nastavku i biti pokazano. 38 4.1. UNICIKLI^NI GRAFOVI FIKSIRANOG REDA 4.1.1 Bipartitni uni ikli~ni grafovi Neka je sa U1(n) ozna~ena klasa povezanih bipartitnih uni ikli~nih grafova sa n ~vorova. S obzirom na to da je kod bipartitnih grafova spek- tar simetri~an, problem nala`ewa grafa ~ija je najmawa karakteristi~na vrednost minimalna u klasi U1(n) mo`e se svesti na problem odre|ivawa grafa sa maksimalnim indeksom u ovoj klasi. Na taj na~in dobijen je rezul- tat prikazan u slede}oj teoremi. PSfrag repla ements n− 4 v0 Slika 4.1. Uni ikli~ni graf U1 Teorema 6. Neka je G povezan bipartitan uni ikli~ni graf sa n (n > 3) ~vorova. Tada je ρ(G) 6 ρ(U1) i jednakost va`i ako i samo ako je G ∼= U1 (slika 4.1). Dokaz. Pretpostavimoda je grafG ∈ U1(n) graf sa maksimalnimindeksom u posmatranoj klasi. Neka je skup ~vorova ovog grafa V (G) = {v1, v2, . . . , vn} i neka je X = (x1, x2, . . . , xn) Peronov vektor grafa G, pri ~emu koordi- nata xi odgovara ~voru vi (1 6 i 6 n). Prvo }emo dokazati da se graf G sastoji iz jedne kontureCp i jednog stabla T prika~enog za neki ~vor v0 kon- ture Cp. U tom iqu pretpostavimo suprotno. Neka postoje dva razli~ita ~vora v0 i v1 konture Cp, za koje su prika~ena stabla T0 i T1, respektivno. Ozna~imo sa z1, . . . , zs (s > 1) ~vorove stabla T0 koji su susedni sa ~vorom v0, a sa w1, w2, . . . , wt (t > 1) ~vorove stabla T1 koji su susedni sa ~vorom v1. Ako je x0 > x1, neka je G∗ = G− {v1w1, . . . , v1wt}+ {v0w1, . . . , v0wt}, a ako je x0 < x1, neka je G∗ = G− {v0z1, . . . , v0zs}+ {v1z1, . . . , v1zs}. U oba slu~aja dobijeni graf G∗ pripada klasi U1(n). Na osnovu leme 3, dobijamo da je ρ(G∗) > ρ(G), {to je u suprotnosti sa izborom grafa G. Po{to jeG bipartitan graf, du`ina p kontureCp mora biti paran broj. Sada }emo pokazati da kontura Cp sadr`i ta~no 4 ~vora. Pretpostavimo suprotno, tj. neka je p > 4. Sa v0, v1, . . . , vp−1 ozna~imo ~vorove konture Cp. O~igledno G 6= Wn i v0, v1, . . . , vp−1, v0 je zatvoren unutra{wi put u grafu G. Neka je G∗ = G− vp−2vp−3 + v0vp−3. 39 4.1. UNICIKLI^NI GRAFOVI FIKSIRANOG REDA Tada G∗ ∈ U1(n). Na osnovu lema 8 i 5 dobijamo da je ρ(G∗) > ρ(G) {to je nemogu}e, po{to je G graf sa maksimalnim indeksom u posmatranoj klasi. Odatle zakqu~ujemo da je p = 4. Ovim je dokazano da je G = C4 · Tn−3. Kako je U1 = C4 · S1,n−4, onda na osnovu leme 10 sledi da je graf U1 sa slike 4.1 jedinstven graf sa maksimal- nim indeksom u klasi U1(n). Kori{}ewem prethodne teoreme direktno dobijamo ekstremalni graf u klasi bipartitnih uni ikli~nih grafova fiksiranog reda. Teorema 7. Neka je G povezan bipartitan uni ikli~ni graf sa n (n > 3) ~vorova ~ija je najmawa karakteristi~na vrednost minimalna u klasi U1(n). Tada je G ∼= U1 (slika 4.1). 4.1.2 Nebipartitni uni ikli~ni grafovi Ozna~imo sa U2(n) klasu povezanih uni ikli~nih grafova reda n koji predstavqaju kompletan proizvod dva stepenasta grafa. Mo`e se pokazati da je ekstremalni graf u ovoj klasi graf sa slike 4.2. PSfrag repla ements n− 3 v0 Slika 4.2. Uni ikli~ni graf U2 Teorema 8. Neka je G povezan nebipartitni uni ikli~ni graf sa n (n > 3) ~vorova koji predstavqa kompletan proizvod dva stepenasta grafa. Tada je λ(G) > λ(U2) i jednakost va`i ako i samo ako je G ∼= U2 (slika 4.2). Dokaz. Iz tabele A.1 povezanih grafova reda n 6 5, lako je videti da za n = 3 i n = 4 jedini grafovi koji dolaze u obzir su grafovi oblika U2, pa teorema va`i za ove grafove. Neka je daqe G povezan nebipartitni uni ikli~ni graf reda n (n > 4) i neka je G = H1∇H2, gde su H1 i H2 stepenasti grafovi. Neka je H1 graf reda s i H2 graf reda n − s, pri ~emu je 1 6 s 6 n − 2. Tada je s = 1. U suprotnom, na osnovu posledi e 1 dobijamo |E(G)| = |E(H1∇H2)| > s(n− s) > n, {to je kontradik ija. Dakle, grafH1 je reda 1, a grafH2 je redan−1. Jedini graf koji zadovoqava ove uslove u klasi U2(n) je graf U2 (slika 4.2). 40 4.1. UNICIKLI^NI GRAFOVI FIKSIRANOG REDA 4.1.3 Struktura ekstremalnog uni ikli~nog grafa Na osnovu rezultata prikazanih u sek ijama 4.1.1 i 4.1.2 mo`e se opisati struktura grafa ~ija je najmawa karakteristi~na vrednost minimalna u klasi U(n) povezanih uni ikli~nih grafova fiksiranog reda. Kako za ekstremalni grafG ∈ U(n) va`i daG ∈ U1(n)∪U2(n) dovoqno je uporediti ekstremalne grafove klasa U1(n) i U2(n). Lema 27. Neka je U1 graf reda n prikazan na sli i 4.1, U2 graf reda n prikazan na sli i 4.2. (i) Ako je 4 6 n 6 11, tada je λ(U1) < λ(U2). (ii) Ako je n > 12, tada je λ(U2) < λ(U1). Dokaz. Iz tabele A.1 povezanih grafova reda n 6 5 (dodatak A), o~igledno je da lema va`i za n = 4 i n = 5. Pretpostavimo da je u nastavku n > 6. Odredimo prvo karakteristi~ne polinome grafova U1 i U2. Kori{}ewem leme 6 dobijamo φ(U1, λ) = λ n−4(λ4 − nλ2 + 2(n− 4)),(4.1) φ(U2, λ) = λ n−4(λ4 − nλ2 − 2λ+ n− 3).(4.2) Iz (4.1) zakqu~ujemo da graf U1 ima ta~no dve negativne karakteristi~ne vrednosti: λn ∈ (−∞,−2) i λn−1 ∈ (−2, 0). Tako|e, iz (4.2) zakqu~ujemo da i grafU2 ima ta~no dve negativne karakteristi~ne vrednosti: λn ∈ (−∞,−2) i λn−1 ∈ (−2, 0). Iz karakteristi~nog polinoma grafa U1 o~igledno je λ(U1) = − √ n+ √ (n− 4)2 + 16 2 . Posmatrajmo funk iju f(λ) = λ4− nλ2− 2λ+ n− 3. Ova funk ija ima iste nenula korene kao polinom φ(U2, λ) i va`i f(λ(U1)) = 5− n + √ 2(n + √ (n− 4)2 + 16). Kako je lim λ→−∞ f(λ) = +∞, zakqu~ujemo da va`e implika ije f(λ(U1)) > 0 ⇒ λ(U1) < λ(U2),(4.3) f(λ(U1)) < 0 ⇒ λ(U2) < λ(U1).(4.4) Ispitajmo za koje vrednosti prirodnog broja n je ispuwena nejednakost f(λ(U1)) > 0. Zamenom vrednosti za f(λ(U1)) dobijamo 5− n + √ 2(n+ √ (n− 4)2 + 16) > 0, 41 4.2. BICIKLI^NI GRAFOVI FIKSIRANOG REDA odnosno √ 2(n+ √ (n− 4)2 + 16) > n− 5 > 0. Nakon kvadrirawa i sre|ivawa dobijamo ekvivalentnu nejednakost 2 √ (n− 4)2 + 16 > (n− 6)2 − 11. Ova nejednakost je o~igledno zadovoqena za (n − 6)2 − 11 < 0, odnosno za 6 6 n 6 9. Za n > 10 dobijamo ekvivalentnu nejednakost (4.5) (n− 6)4 − 26(n− 6)2 − 16(n− 6) + 41 < 0. Neka jex = n−6 > 4. Funk ija g(x) = x4−26x2−16x+41 ima ta~no jedan koren x = 5.2498 na intervalu [4,+∞) i negativna je na tom intervalu ako i samo ako je 4 6 x < 5.2498. Otuda, nejednakost (4.5) va`i za 4 6 n− 6 6 5, tj. 10 6 n 6 11. Na ovaj na~in smo dokazali da je f(λ(U1)) > 0 ako i samo ako je 6 6 n 6 11. Na osnovu (4.3) zakqu~ujemo da je λ(U1) < λ(U2). Sli~no se dokazuje da je f(λ(U1)) < 0 ako i samo ako je n > 12, pa na osnovu implika ije (4.4) va`i λ(U2) < λ(U1). Kori{}ewem prethodne leme i teorema 7 i 8 mo`emo opisati strukturu ekstremalnog grafa klase U(n). Naredna teorema predstavqa najva`niji rezultat poglavqa 4.1. Teorema 9. Neka je G povezan uni ikli~ni graf reda n. (i) Ako je 4 6 n 6 11, tada je λ(G) > λ(U1) i jednakost va`i ako i samo ako je G ∼= U1 (slika 4.2). (ii) Ako je n > 12, tada je λ(G) > λ(U2) i jednakost va`i ako i samo ako je G ∼= U2 (slika 4.1). 4.2 Bi ikli~ni grafovi fiksiranog reda Sli~nom tehnikomkao u sek iji 4.1, u nastavku }e biti opisana struktura grafa ~ija je najmawa karakteristi~na vrednost minimalna u klasiB(n) po- vezanih bi ikli~nih grafova sa n ~vorova. Kod ovakvih grafova broj grana je m = n + 1. Imaju}i na umu teoremu 1 ovaj problem se mo`e razlo`iti na probleme minimalne najmawe karakteristi~ne vrednosti u klasi bipartit- nih bi ikli~nih grafova i u klasi nebipartitnih bi ikli~nih grafova koji predstavqaju kompletan proizvod dva stepenasta grafa. 42 4.2. BICIKLI^NI GRAFOVI FIKSIRANOG REDA 4.2.1 Bipartitni bi ikli~ni grafovi Ozna~imo sa B1(n) skup svih povezanih bipartitnih bi ikli~nih gra- fova. Kako je spektar bipartitnog grafa simetri~an u odnosu na nulu, problem minimalne najmawe karakteristi~ne vrednosti u klasi B1(n) je ekvivalentan sa problemom maksimalnog indeksa u ovoj klasi. Stoga, u nastavku pa`wa }e biti usmerena na indekse odgovaraju}ih grafova. PSfrag repla ements n− 5 n− 6n− 7 B1 B2 B3 vv v Slika 4.3. Bi ikli~ni grafovi B1, B2 i B3 Ozna~imo sa G − x i G − xy grafove dobijene iz grafa G uklawawem ~vora x ∈ V (G), odnosno grane xy ∈ E(G), respektivno. Sli~no, neka je G+xy graf dobijen iz grafaG dodavawem grane xy /∈ E(G), gde x, y ∈ V (G). Lema 28. Neka je G povezan bipartitni bi ikli~ni graf reda n (n > 5), pri ~emu G 6∈ {B1, B2, B3}. Tada je (4.6) ρ(G) < max{ρ(B1), ρ(B2), ρ(B3)}, gde su B1, B2 i B3 grafovi sa slike 4.3. Dokaz. Iz tabele povezanih grafova reda n 6 5 i tabele povezanih bi i- kli~nih grafova reda 6 vidi se da teorema va`i zan = 5 in = 6 (tabeleA.1 i A.2). Pretpostavimo sada da je n > 7. Izaberimo grafG ∈ B1(n) takav da je indeks grafa G najve}i mogu}i u ovoj klasi. Neka je V (G) = {v1, v2, . . . , vn} skup ~vorova grafa G i X = (x1, x2, . . . , xn) Peronov vektor grafa G, gde koordinata xi odgovara ~voru vi (1 6 i 6 n). Prvo }emo dokazati da svake dve konture Cp i Cq grafa G imaju naj- mawe jedan zajedni~ki ~vor. Pretpostavimo suprotno, tj. da postoji put v1, v2, . . . , vl koji povezuje konture Cp i Cq (v1 ∈ V (Cp), vl ∈ V (Cq), l > 2). Bez gubitka op{tosti, pretpostavimo da je x1 > xl. Ozna~imo sa vl+1 i vl+2 ~vorove konture Cq koji su susedni sa ~vorom vl. Tada ~vorovi vl+1 i vl+2 nisu susedni sa ~vorom v1, jer u suprotnom graf G nije bi ikli~an. Neka je G∗ = G− {vlvl+1, vlvl+2}+ {v1vl+1, v1vl+2}. O~igledno, G∗ ∈ B1(n). Na osnovu leme 3 dobijamo da je ρ(G) < ρ(G∗), {to je u kontradik iji sa izborom grafa G. 43 4.2. BICIKLI^NI GRAFOVI FIKSIRANOG REDA PSfrag repla ements w1 w2 v1v1 v2 G01 w3 w4 G02 Cp Cq P1 P2 P3 Slika 4.4. OsnovaG0 bi ikli~nog grafa Dakle, svake dve konture u grafu G imaju bar jedan zajedni~ki ~vor i mo`emo razlikovati slede}a dva slu~aja. 1◦ U grafu G dve konture Cp i Cq imaju ta~no jedan zajedni~ki ~vor. U ovom slu~aju graf G sadr`i graf G01 sa slike 4.4 kao indukovani podgraf. Primetimo da je graf G01 funk ija odgovaraju}ih parametara p i q, tj. G01 = G 0 1(p, q), gde parametri p i q predstavqaju broj ~vorova redom kontura Cp i Cq i oni su parni prirodni brojevi. 2◦ Postoje dve konture u grafu G koje imaju vi{e od jednog zajedni~kog ~vora. Tada u grafu G postoji indukovani podgraf G02, koji sadr`i tri dis- junktna puta P1, P2 i P3 sa zajedni~kim po~etnim ~vorom v1 i zajedni~kim krajwim ~vorom v2 (slika 4.4). Najvi{e jedan od ova tri puta je du`ine 1. Graf G02 je funk ija odgovaraju}ih parametara p, q i r, tj. G 0 2 = G 0 2(p, q, r). Ovde parametri p, q i r predstavqaju broj ~vorova odgovaraju}ih puteva grafaG02 i oni su svi parni prirodni brojevi ili su svi neparni prirodni brojevi. Na osnovu 1◦ i 2◦ zakqu~ujemo da graf G sadr`i jedan od grafova G01 i G02 kao indukovani podgraf. Ozna~imo sa B11(n) ⊆ B1(n) skup svih bi ikli~nih grafova koji sadr`e graf G01 kao indukovani podgraf, sa B21(n) ⊆ B1(n) skup svih bi ikli~nih grafova koji sadr`e grafG02 kao indukovani podgraf pri ~emu su parametri p, q i r parni prirodni brojevi i sa B31(n) ⊆ B1(n) skup svih bi ikli~nih grafova koji sadr`e graf G02 kao indukovani podgraf i parametri p, q i r su neparni prirodni brojevi. Tada Bi1(n) ∩ Bj1(n) = ∅ (i, j = 1, 2, 3; i 6= j) i G ∈ ∪3i=1Bi1(n). Pretpostavimo prvo da graf G pripada skupu B11(n). Tada je o~igledno G = B1 za n = 7 (slika 4.3). Neka je u nastavku n > 7. Tada je n > p + q − 1. Zaista, u suprotnom slu~aju jeG = G01(p, q) (p > q) i postoji grafH ∈ B11(n) (slika 4.5) takav da je na osnovu lema 8 i 5 ρ(G01) < ρ(H), {to je nemogu}e. Neka je daqe sa v1 ozna~en zajedni~ki ~vor kontura Cp i Cq u grafu G 0 1 (slika 4.4). Dokaza}emo da se graf G sastoji iz grafa G01 sa jednim stablom zaka~enim za ~vor v1. Pretpostavimo suprotno, tj. da postoji ~vor v grafa 44 4.2. BICIKLI^NI GRAFOVI FIKSIRANOG REDA PSfrag repla ements Cp−2 Cq Slika 4.5. GrafH G01 takav da je v 6= v1 i postoji stablo T zaka~eno za v. Ukoliko je x1 > xv, neka su z1, . . . , zs (s > 1) ~vorovi stabla T koji su susedni sa ~vorom vi i neka je G∗ = G− {vz1, . . . , vzs}+ {v1z1, . . . , v1zs}. U slu~aju kada je x1 < xv ozna~imo sa w1, w2, . . . , wt (t > 4) ~vorove susedne sa ~vorom v1 (slika 4.4). Ako je v ~vor konture Cp, neka je G∗ = G− {v1w3, . . . , v1wt}+ {vw3, . . . , vwt}. U oba slu~aja G∗ ∈ B11(n). Na osnovu leme 3, dobijamo da je ρ(G∗) > ρ(G). Ovo je nemogu}e s obzirom na to daG ima maksimalni indeks u posmatranoj klasi. Dakle, graf G ima jedinstveno stablo prika~eno za ~vor v1 grafa G01. Po defini iji grafa G 0 1, vidimo da su p i q parni prirodni brojevi. Dokaza}emo da je p = q = 4. Pretpostavimo suprotno, tj. da je p > 4. Ozna~imo sa v1, v2, . . . , vp ~vorove konture Cp, a sa u ~vor stepena jedan stabla T prika~enog za ~vor v1 grafa G 0 1. O~igledno, G 6= Cn, G 6= Wn, v1, v2, . . . , vp, v1 je zatvoren unutra{wi put i ~vor u pripada putu koji nije unutra{wi put. Neka je G∗ = G− {v1vp, vp−1vp−2}+ {v1vp−2, uvp}. Tada G∗ ∈ B11(n). Graf izomorfan grafu G mo`e se dobiti iz grafa G∗ podelom grane v1vp−2 grafa G∗ pomo}u dva nova ~vora i brisawem ~vorova vp i vp−1 iz grafa G∗. Na osnovu lema 8 i 5, va`i da je ρ(G∗) > ρ(G), {to je u kontradik iji sa izborom grafa G. Dakle, p = 4. Na sli~an na~in se dokazuje da je q = 4. Kona~no, dokaza}emo da stablo T , koje je zaka~eno za ~vor v1 grafa G 0 1, sadr`i samo ~vorove na udaqenosti jedan od korena v1. U suprotnom postoji ~vor stabla T ~ija je udaqenost od ~vora v1 ve}a od jedan. Neka je vj ∈ V (T ) ~vor koji je najudaqeniji od korena v1. Tada je d(v1, vj) > 2 i postoji put v1 . . . vj−2vj−1vj du`ine ve}e od jedan, koji povezuje ~vorove v1 i vj . Posma- trajmo sada ~vor vj−2 kao koren r grafa A sa slike 2.3. Primenom leme 9 dobijamo graf G∗ ∈ B11(n), takav da je ρ(G∗) > ρ(G). Zbog izbora grafa G posledwa nejednakost je nemogu}a, pa zakqu~ujemo da je G ∼= B1 (slika 4.3). Analogno prethodnom postupku, pokazuje se da ako graf G ∈ B21(n), tada je G ∼= B2, a ako G ∈ B31(n), tada je G ∼= B3 (slika 4.3). Kako G ∈ ∪3i=1Bi1(n) (Bi1(n) ∩ Bj1(n) = ∅, i, j = 1, 2, 3, i 6= j) zakqu~ujemo da va`i nejednakost (4.6). 45 4.2. BICIKLI^NI GRAFOVI FIKSIRANOG REDA Rezultati prethodne teoreme ukazuju na to da se prilikom odre|ivawa ekstremalnog grafa u klasi B1(n) razmatrawe mo`e suziti na grafove B1, B2 i B3 prikazane na sli i 4.3. Za dobijawe glavnog rezultata potrebno je uporediti najmawe karakteristi~ne vrednosti ova tri grafa, odnosno wihove indekse. Lema 29. Neka su B1, B2 i B3 grafovi reda n prikazani na sli i 4.3. Ako je n > 7, tada je ρ(B2) > ρ(B1) i ρ(B2) > ρ(B3). Dokaz. Primenom leme 6 na ~vor v grafa B1 dobijamo (4.7) φ(B1, λ) = λ n−6(λ2 − 2)(λ4 − (n− 1)λ2 + 2n− 14). Istim postupkom dobijamo φ(B2, λ) = λ n−4(λ4 − (n+ 1)λ2 + 3n− 15),(4.8) φ(B3, λ) = λ n−6(λ2 − 1)(λ4 − nλ2 + 3n− 17).(4.9) Iz (4.7) se lako zakqu~uje da za n = 7 graf B1 ima ta~no dve pozitivne karakteristi~ne vrednosti: ρ ∈ (2,+∞) i λ2 = √ 2, a za n > 7 ima ta~no tri pozitivne karakteristi~ne vrednosti: ρ ∈ (2,+∞), λ2 = √ 2 i λ3 ∈ (0, √ 2). Tako|e, iz (4.8) se zakqu~uje da graf B2 ima ta~no dve pozitivne sopstvene vrednosti: ρ ∈ (2,+∞) i λ2 ∈ (0, 2). Iz (4.9) sledi da graf B3 ima ta~no tri pozitivne karakteristi~ne vrednosti: ρ ∈ (2,+∞), λ2 = 1 i λ3 ∈ (0, 1) za n = 7; ρ ∈ (2,+∞) i λ2 = λ3 = 1 za n = 8; ρ ∈ (2,+∞), λ2 ∈ (1, 2) i λ3 = 1 za n > 8 . Iz jednakosti (4.8) i (4.9) lako se dobija ρ(B1) = √ n− 1 +√(n− 5)2 + 32 2 i ρ(B3) = √ n+ √ (n− 6)2 + 32 2 . Posmatrajmo funk iju f(λ) = λ4 − (n + 1)λ2 + 3n − 15. Primetimo da ova funk ija ima iste nenula korene kao φ(B2, λ) i va`i f(ρ(B1)) = −1 2 ( 1 + √ (n− 5)2 + 32 ) < 0, f(ρ(B3)) = −1 2 ( n− 4 + √ (n− 6)2 + 32 ) < 0. Po{to je lim λ→+∞ f(λ) = +∞, zakqu~ujemo da je ρ(B2) > ρ(B1) i ρ(B2) > ρ(B3). Primenom leme 28 i leme 29 dobijamo jedinstven graf ~ija je najmawa sopstvena vrednost minimalna u klasi B1(n). Teorema 10. Neka je G povezan bipartitni bi ikli~ni graf reda n (n > 5). Tada je λ(B2) 6 λ(G) i jednakost va`i ako i samo ako G ∼= B2. 46 4.2. BICIKLI^NI GRAFOVI FIKSIRANOG REDA 4.2.2 Nebipartitni bi ikli~ni grafovi Ozna~imo sa B2(n) klasu povezanih bi ikli~nih grafova reda n koji predstavqaju kompletan proizvod dva stepenasta grafa. U nastavku }e pro- blem minimalne najmawe karakteristi~ne vrednosti biti re{en u klasi B2(n). PSfrag repla ements n− 4 v Slika 4.6. Bi ikli~ni graf B4 Teorema 11. Neka je G povezan nebipartitni bi ikli~ni graf sa n ~vorova (n > 5) koji je kompletan proizvod dva stepenasta grafa i neka je B4 graf prikazan na sli i 4.6. Tada je λ(B4) 6 λ(G) i jednakost va`i ako i samo ako je G ∼= B4. Dokaz. Iz tabeleA.1 povezanih grafova redan6 5, lako je videti da teorema va`i za n = 5. Neka je n > 6 i G ∈ B2(n) takav da je G = H1∇H2, gde su H1 i H2 stepenasti grafovi. Ozna~imo sa s (1 6 s 6 n−2) red grafaH1. O~igledno, graf H2 je reda n − s. Dokaza}emo da je s = 1. U suprotnom, na osnovu posledi e 2, dobijamo |E(G)| = |E(H1∇H2)| > s(n− s) > n+ 1, {to je kontradik ija. Dakle, |H1| = 1 i |H2| = n − 1. Jedini graf koji zadovoqava ove uslove u klasi B2(n) je graf B4 sa slike 4.3. 4.2.3 Struktura ekstremalnog bi ikli~nog grafa Kori{}ewem teorema 10 i 11 mo`e se odrediti jedinstveni graf sa mi- nimalnom najmawom karakteristi~nom vredno{}u u klasi svih povezanih bi ikli~nih grafova B(n). Naime, dovoqno je uporediti najmawe karakte- risti~ne vrednosti ekstremalnih grafova klasa B1(n) i B2(n). Lema 30. Neka je B2 graf prikazan na sli i 4.3,B4 graf prikazan na sli i 4.6 i n broj ~vorova ovih grafova. (i) Ako je 5 6 n 6 27, tada je λ(B2) < λ(B4). (ii) Ako je n > 28, tada je λ(B4) < λ(B2). 47 4.2. BICIKLI^NI GRAFOVI FIKSIRANOG REDA Dokaz. Iz tabele A.1 povezanih grafova reda n 6 5 i tabele A.2 povezanih bi ikli~nih grafova reda 6 lako je videti da lema va`i za n = 5 i n = 6. Pretpostavimo sada da je n > 7. Na osnovu leme 6 dobijamo da je φ(B2, λ) = λ n−4(λ4 − (n+ 1)λ2 + 3n− 15), φ(B4, λ) = λ n−4(λ4 − (n+ 1)λ2 − 4λ+ 2n− 8). Primetimo da graf B2 ima ta~no dve negativne sopstvene vrednosti: λn ∈ (−∞,−2) i λn−1 ∈ (−2, 0). Graf B4 ima tako|e ta~no dve negativne sopstvene vrednosti: λn ∈ (−∞,−2) i λn−1 ∈ (−2, 0). O~igledno, λ(B2) = − √ n + 1 + √ (n− 5)2 + 36 2 . Neka je f(λ) = λ4−(n+1)λ2−4λ+2n−8. Polinom f(λ) ima iste nenula korene kao karakteristi~ni polinom φ(B4, λ) i f(λ(B2)) = −n + 7 + 4 √ n+ 1 + √ (n− 5)2 + 36 2 . Kako je lim λ→−∞ f(λ) = +∞ zakqu~ujemo da va`e slede}e implika ije f(λ(B2)) > 0 ⇒ λ(B2) < λ(B4), f(λ(B2)) < 0 ⇒ λ(B4) < λ(B2). Ispitajmo za koje vrednosti prirodnog broja n va`i nejednakost −n + 7 + 4 √ n+ 1 + √ (n− 5)2 + 36 2 > 0, odnosno 4 √ n + 1 + √ (n− 5)2 + 36 2 > n− 7 > 0. Nakon kvadrirawa i sre|ivawa dobijamo ekvivalentnu nejednakost 8 √ (n− 5)2 + 36 > (n− 11)2 − 80, koja je, o~igledno, zadovoqena za (n− 11)2 − 80 < 0, odnosno za 7 6 n 6 19. Za n > 20, nakon kvadrirawa i sre|ivawa dobijamo nejednakost (4.10) (n− 11)4 − 224(n− 11)2 − 768(n− 11) + 1792 < 0. Neka je x = n − 11 > 9. Funk ija g(x) = x4 − 224x2 − 768x + 1792 ima ta~no jedan koren x = 16.2619 na intervalu [9,+∞) i negativna je na tom intervalu ako i samo ako je x < 16.2619. Dakle, nejednakost (4.10), koja je ekvivalentna sa polaznom nejednako{}u za n > 20, je zadovoqena u slu~aju kada je 9 6 n−11 6 16, tj. 20 6 n 6 27. 48 4.3. TRICIKLI^NI, TETRACIKLI^NII PENTACIKLI^NI GRAFOVI FIKSIRANOG REDA Imaju}i na umu lemu 28, teoreme 10 i 11 i lemu 30 dolazimo do glavnog rezultata sek ije 4.2. Teorema 12. Neka je G povezan bi ikli~ni graf reda n. (i) Ako je 5 6 n 6 27, tada je λ(G) > λ(B2) i jednakost va`i ako i samo ako G ∼= B2. (ii) Ako je n = 4 ili n > 28, tada je λ(G) > λ(B4) i jednakost va`i ako i samo ako G ∼= B4. 4.3 Tri ikli~ni, tetra ikli~ni i penta ikli~ni grafovi fiksiranog reda Postupak koji je kori{}en za odre|ivawe grafova sa minimalnom naj- mawom sopstvenom vredno{}u u klasama povezanih uni ikli~nih i bi i- kli~nih grafova fiksiranog reda postaje veoma komplikovan ako se po- smatraju povezani tri ikli~ni, tetra ikli~ni i penta iki~ni grafovi fiksiranog reda. U ovom poglavqu bi}e prikazana druga~ija tehnika koja ovaj problem re{ava u klasi povezanih c ikli~nih grafova fiksiranog reda za 1 6 c 6 5. Problem minimalne najmawe sopstvene vrednosti bi}e re{en u klasi povezanih grafova reda n i veli~ine n + k, gde je 0 6 k 6 4 i n > k + 4. Ova tehnika se tako|e oslawa na teoremu 1, tj. odvojeno se razmatraju klase bipartitnih i nebipartitnih grafova. Problem minimalne najmawe karakteristi~ne vrednosti grafa u klasi povezanih bipartitnih grafova reda n i veli~ine n + k (0 6 k 6 4, n > k + 4) ekvivalentan je problemu maksimalnog indeksa grafa u istoj klasi i on je re{en u poglavqu 3.2 (teorema 5). Zbog toga }e u ovom poglavqu biti razmatrani samo nebipartitni grafovi. 4.3.1 Nebipartitni grafovi sa malim brojem kontura Neka je k > 0, n > k + 4 i 0 6 q 6 k 2 . Ozna~imo sa Gq stepenasti graf ~ija je matri a susedstva oblika (1) (i) (j) 0 1 1 1 . . . 1 1 . . . 1 1 . . . 1 (1) 0 1 1 . . . 1 1 . . . 1 (2) 0 1 . . . 1 (3) gde je i = q + 3 i j = k − q + 3. Graf Gq, za q > 0 i i < j, prikazan je na sli i 4.7. 49 4.3. TRICIKLI^NI, TETRACIKLI^NII PENTACIKLI^NI GRAFOVI FIKSIRANOG REDA PSfrag repla ements q v1 v2 v3 v4 vi vi+1 vj vj+1 vn Slika 4.7. Graf Gq za q > 0 i i < j Wegov kanoni~ki graf ima ta~no 6 nenula karakteristi~nih vrednosti i prikazan je na sli i 4.8. Na osnovu leme 11 zakqu~ujemo da i grafGq u ovom slu~aju ima ta~no 6 nenula karakteristi~nih vrednosti.PSfrag repla em ts v1 v2 v3 v4 v5 v6 Slika 4.8. Kanoni~ki graf grafa Gq za q > 0 i i < j Neka jeX = (x1, y1, z1, r1, . . . , rq, s1, . . . , sj−i, t1, . . . , tn−j) karakteristi~ni vektor koji odgovara nenula karakteristi~noj vrednosti λ grafa Gq, pri ~emu wegove koordinate odgovaraju redom ~vorovima v1, . . . , vn (slika 4.7). Koriste}i (λ,X)karakteristi~ne jedna~ine grafa Gq zakqu~ujemo da je r1 = · · · = rq, s1 = · · · = sj−i, t1 = · · · = tn−j . Tako|e zakqu~ujemo da koordinate x1, y1, z1, r1, s1 i t1 zadovoqavaju slede}e jednakosti λx1 = y1 + z1 + qr1 + (j − i)s1 + (n− j)t1, λy1 = x1 + z1 + qr1 + (j − i)s1, λz1 = x1 + y1 + qr1, λr1 = x1 + y1 + z1, λs1 = x1 + y1, λt1 = x1. Dobijeni homogeni sistem jedna~ina ima netrivijalna re{ewa (po x1, y1, z1, r1, s1 i t1) ako i samo ako je wegova determinanta jednaka nuli, tj. 50 4.3. TRICIKLI^NI, TETRACIKLI^NII PENTACIKLI^NI GRAFOVI FIKSIRANOG REDA (4.11) ∣∣∣∣∣∣∣∣∣∣∣∣ λ −1 −1 −q −j + i −n + j −1 λ −1 −q −j + i 0 −1 −1 λ −q 0 0 −1 −1 −1 λ 0 0 −1 −1 0 0 λ 0 −1 0 0 0 0 λ ∣∣∣∣∣∣∣∣∣∣∣∣ = 0. Dakle, nenula sopstvene vrednosti grafa Gq zadovoqavaju jedna~inu (4.11), a razvojem posledwe determinante dobija se φ(Gq, λ) = λ n−6(λ6 − (n + k)λ4 − 2(k + q + 1)λ3 + (k(n+ 3q − 4) + n− k2 − 4q2 − 2q − 3)λ2 + 2q(n− q − 3)λ + q(k − 2q)(3 + k − n− q)). (4.12) PSfrag repla ements n− (k + 3) k + 1 Slika 4.9. Graf G0 Jednakost (4.12) daje vrednost karakteristi~nog polinoma grafa Gq i u slu~ajevima q = 0, odnosno i = j. Graf G0 prikazan je na sli i 4.9, a wegov karakteristi~ni polinom glasi φ(G0, λ) = λ n−6(λ6 − (n + k)λ4 − 2(k + 1)λ3 + (k(n− 4) + n− k2 − 3)λ2).(4.13) U vezi sa pomenutim grafovima dokazujemo slede}u lemu. Lema 31. Ako je k > 2 i q > 1, tada je λ(G0) < λ(Gq). Dokaz. Iz jednakosti (4.12) i (4.13) dobijamo φ(Gq, λ)− φ(G0, λ) = qλn−6(−2λ3 + (3k − 4q − 2)λ2 + 2(n− q − 3)λ − (k − 2q)(n+ q − k − 3)). Neka je f(λ) = −2λ3 + (3k − 4q − 2)λ2 + 2(n− q − 3)λ− (k − 2q)(n+ q − k − 3). Funk ija f(λ) ima ta~no jedan negativan koren α0. Ona je pozitivna i strogo opadaju}a na (−∞, α0) i negativna na (α0, 0). 51 4.3. TRICIKLI^NI, TETRACIKLI^NII PENTACIKLI^NI GRAFOVI FIKSIRANOG REDA Po{to je f(−√n− 3) = 2q√n− 3 + (k − 2q)(k − q) + 2(k − q − 1)(n− 3) > 0, zakqu~ujemo da −√n− 3 ∈ (−∞, α0). Tako|e, za λ < − √ n− 3 va`i f(λ) > f(−√n− 3) > 0. Mo`emo razlikovati slede}a dva slu~aja. 1◦ n  paran broj U ovom slu~aju, za λ < −√n− 3, dobijamo φ(Gq, λ)− φ(G0, λ) = qλn−6f(λ) > qλn−6f(− √ n− 3) > 0, tj. φ(Gq, λ) > φ(G0, λ). 2◦ n  neparan broj Tada za λ < −√n− 3 imamo φ(Gq, λ)− φ(G0, λ) = qλn−6f(λ) < qλn−6f(− √ n− 3) < 0, tj. φ(Gq, λ) < φ(G0, λ). Po{to je zvezda S1,n−3 indukovani podgraf grafa Gq (0 6 q 6 k2 ), onda je λ(Gq) 6 λ(S1,n−3) = − √ n− 3. Prema tome, iz 1◦ i 2◦ sledi da je λ(G0) < λ(Gq). Teorema 13. Ako je 0 6 k 6 4, tada je graf G0 (slika 4.9) jedinstveni graf sa minimalnom najmawom karakteristi~nom vredno{}u me|u svim povezanim grafovima reda n i veli~ine n + k (n > k + 4) koji su kompletni proizvodi dva stepenasta grafa. Dokaz. Neka jeG graf sa minimalnom najmawom sopstvenom vredno{}ume|u svim povezanim grafovima reda n i veli~ine n + k (0 6 k 6 4, n > k + 4), koji su kompletni proizvodi dva stepenasta grafa. Tada je G = H1∇H2, gde je |H1| = s i |H2| = n − s (1 6 s 6 n − 2). Zakqu~ujemo da je s = 1, jer u suprotnom slu~aju dolazimo do kontradik ije |E(G)| = |E(H1∇H2)| > s(n− s) > 2(n− 2) > n + k. Dakle, |H1| = 1 i |H2| = n − 1. Sledi da je G ∼= Gq (0 6 q 6 k2 ), jer je u suprotnom |E(G)| > n + 5 > n + k, {to je nemogu}e. Dakle, za 0 6 k 6 1 tvr|ewe je o~igledno, a za 2 6 k 6 4 tvr|ewe sledi iz leme 31. 52 4.3. TRICIKLI^NI, TETRACIKLI^NII PENTACIKLI^NI GRAFOVI FIKSIRANOG REDA 4.3.2 Struktura ekstremalnog grafa sa malim brojem kontura Da bismo odredili ekstremalni graf me|u grafovima fiksiranog reda sa malim brojem kontura potrebno je jo{ uporediti ekstremalne grafove u klasama bipartitinih, odnosno nebipartitnih grafova. U teoremama 5 i 13 je pokazano da su u pitawu grafoviD1 (slika 3.3) iG0 (slika 4.9). Stoga, u nastavku }e pa`wa biti posve}ena ovim grafovima. Naime, potrebno je odrediti koji od wih ima mawu najmawu karakteristi~nu vrednost za proizvoqni izbor parametara n i k (0 6 k 6 4, n > k + 4). Neka je Q(t) = t4 − 2(k + 1)2(3k2 + 12k + 13)t2 − 8(k + 1)5(k + 2)t − (k + 1)5(3k3 + 5k2 − 23k − 41). Polinom Q(t) ima ta~no dva pozitivna korena t1 i t2 (t1 > t2) za 0 6 k 6 2, i ima ta~no jedan pozitivan koren t1 za k > 3. Lako je proveriti da za 0 6 k 6 2 va`i slede}a nejednakost (4.14) t2 < (k + 1) √ k2 + 8k + 11. Neka je daqe n0 = k 2 + 4k + 6 + ⌊t1⌋. Lema 32. Neka su D1 i G0 grafovi reda n i veli~ine n + k (k > 0, n > k + 4) sa slika 3.3 i 4.9, respektivno. (i) Ako je n 6 n0, tada je λ(D1) < λ(G0). (ii) Ako je n > n0, tada je λ(G0) < λ(D1). Dokaz. Karakteristi~ni polinomi grafovaD1 i G0 su φ(D1, λ) = λ n−4(λ4 − (n+ k)λ2 + (k + 2)(n− k − 4)), φ(G0, λ) = λ n−4(λ4 − (n+ k)λ2 − 2(k + 1)λ+ (k + 1)(n− k − 3)). Razlika ovih polinoma je φ(G0, λ)− φ(D1, λ) = λn−4f(λ), gde f(λ) = −2(k + 1)λ+ 2k + 5− n. Lako je videti da je najmawa karakteristi~na vrednost grafaD1 λ(D1) = λ0 = − √ n+ k + √ (n− (k + 4))2 + 4(k + 2)2 2 i da je f(λ0) = 2k + 5− n+ √ 2(k + 1) √ n+ k + √ (n− (k + 4))2 + 4(k + 2)2. Razmotrimo slede}e dve mogu}nosti. 53 4.3. TRICIKLI^NI, TETRACIKLI^NII PENTACIKLI^NI GRAFOVI FIKSIRANOG REDA 1◦ f(λ0) > 0 Za λ < λ0 i parno n va`i φ(G0, λ)− φ(D1, λ) = λn−4f(λ) > λn−4f(λ0) > 0, odnosno (4.15) φ(G0, λ) > φ(D1, λ). Ako je, pak, λ < λ0 i n neparno, tada je φ(G0, λ)− φ(D1, λ) = λn−4f(λ) < λn−4f(λ0) < 0, odnosno (4.16) φ(G0, λ) < φ(D1, λ). Na osnovu nejednakosti (4.15) i (4.16) zakqu~ujemo da je λ(D1) < λ(G0). 2◦ f(λ0) < 0 Posmatrajmo razliku φ(G0, λ0) − φ(D1, λ0) = λn−40 f(λ0). Vidimo da je φ(G0, λ0) < 0 za parno n, i φ(G0, λ0) > 0 za neparno n. U svakom slu~aju, zakqu~ujemo da je λ(G0) < λ(D1). Ispitajmo sada za koje vrednosti prirodnog broja n je f(λ0) > 0, a za koje vrednosti je f(λ0) < 0. Nejednakost f(λ0) > 0 mo`e se napisati u obliku (4.17) √ 2(k + 1) √ n + k + √ (n− (k + 4))2 + 4(k + 2)2 > n− 2k − 5. Ova nejednakost o~igledno va`i za k + 4 < n 6 2k + 5. Neka je daqe n > 2k + 5. Nakon kvadrirawa i sre|ivawa izraza (4.17) dobijamo ekviva- lentnu nejednakost 2(k+1)2 √ (n− (k + 4))2 + 4(k + 2)2 > (n−(k2+4k+6))2−(k+1)2(k2+8k+11). O~igledno, posmatrana nejednakost je ta~na za 2k + 5 < n 6 k2 + 4k + 6 + (k + 1) √ k2 + 8k + 11. Zbog toga pretpostavimo da je n > k2 + 4k + 6 + (k + 1) √ k2 + 8k + 11. Nakon kvadrirawa i sre|ivawa dobija se ekvivalentna nejednakost (4.18) Q(t) < 0, gde je t = n− (k2 + 4k + 6). Koriste}i nejednakost (4.14) i rela iju t > (k + 1) √ k2 + 8k + 11 > 0 54 4.3. TRICIKLI^NI, TETRACIKLI^NII PENTACIKLI^NI GRAFOVI FIKSIRANOG REDA zakqu~ujemo da je nejednakost (4.18) zadovoqena za k2 + 4k + 6 + (k + 1) √ k2 + 8k + 11 < n 6 n0. Prema tome, za k + 4 < n 6 n0 dobijamo da je f(λ0) > 0, pa je u ovom slu~aju λ(D1) < λ(G0). Posledwa nejednakost upotpuwuje dokaz teoreme. Koriste}i softver Mathematica 7 dobijamo najve}i koren t1 polinoma Q(t) za 0 6 k 6 4. Slede}a tabela sadr`i dobijene vrednosti parametara t1 i n0 = k 2 + 4k + 6 + ⌊t1⌋ za 0 6 k 6 4. k t1 n0 0 5.25 11 1 16.26 27 2 33.26 51 3 56.26 83 4 85.26 123 Tabela 4.1. Vrednosti parametara t1 i n0 za 0 6 k 6 4 Imaju}i na umu teoreme 1, 5 i 13 i lemu 32, najva`niji rezultat ovog poglavqa se mo`e sumirati u vidu slede}e teoreme. Teorema 14. Postoji jedinstveni graf G sa minimalnom najmawom karak- teristi~nom vredno{}u u klasi povezanih grafova reda n i veli~ine n + k (0 6 k 6 4, n > k + 4). Neka je n0 = k 2 + 4k + 6 + ⌊t1⌋, gde je t1 najve}i koren polinoma Q(t) za 0 6 k 6 4 (tabela 4.1). Tada je G ∼= D1 za n 6 n0 i G ∼= G0 za n > n0. Znamo da dobijeni ekstremalni graf G0, reda n i veli~ine n + k, pred- stavqa kompletan proizvod dva stepenasta grafa, tj. G0 = K1∇(K1,k+1 ∪ (n− k − 3)K1). Interesantno je, me|utim, da je i sam graf G0 stepenasti graf. Ovaj graf se dobija iz zvezde S1,n−1 i to dodavawem jo{ k + 1 grana na wu, koje i same indukuju zvezdu nad skupom vise}ih ~vorova u S1,n−1. 55 Glava 5 Ekstremalni kaktusi Za povezani graf ka`emo da je kaktus (engl. cactus) ako svake dve konture u wemu imaju najvi{e jedan zajedni~ki ~vor. Stabla i uni ikli~ni gra- fovi, o~igledno, pripadaju ovoj klasi. U klasi kaktusa prou~avano je vi{e spektralnih invarijanti. Petrovi} i Borovi}anin [6] su odredili kaktus sa najve}im spektralnim radijusom me|u kaktusima fiksiranog reda. Liu i Lu [27] su pokazali da taj kaktus ima istu ili sli~nu strukturu kao kaktusi koji su ekstremalni u smisluWienerovog indeksa,Merrifield-Simmonsovog indeksa iHosoyainog indeksa, u istoj klasi grafova. Wu, Deng iQin [45] su prou~avali spektralni radijus kaktusa sa k vise}ih ~vorova. Izu~avani su i spektralni radijus kaktusa sa savr{enim sparivawem, te`inskih kaktusa, zatim kaktusi sa odre|enim spektralnim osobinama, itd. (videti [22, 34]). Minimalna najmawa sopstvena vrednost i raspon kaktusa, me|utim, nisu izu~avani ranije pa }e u ovom poglavqu pa`wa biti posve}ena ovim dvema spektralnim invarijantama. Pre iznije, tema ovog poglavqa su kaktusi koji su ekstremalni u smislu minimalne najmawe karakteristi~ne vredno- sti, maksimalnog indeksa i maksimalnog raspona. Predstavqen je graf koji ima minimalnu najmawu karakteristi~nu vrednost me|u svim kaktu- sima sa n ~vorova i k kontura (k > 1). Tako|e, u istoj klasi opisana je i struktura kaktusa ~iji je indeks maksimalan, kao i kaktusa ~iji je raspon maksimalan. Dokazano je da su ovi grafovi jedinstveni. Interesantno je da ve}ina osobina koje se ti~u strukture kaktusa sa minimalnom najmawom karakteristi~nom vredno{}u va`i i za kaktus maksimalnog raspona. Poglavqe je zavr{eno sek ijom o kaktusimafiksiranog reda koji sadr`e konture. U ovoj klasi dobijen je jedinstven graf sa maksimalnim indeksom i jedinstven graf sa minimalnom najmawom karakteristi~nom vredno{}u. 56 5.1. EKSTREMALNI GRAFOVI U KLASI KAKTUSA SA FIKSIRANIM BROJEM ^VOROVA I FIKSIRANIM BROJEM KONTURA 5.1 Ekstremalni grafovi u klasi kaktusa sa fiksiranim brojem ~vorova i fiksiranim brojem kontura Neka je sa C(n, k) ozna~en skup svih kaktusa sa n ~vorova i k kontura. Ako sve konture u kaktusu G imaju ta~no jedan zajedni~ki ~vor, re imo v0, onda ka`emo da one formiraju sve`aw (engl. bundle). U tom slu~aju ~vor v0 se naziva entralni ~vor sve`wa. Sa B(n, k) ozna~imo skup svih sve`weva sa n ~vorova i k kontura. Neka je G(C1, . . . , Ck; r) (k > 1, r > 0) graf prikazan na sli i 5.1, a S(n, k) skup svih sve`weva oblika G(C1, . . . , Ck; r) iz B(n, k). PSfrag repla ements v0 r k C1 Ck Slika 5.1. Sve`aw G(C1, . . . , Ck; r) Neka je saB∗(n, k) ozna~en skup svih sve`weva iz skupaS(n, k) kod kojih je du`ina najdu`e konture mawa ili jednaka od 4. Tako|e, neka je t maksimalan broj kontura du`ine 4 u takvim grafovima. Pretpostavimo da u sve`wu sa n ~vorova imamo k − s kontura du`ine 3 i s kontura du`ine 4. Tada je n > 3s+2(k− s) + 1, odakle je s 6 n− 2k− 1. Po{to posmatramo sve`weve sa k kontura o~igledno je t = min{k, n− (2k + 1)}. Ozna~imo sa Bk,s = B(k − s, s, n − (2k + s + 1)) (s = 0, 1, . . . , t) sve`aw iz skupa B∗(n, k) koji sadr`i k − s kontura du`ine 3, s kontura du`ine 4 i n− (2k + s+ 1) ~vorova stepena 1 prika~enih za ~vor v0 (slika 5.2). Tada je B∗(n, k) = {Bk,0, . . . , Bk,t}. Neka je c(G) du`ina najdu`e konture grafa G. Veli~inu c(G) nazivamo obimom (engl. circumference) grafa G. Lema 33. Neka jeB sve`aw oblikaG(C1, . . . , Ck; r) (k > 1, r > 0) prikazan na sli i 5.1, ~iji je obim c(B) > 5. Tada je λ(B) > −2 ako i samo ako je B = Cn ili B = C5 · S1,1 ili B = C7 · S1,1 ili B = C3 · C5. 57 5.1. EKSTREMALNI GRAFOVI U KLASI KAKTUSA SA FIKSIRANIM BROJEM ^VOROVA I FIKSIRANIM BROJEM KONTURA PSfrag repla ements v0 n− (2k + s+ 1) k − s s Slika 5.2. Sve`aw Bk,s Dokaz. Kori{}ewemsoftveraNewGraphdobijamoda jeλ(C5·S1,1) = −1.8608, λ(C7 · S1,1) = −1.9738 i λ(C3 · C5) = −1.9354. Ako je B = Cn ili B = C5 · S1,1 ili B = C7 · S1,1 ili B = C3 · C5, o~igledno je λ(B) > −2. PSfrag repla ements G3G2G1 Slika 5.3. Grafovi G1, G2 i G3 Neka je u nastavku B sve`aw oblika G(C1, . . . , Ck; r) (k > 1, r > 0) prikazan na sli i 5.1 ~iji je obim c(B) > 5 i neka je λ(B) > −2. Kako je λ(G1) = −2.0321, λ(G2) = −2.0743 i λ(G3) = −2.0153, onda na osnovu leme 5 zakqu~ujemo da grafB ne sadr`i kao indukovani podgraf nijedan od grafova G1, G2 i G3 sa slike 5.3. Razmotrimo slede}e mogu}nosti. 1◦ k = 1, r = 0 U ovom slu~aju je B = Cn i λ(B) = λ(Cn) > −2. 2◦ k = 1, r = 1 Tada je B = Cn−1 · S1,1. Za n > 10 stablo G3 sa slike 5.3 je indukovani podgraf grafa B, {to je nemogu}e. Kako je λ(C8 · S1,1) = −2.0839 < −2, λ(C7 · S1,1) = −1.9738 > −2, λ(C6 · S1,1) = −2.1010 < −2 i λ(C5 · S1,1) = −1.8608 > −2, zakqu~ujemo da je B = C5 · S1,1 ili B = C7 · S1,1. 58 5.1. EKSTREMALNI GRAFOVI U KLASI KAKTUSA SA FIKSIRANIM BROJEM ^VOROVA I FIKSIRANIM BROJEM KONTURA 3◦ k = 1, r > 2 U ovom slu~aju jeB = Cn−r ·S1,r i stabloG2 je indukovani podgraf grafa G, {to nije mogu}e. 4◦ k = 2, r = 0 Tada je B = Cp · Cn−p+1 (n − p + 1 > 5). Ako je p > 4, onda je stablo G2 indukovanipodgraf grafaB,{to je nemogu}e. Ako je pak p = 3 in−p+1 > 7, tada je G1 (slika 5.3) indukovani podgraf grafa B, {to je tako|e nemogu}e. Kako je λ(C3 ·C6) = −2.1466 < −2, a λ(C3 ·C5) = −1.9354 > −2, zakqu~ujemo da je B = C3 · C5. 5◦ k = 2, r > 0 ili k > 3 U ovom slu~aju je stablo G2 indukovani podgraf grafa B, {to nije mogu}e. Na osnovu 1◦, 2◦, 3◦, 4◦ i 5◦ zakqu~ujemo da je B = Cn ili B = C5 · S1,1 ili B = C7 · S1,1 ili B = C3 · C5. Lema 34. Neka je B sve`aw oblika G(C1, . . . , Ck; r) (k > 1, r > 0), prikazan na sli i 5.1. Ako je najmawa karakteristi~na vrednost λ(B) < −2, tada za svaki karakteristi~ni vektor X = (x0, x1, x2, . . . , xn−1) koji odgovara karakteristi~noj vrednosti λ(B) va`i xv0 = x0 6= 0. Tako|e, za svaku konturu C = v0v1 . . . vl−1v0 u grafu B ispuwene su slede}e rela ije, pri ~emu je s = ⌊ l 2 ⌋: xi = xl−i (i = 1, 2, . . . , l − 1),(5.1) |x0| > |x1| > · · · > |xs−1| > |xs| > 0,(5.2) xi−1xi < 0 (i = 1, . . . , s).(5.3) Dokaz. Neka je λ(B) < −2 i neka je X = (x0, x1, x2, . . . , xn−1) proizvoqan karakteristi~ni vektor sve`waB koji odgovara najmawoj karakteristi~noj vrednosti λ = λ(B). Tako|e, neka je C = v0v1 . . . vl−1v0 proizvoqna kontura u kaktusu B. Pretpostavimo obrnuto, da je xv0 = 0. Pomo}u (λ,X)karakteristi~nih jedna~ina (2.4) dobijamo da su vrednosti ~vorova stepena jedan, prika~enih za v0 i odre|ene sa X , jednake 0. Tako|e, dobijamo k sistema homogenih linearnih jedna~ina oblika λx1 = x2 λxi = xi−1 + xi+1 (i = 2, . . . , l − 2) λxl−1 = xl−2, sa determinantom 59 5.1. EKSTREMALNI GRAFOVI U KLASI KAKTUSA SA FIKSIRANIM BROJEM ^VOROVA I FIKSIRANIM BROJEM KONTURA (5.4) D = ∣∣∣∣∣∣∣∣∣∣∣ −λ 1 0 · · · 0 0 1 −λ 1 · · · 0 0 0 1 −λ · · · 0 0 . . . . . . . . . . . . . . . . . . 0 0 0 · · · 1 −λ ∣∣∣∣∣∣∣∣∣∣∣ = Φ(Pl−1, λ). Polinom Φ(Pl−1, λ) je karakteristi~ni polinom puta Pl−1 pa na osnovu leme 1 sledi da je D 6= 0 za λ < −2. Zato ovi sistemi imaju samo trivijalno re{ewe. Zbog toga jeX = 0, {to je nemogu}e. Doka`imo prvo osobinu (5.1). Primetimo da postoji automorfizam ϕ sve`wa B takav da za svaku konturu C = v0v1 . . . vl−1v0 va`i ϕ(vi) = vl−i (i = 1, . . . , l − 1) i ϕ(v) = v za ostale ~vorove sve`wa B. Defini{imo novi vektor Y = (y0, y1, y2, . . . , yn−1) tako da je yi = xϕ(vi) za svaki ~vor vi ∈ V (B). Vektor Y je karakteristi~ni vektor koji odgovara karakteristi~noj vred- nosti λ(B) i pri tome je Y = X iz slede}ih razloga. Dimenzija sopstvenog prostora karakteristi~ne vrednostiλ(B) je jednaka 1. U suprotnom, za λ(B) mo`emo definisati karakteristi~ni vektor Z za koji je Z(v0) = 0. Kako je jo{ ‖Y ‖ = ‖X‖ to imamo Y = ±X . Po{to je X(v0) = Y (v0) 6= 0 onda je o~igledno Y 6= −X . Dakle Y = X , pa na osnovu defini ije vektora Y zakqu~ujemo da su jednakosti (5.1) zadovoqene. Doka`imo sada nejednakosti (5.2) i (5.3). Koriste}i (λ,X)karakteri- sti~ne jedna~ine (2.4), za svaku konturu C = v0v1 . . . vl−1v0 u kaktusuB dobi- jamo λxs = 2xs−1, za parno l,(5.5) (λ− 1)xs = xs−1, za neparno l.(5.6) Ako je xs = 0, tada pomo}u (λ,X)karakteristi~nih jedna~ina mo`emo za- kqu~iti da je xi = 0 za svako i = 1, 2, . . . , l − 1 pa je o~igledno i x0 = 0, {to dovodi do kontradik ije. Tako|e, iz (5.5) i (5.6) vidimo da je |xs| < |xs−1|, kada je λ < −2. Da bismo dokazali (5.2) dovoqno je da doka`emo implika ije |xi+1| < |xi| ⇒ |xi| < |xi−1| (i = 1, . . . , s− 1). Pretpostavimo da je |xi+1| < |xi|. Iz jedna~ine λxi = xi−1 + xi+1, za λ < −2, dobijamo |xi−1| = |λxi − xi+1| > |λ||xi| − |xi+1| > |λ||xi| − |xi| = (|λ| − 1)|xi| > |xi|. Osobina (5.2) o~igledno va`i. Primetimo da iz nejednakosti (5.2) sledi |xi−1xi| = |xi−1||xi| > |xi||xi+1| = |xixi+1| (i = 1, . . . , s− 1) pa su izrazi xi−1xi+xixi+1 i xi−1xi su istog znaka. Koriste}i sada jedna~inu λxi = xi−1 + xi+1 dobijamo da je λx2i = xi−1xi + xixi+1 < 0. Zbog toga je xi−1xi < 0 za i = 1, . . . , s, tj. nejednakosti (5.3) su ispuwene. 60 5.1. EKSTREMALNI GRAFOVI U KLASI KAKTUSA SA FIKSIRANIM BROJEM ^VOROVA I FIKSIRANIM BROJEM KONTURA Lema 35. Za svaki graf G ∈ C(n, k)\S(n, k) postoji graf B ∈ S(n, k) takav da grafovi G i B imaju iste du`ine kontura i va`e nejednakosti: (i) λ(B) < λ(G), (ii) ρ(B) > ρ(G), (iii) s(B) > s(G). Dokaz. Neka je G kaktus iz skupa C(n, k)\S(n, k). Tada G sadr`i m artiku- la ionih ~vorova, pri ~emu jem > 2. (i) Neka su u i v dva artikula iona ~vora grafa G i neka je X karakteri- sti~ni vektor koji odgovara karakteristi~noj vrednosti λ(G). Pretposta- vimo da je |xu| > |xv|. Primetimo da seGmo`e posmatrati kao koales en ija dva podgrafa u ~voru v, tj. G = G1(v) · G2(v), gde u pripada V (G1) i v nije artikula ioni ~vor u grafu G1 (v je ili vise}i ~vor ili pripada nekoj konturi uG1). Neka je sadaG ∗ = G1(u) ·G2(v). Svakako,G∗ ∈ C(n, k) i graf G∗ sadr`i jedan artikula ioni ~vor mawe nego graf G. Na osnovu leme 4 imamo (5.7) λ(G∗) 6 λ(G). Kada opisani postupak i lemu 4 ponovimom− 1 puta, na svaki par artiku- la ionih ~vorova, na kraju dobijamo sve`aw B ∈ S(n, k) koji sadr`i ta~no jedan artikula ioni ~vor v0, takav da grafovi G i B imaju iste du`ine kontura. Ako je c(B) = 3, tada pomo}u (λ,X)-karakteristi~nih jedna~ina dobi- jamo λxv = xv0 , za svaki vise}i ~vor v i (λ− 1)xv = xv0 , za svaki ~vor v 6= v0 sa neke od kontura. Odatle zakqu~ujemo da je xv0 6= xv za svaki ~vor v (v 6= v0) sve`wa B. Neka je daqe c(B) > 3. S obzirom na to da je sve`awB dobijen iz grafaG sa m > 2 artikula ionih ~vorova, sledi da B sadr`i indukovani podgraf G(C1; 2), gde je kontura C1 du`ine ve}e od 3. Stoga, na osnovu leme 5 va`i λ(B) 6 λ(G(C1; 2)) < −2. I u ovom slu~aju, koriste}i lemu 34 i (λ,X) karakteristi~ne jedna~ine, dobijamo da je xv0 6= xv za svaki ~vor v (v 6= v0) sve`wa B. Prema tome, na osnovu leme 4 zakqu~ujemo da uvek va`i stroga nejednakost u rela iji (5.7) u posledwem koraku opisanog postupka. Zbog toga je λ(B) < λ(G). (ii) Fokusirajmo se sada na indeks kaktusa G. Neka je Y Peronov vektor grafa G i u i v dva artikula iona ~vora u G. Pretpostavimo da je yu > yv. Ponovo, posmatrajmoG kao koales en iju G = G1(v) ·G2(v), gde u ∈ V (G1) 61 5.1. EKSTREMALNI GRAFOVI U KLASI KAKTUSA SA FIKSIRANIM BROJEM ^VOROVA I FIKSIRANIM BROJEM KONTURA i v nije artikula ioni ~vor u grafu G1 (v je ili vise}i ~vor ili pripada nekoj konturi u G1) i neka je G ′ = G1(u) · G2(v). Vidimo da G′ ∈ C(n, k) i graf G′ sadr`i jedan artikula ioni ~vor mawe nego graf G. Na osnovu leme 3 dobijamo ρ(G′) > ρ(G). Kada ovaj postupak i lemu 3 ponovimo m − 1 puta, na svaki par artiku- la ionih ~vorova, dobi}emo sve`aw B ∈ S(n, k) koji sadr`i ta~no jedan artikula ioni ~vor v0, takav da grafovi G i B imaju iste du`ine kontura i za koji je ρ(B) > ρ(G). (iii) Primetimo da je u dokazima pod (i) i pod (ii) dobijen isti sve`aw B, pa je nejednakost s(B) > s(G) neposredna posledi a nejednakosti dobijenih pod (i) i (ii). Koriste}i prethodnu lemu mo`emo odrediti strukturu kaktusa koji ima maksimalni indeks u klasi C(n, k). Lema 36. Ako graf B∗ ima maksimalni indeks u skupu C(n, k) gde je k > 1 i n > 2k + 1, tada je c(B∗) = 3. Dokaz. Neka jeB∗ kaktus koji ima maksimalni indeks u skupu C(n, k) (k > 1, n > 2k+1). Na osnovu leme 35, bez gubitka op{tosti, mo`emopretpostaviti da B∗ ∈ S(n, k) (k > 1, r > 0). Pretpostavimo suprotno,tj. da je c(B∗) > 3. Tada u grafu B∗ postoji kontura Cp = v0v1 . . . vp−1v0 du`ine p > 3, gde je v0 entralni ~vor kaktusa B∗. Neka je B = B∗ − v1v2 + v0v2. Tada B ∈ S(n, k). Na osnovu lema 8 i 5 zakqu~ujemo da je ρ(B) > ρ(B∗), {to je u kontradik iji sa izborom grafa B∗. Posledi a 3. Graf Bk,0 = B(k, 0, n− (2k+1)) (slika 5.2) je graf sa najve}im indeksom u skupu svih povezanih kaktusa sa n ~vorova i k kontura (k > 1, n > 2k + 1). Isti rezultat dobili su i Borovi}anin i Petrovi} u radu [6], koriste}i druga~iju tehniku. U nastavku, odredi}emo kaktuse koji imaju minimalnu najmawu karakte- risti~nu vrednost i maksimalni raspon u skupu C(n, k). Lema 37. Neka jeC(n, k) skup svih povezanih kaktusa sa n ~vorova i k kontura pri ~emu je k > 1 i n > 2k + 1. (i) Ako grafB∗ ima minimalnu najmawu karakteristi~nu vrednost u skupu C(n, k), tada je c(B∗) 6 4. (ii) Ako graf B∗ ima maksimalni raspon u skupu C(n, k), tada je c(B∗) 6 4. Dokaz. Sa C(n, k) smo ozna~ili skup svih povezanih kaktusa sa n ~vorova i k kontura pri ~emu je k > 1 i n > 2k + 1. 62 5.1. EKSTREMALNI GRAFOVI U KLASI KAKTUSA SA FIKSIRANIM BROJEM ^VOROVA I FIKSIRANIM BROJEM KONTURA (i) Neka je B∗ kaktus koji ima minimalnu najmawu karakteristi~nu vred- nost u skupu C(n, k) (k > 1, n > 2k + 1). Na osnovu leme 35, mo`emo pretpostaviti da B∗ ∈ S(n, k) (k > 1, r > 0). Da bismo dokazali tvr|ewe pretpostavimo suprotno, da je c(B∗) > 5. Tada je n > 5. Dovoqno je da na|emo graf B ∈ B(n, k) za koji va`i λ(B) < λ(B∗). U skupu B∗(n, k) postoji sve`aw H takav da je graf B(0, 1, 1) induko- vani podgraf sve`wa H . Koriste}i lemu 5 i obzirom na to da kaktus B∗ ima minimalnu najmawu sopstvenu vrednost u skupu C(n, k), vidimo da va`i λ(B∗) 6 λ(H) 6 λ(B(0, 1, 1)) = −2.1358 < −2. Neka je X jedini~ni sop- stveni vektor koji odgovara sopstvenoj vrednosti λ(B∗). Na osnovu leme 34, osobine (5.1)  (5.3) su ispuwene za svaku konturu kaktusa B∗. Ozna~imo sada sa B graf dobijen preme{tawem jedne proizvoqne grane u grafu B∗. Tada iz (2.5) dobijamo λ(B)− λ(B∗) = min ||Y ||=1 Y TA(B)Y −XTA(B∗)X 6 XT (A(B)−A(B∗))X. (5.8) Neka je sa v0 ozna~en entralni ~vor grafaB ∗ i neka jeC = v0v1 . . . vl−1v0 proizvoqna kontura du`ine l > 5. U zavisnosti od du`ine konture C razlikujemo dva slu~aja. 1◦ l  neparan broj (l = 2s+ 1, s > 2) U ovom slu~aju, saB ozna~imo graf dobijen iz grafaB∗ rotirawem grane vsvs+1 oko ~vora vs+1 u pozi iju vs−1vs+1 gde prethodno nije bilo grane. Tada B ∈ B(n, k). Na osnovu nejednakosti (5.8) i leme 34 imamo λ(B)− λ(B∗) 6 XT (A(B)− A(B∗))X = 2(xs−1xs+1 − xsxs+1) = 2(xs−1xs − x2s) < 0, tj. λ(B) < λ(B∗). 2◦ l  paran broj (l = 2s, s > 3) Ovde, sa B ozna~imo graf dobijen iz grafa B∗ pomerawem grane vs−1vs u pozi iju vs−2vs+1 gde prethodno nije bilo grane. Ponovo va`i B ∈ B(n, k). Na osnovu jednakosti (5.8) i leme 34 dobijamo λ(B)− λ(B∗) 6 XT (A(B)− A(B∗))X = 2(xs−2xs+1 − xs−1xs) = 2xs−1(xs−2 − xs) < 0, odnosno λ(B) < λ(B∗). 63 5.1. EKSTREMALNI GRAFOVI U KLASI KAKTUSA SA FIKSIRANIM BROJEM ^VOROVA I FIKSIRANIM BROJEM KONTURA (ii) Neka je B∗ kaktus koji ima maksimalni raspon u skupu C(n, k) (k > 1, n > 2k + 1). Na osnovu leme 35 mo`emo pretpostaviti da B∗ ∈ S(n, k) (k > 1, r > 0). Da bismo dokazali tvr|ewe pretpostavimo suprotno, tj. da je c(B∗) > 5. Tada je n > 5. Sli~no kao u dokazu pod (i), dovoqno je da na|emo graf B ∈ B(n, k) za koji va`i s(B) > s(B∗). Razlikova}emo slede}a dva slu~aja. 1◦ λ(B∗) > −2 Naosnovu leme 33 vidimo da jeB∗ = Cn iliB∗ = C5·S1,1 iliB∗ = C7·S1,1 ili B∗ = C3 · C5. Ako je B∗ = Cn, tada je B = C4 · S1,n−4 i va`i s(B∗) 6 4 < 4.2716 = s(C4 · S1,1) 6 s(B). Ako je B∗ = C5 · S1,1, tada je B = C4 · S1,2 i s(B∗) = 3.9757 < 4.5765 = s(B). Ako je B∗ = C7 · S1,1, tada je B = C4 · S1,3 i s(B∗) = 4.0650 < 4.8989 = s(B). Ako je B∗ = C3 · C5, tada je B = C4 · S1,3 i s(B∗) = 4.4083 < 4.8989 = s(B). 2◦ λ(B∗) < −2 Na isti na~in kao u slu~aju (i) (1◦ i 2◦) konstrui{emo graf B za koji je λ(B) < λ(B∗). Kako na osnovu lema 8 i 5 va`i ρ(B) > ρ(B∗), zakqu~ujemo da je s(B) > s(B∗), {to je nemogu}e. U skladu sa uvedenim oznakama, kori{}ewem prethodne leme, dolazimo do slede}ih zakqu~aka. Posledi a 4. Ako je B∗ graf koji ima minimalnu najmawu karakteristi~nu vrednost u skupu C(n, k) (k > 1, n > 2k + 1), onda B∗ ∈ B∗(n, k). Posledi a 5. Ako je B∗ graf koji ima maksimalan raspon u skupu C(n, k) (k > 1, n > 2k + 1), onda B∗ ∈ B∗(n, k). U nastavku }emo odrediti graf sa minimalnom najmawom karakteri- sti~nom vredno{}u u klasi C(n, k) kaktusa sa n ~vorova i k kontura. U vezi sa ovim rezultatom, u tabeli 5.1 na kraju sek ije 5.1, prikazana je lista svih sve`weva iz skupa B∗(n, k) (3 6 n 6 14, 1 6 k 6 1 2 (n− 1)) i wihove najmawe karakteristi~ne vrednosti. 64 5.1. EKSTREMALNI GRAFOVI U KLASI KAKTUSA SA FIKSIRANIM BROJEM ^VOROVA I FIKSIRANIM BROJEM KONTURA Teorema 15. Neka je B∗ kaktus koji ima minimalnu najmawu sopstvenu vred- nost u skupu C(n, k) (k > 1, n > 2k + 1) i neka je t = min{k, n − (2k + 1)}. Tako|e, neka je n0(k) = 12 za 1 6 k 6 2, n0(k) = 13 za 3 6 k 6 4 i n0(k) = 14 za 5 6 k 6 6. (i) Ako je k 6 6 i n < n0(k), tada je B ∗ = B(k − t, t, n− (2k + t+ 1)). (ii) Ako je k 6 6 i n > n0(k) ili k > 7, tada je B ∗ = B(k, 0, n− (2k + 1)). Dokaz. Ozna~imo saB∗ kaktus kojiimaminimalnunajmawukarakteristi~nu vrednost u skupu C(n, k) (k > 1, n > 2k + 1). Na osnovu posledi e 4 vidimo da B∗ ∈ B∗(n, k). Ukoliko je n 6 7, rezultati slede iz tabele 5.1. Pretpostavimo da je u nastavku n > 7. Ako je n = 2k + 1, tada je t = 0 i u tom slu~aju je B∗(2k+ 1, k) = {Bk,0}, pa rezultat direktno sledi. Neka je daqe n > 2k+ 1. Tada je t > 1 iB∗(n, k) = {Bk,0, . . . , Bk,t}. Primenom leme 6 na ~vor v0 grafa Bk,s dobijamo karakteristi~ni polinom (5.9) Φ(Bk,s, λ) = λ n−2k−2(λ− 1)k−s−1(λ+ 1)k−s(λ2 − 2)s−1Q(k, s, λ), gde je Q(k, s, λ) = λ5 − λ4 − (n− s+ 1)λ3 + (n− 2k + s+ 1)λ2 + (2n− 6s− 2)λ− 2(n− 2k − s− 1).(5.10) Primetimo da za n > 7 va`i Q(k, s,−2) = 2(2n− 15) + 2(n− 2k) + 10s > 0. Sa druge strane, po{to je Q(k, s, λ) polinom neparnog stepena onda je (5.11) lim λ→−∞ Q(k, s, λ) = −∞. Zakqu~ujemo da je najmawi koren polinoma Q(k, s, λ) mawi od −2. Tako|e, najmawa karakteristi~na vrednost grafa Bk,s jednaka je najmawem korenu polinoma Q(k, s, λ). Razlika polinomaQ(k, s+1, λ) i Q(k, s, λ) ne zavisi od vrednosti para- metra s, tj. (5.12) Q(k, s+ 1, λ)−Q(k, s, λ) = λ3 + λ2 − 6λ+ 2. Ozna~imo ovu razliku sa f(λ) = λ3 + λ2 − 6λ + 2. Koriste}i softver Mathematica 7 dobijamo da polinom f(λ) ima ta~no jedan negativan koren λ0 = −3.1249. Po{to je funk ija f neparnog stepena izvodimo slede}e zakqu~ke. Ako je λ < λ0, onda je f(λ) < 0 i va`i (5.13) Q(k, s+ 1, λ) < Q(k, s, λ). 65 5.1. EKSTREMALNI GRAFOVI U KLASI KAKTUSA SA FIKSIRANIM BROJEM ^VOROVA I FIKSIRANIM BROJEM KONTURA Analogno, za λ0 < λ < −2 va`i da je f(λ) > 0 pa je (5.14) Q(k, s+ 1, λ) > Q(k, s, λ). Tako|e, na osnovu (5.12) ispuwene su jednakosti Q(k, 0, λ0) = Q(k, 1, λ0) = · · · = Q(k, t, λ0). Iz (5.11) vidimo da ukoliko je Q(k, 0, λ0) > 0, onda je najmawi koren poli- noma Q(k, s, λ) mawi od λ0. U suprotnom, najmawi koren ovog polinoma je ve}i od λ0. Iz nejednakosti (5.13) zakqu~ujemo da za Q(k, 0, λ0) > 0 i λ < λ0 va`e nejednakosti Q(k, 0, λ) > Q(k, 1, λ) > · · · > Q(k, t, λ), odakle je (5.15) λ(Bk,0) < λ(Bk,1) < · · · < λ(Bk,t) < λ0. Sli~no, ako je Q(k, 0, λ0) < 0, na osnovu (5.14) za λ0 < λ < −2 va`e nejedna- kosti Q(k, 0, λ) < Q(k, 1, λ) < · · · < Q(k, t, λ), odnosno (5.16) λ(Bk,0) > λ(Bk,1) > · · · > λ(Bk,t) > λ0. Da bismo odredili tra`eni graf ostaje jo{ da pro enimo znak izraza Q(k, 0, λ0). Iz (5.10) dobijamo da je (5.17) Q(k, 0, λ0) = 32.0295n− 15.5299k − 344.7960. Imaju}i na umu da je k broj kontura u grafu Bk,0, primetimo da za broj ~vorova ovog grafa mora va`iti n > 2k + 1. Na osnovu (5.17) zakqu~ujemo da je Q(k, 0, λ0) > 0 ako i samo ako je 1◦ 1 6 k 6 2, n > 12; 2◦ 3 6 k 6 4, n > 13; 3◦ 5 6 k 6 6, n > 14; 4◦ k > 7, n > 2k + 1. U kombina iji sa nejednakostima (5.15) i (5.16) ovaj rezultat kompletira dokaz teoreme. Kori{}ewem prethodnih rezultata jednostavno se dokazuje da u skupu C(n, k) (k > 1, n > 2k+1) najve}i rasponima grafBk,0 = B(k, 0, n−(2k+1)), osim u kona~no mnogo slu~ajeva. 66 5.2. EKSTREMALNI GRAFOVI U KLASI KAKTUSA SA FIKSIRANIM BROJEM ^VOROVA Teorema 16. Neka graf G ima najve}i raspon u klasi kaktusa sa n ~vorova i k kontura (k > 1, n > 2k + 1) i neka je t = min{k, n − (2k + 1)}. Tada je G ∼= B(k − t, t, n− (2k + t + 1)) ako je n ∈ {4, 5} i k = 1, ili n = 6 i k = 2, a G ∼= B(k, 0, n− (2k + 1)) u svim ostalim slu~ajevima. Dokaz. Neka je n0(k) = 12 za 1 6 k 6 2, n0(k) = 13 za 3 6 k 6 4 i n0(k) = 14 za 5 6 k 6 6. Na osnovu teoreme 15 i posledi e 3 zakqu~ujemo da jeG ∼= Bk,0 ako je k 6 6 i n > n0(k) ili k > 7. U preostalim slu~ajevima, na osnovu posledi e 5, zakqu~ujemo da za kak- tuse maksimalnog raspona u posmatranoj klasi u obzir dolaze samo kaktusi Bk,s iz skupa B ∗(n, k). Analizom rezultata iz tabele 5.1 pokazuje se da je tvr|ewe teoreme ta~no za sve vrednosti n i k. 5.2 Ekstremalni grafovi u klasi kaktusa sa fiksiranim brojem ~vorova Neka je sa C(n) ozna~en skup svih kaktusa reda n koji sadr`e konture. Imaju}i na umu teoremu 15, u ovoj klasi je mogu}e odrediti graf sa maksi- malnim indeksom, kao i graf sa minimalnom najmawom karakteristi~nom vredno{}u. Teorema 17. Neka jeB∗ graf koji ima maksimalni indeks u skupu C(n) (n > 3). Tada je B∗ = B(m, 0, 0) ako je n = 2m+ 1 i B∗ = B(m, 0, 1) ako je n = 2m+ 2 (m ∈ N). Dokaz. Ozna~imo sa B∗ graf koji ima maksimalni indeks u skupu svih kak- tusa reda n (n > 3). Tada je n = 2m+1 ili n = 2m+2 (m ∈ N), a maksimalan broj kontura grafova skupa C(n) iznosi ⌊1 2 (n− 1)⌋ = m. Zbog toga je C(n) = m⋃ k=1 C(n, k). Na osnovu posledi e 3 zakqu~ujemo da za graf B∗ va`i B∗ ∈ {B1,0, B2,0, . . . , Bm,0}. Primetimo da graf Bk,0 (1 6 k 6 m) sadr`i konturu C3 kao indukovani podgraf, pa je ρ(Bk,0) > ρ(C3) = 2, na osnovu leme 5. Koriste}i jednakosti (5.9) i (5.10) zakqu~ujemo da karakteristi~ni po- linom grafa Bk,0 glasi φ(Bk,0, λ) = λ n−2k−2(λ− 1)k−1(λ+ 1)k(λ2 − 2)−1Q(k, 0, λ), 67 5.2. EKSTREMALNI GRAFOVI U KLASI KAKTUSA SA FIKSIRANIM BROJEM ^VOROVA gde je Q(k, 0, λ) = λ5 − λ4 − (n+ 1)λ3 + (n− 2k + 1)λ2 + (2n− 2)λ− 2(n− 2k − 1).(5.18) Vidimo da je indeks ρ(Bk,0) najve}a nula polinomaQ(k, 0, λ). Iz jednakosti (5.18) dobijamo da za λ > 1.4142 va`i Q(k, 0, λ)−Q(k + 1, 0, λ) = 2(λ2 − 2) > 0, odnosno, (5.19) Q(1, 0, λ) > Q(2, 0, λ) > · · · > Q(m, 0, λ). Koriste}i nejednakosti (5.19) zakqu~ujemo da je ρ(B1,0) < ρ(B2,0) < · · · < ρ(Bm,0). O~igledno, u klasi C(n) maksimalni indeks ima graf Bm,0 = B(m, 0, 0) ako je n = 2m+ 1, odnosno Bm,0 = B(m, 0, 1) ako je n = 2m+ 2. Prethodni rezultat dokazali su i Borovi}anin i Petrovi} u radu [6], koriste}i druga~iju tehniku. Poglavqe 5 zakqu~ujemo rezultatomo grafu koji imaminimalnu najmawu karakteristi~nu vrednost u klasi C(n). Teorema 18. Neka jeB∗ graf koji ima minimalnu najmawu sopstvenu vrednost u skupu C(n) (n > 3). (i) Ako je n = 3 ili n > 12, tada je B∗ = B(1, 0, n− 3). (ii) Ako je 4 6 n 6 6 ili 8 6 n 6 11, tada je B∗ = B(0, 1, n− 4). (iii) Ako je n = 7, tada je B∗ = B(0, 1, 3) ili B∗ = B(0, 2, 0). Dokaz. Ozna~imo sa B∗ graf ~ija je najmawa karakteristi~na vrednost mi- nimalna u skupuC(n) (n > 3). Tako|e, neka jem = ⌊1 2 (n−1)⌋ i l = ⌊1 3 (n−1)⌋. Kako je C(n) = m⋃ k=1 C(n, k), imaju}i u vidu posledi u 4, mo`emo pretpostaviti da va`i B∗ ∈ m⋃ k=1 B∗(n, k). Ako je n 6 7, rezultat sledi iz tabele 5.1. Neka je u nastavku n > 8. Tada, u skupu B∗(n, k) postoji sve`aw B takav da je graf B(0, 2, 1) indukovani podgraf grafa B. Na osnovu leme 5 i s obzirom na to da kaktus B∗ ima 68 5.2. EKSTREMALNI GRAFOVI U KLASI KAKTUSA SA FIKSIRANIM BROJEM ^VOROVA minimalnu najmawu karakteristi~nu vrednost u skupuC(n), zakqu~ujemo da λ(B∗) 6 λ(B) 6 λ(B(0, 2, 1)) = −2.5887. Daqe sprovodimo ideju prikazanu u vidu dijagrama 1 na sli i 5.4. Prvo }emo uporediti najmawe karakteristi~ne vrednosti grafova iz prve kolone. Zatim, da bismo dokazali teoremu, uporedi}emo i najmawe karakteristi~ne vrednosti grafova koji se nalaze na istoj dijagonali na dijagramu 1 i do- kazati da se ekstremalni grafovi ovih dijagonala nalaze u prvoj vrsti ili prvoj koloni dijagrama. PSfrag repla ements B1,0 B2,0 B2,1 B2,2 B3,0 B3,1 B3,2 B3,3 B4,1 B4,2 B4,3B4,0 B4,4 B1,1 Slika 5.4. Dijagram 1 Dakle, koriste}i polinom (5.18) dobijamo da za λ < −1.4142 va`i Q(k, 0, λ)−Q(k + 1, 0, λ) = 2(λ2 − 2) > 0, odakle sledi da je (5.20) λ(B1,0) < λ(B2,0) < · · · < λ(Bm,0). Sli~no, koriste}i polinom (5.10) dobijamo da je za λ < −2.4495 ispuweno Q(k, s, λ)−Q(k + 1, s+ 1, λ) = (λ− 1)(6− λ2) > 0. Ako je 2 6 k 6 l, tada je t = k i za λ < −2.4495 va`i Q(k, k, λ) < Q(k − 1, k − 1, λ) < · · · < Q(1, 1, λ). Otuda, (5.21) λ(Bk,k) > λ(Bk−1,k−1) > · · · > λ(B1,1). Istom argumenta ijom, i na osnovu (5.20), dolazimo do zakqu~ka da za k > l i t > 0 va`e nejednakosti (5.22) λ(Bk,t) > λ(Bk−1,t−1) > · · · > λ(Bk−t,0) > λ(B1,0). Iz rela ija (5.21) i (5.22) zakqu~ujemo da B∗ ∈ B∗(n, 1). Koriste}i ovaj rezultat i teoremu 15 za k = 1, dobijamo grafove koji su, u zavisnosti od vrednosti broja n, ekstremalni u smislu indeksa u skupu C(n). 69 5.2. EKSTREMALNI GRAFOVI U KLASI KAKTUSA SA FIKSIRANIM BROJEM ^VOROVA Na kraju poglavqa navodimo najmawe sopstvene vrednosti, indekse i raspone svih sve`weva Bk,s ∈ B∗(n, k) (slika 5.2) za 3 6 n 6 14, koji su kori{}eni u dokazima prethodnih teorema. Prikazani rezultati su dobijeni pomo}u softvera NewGraph. n k Graf Najmawa sopstvena Indeks Raspon vrednost grafa grafa grafa 3 1 B(1, 0, 0) −1.0000 2.0000 3.0000 4 1 B(1, 0, 1) −1.4812 2.1701 3.6513 B(0, 1, 0) −2.0000 2.0000 4.0000 5 1 B(1, 0, 2) −1.8136 2.3429 4.1565 B(0, 1, 1) −2.1358 2.1359 4.2717 2 B(2, 0, 0) −1.5615 2.5615 4.1231 6 1 B(1, 0, 3) −2.0861 2.5141 4.6003 B(0, 1, 2) −2.2882 2.2882 4.5765 2 B(2, 0, 1) −1.9032 2.7093 4.6125 B(1, 1, 0) −2.1912 2.5035 4.6947 7 1 B(1, 0, 4) −2.3234 2.6813 5.0047 B(0, 1, 3) −2.4495 2.4495 4.8990 2 B(2, 0, 2) −2.1774 2.8558 5.0332 B(1, 1, 1) −2.3527 2.6480 5.0006 B(0, 2, 0) −2.4495 2.4495 4.8990 3 B(3, 0, 0) −2.0000 3.0000 5.0000 8 1 B(1, 0, 5) −2.5366 2.8434 5.3800 B(0, 1, 4) −2.6131 2.6131 5.2263 2 B(2, 0, 3) −2.4142 3.0000 5.4142 B(1, 1, 2) −2.5201 2.7936 5.3137 B(0, 2, 1) −2.5887 2.5887 5.1775 3 B(3, 0, 1) −2.2731 3.1326 5.4057 B(2, 1, 0) −2.4219 2.9427 5.3647 9 1 B(1, 0, 6) −2.7320 3.0000 5.7320 B(0, 1, 5) −2.7752 2.7752 5.5503 2 B(2, 0, 4) −2.6262 3.1413 5.7675 B(1, 1, 3) −2.6876 2.9385 5.6261 B(0, 2, 2) −2.7320 2.7320 5.4641 3 B(3, 0, 2) −2.5079 3.2635 5.7714 B(2, 1, 1) −2.5947 3.0761 5.6708 B(1, 2, 0) −2.6533 2.8854 5.5387 4 B(4, 0, 0) −2.3723 3.3723 5.7446 10 1 B(1, 0, 7) −2.9136 3.1511 6.0647 B(0, 1, 6) −2.9335 2.9335 5.8670 70 5.2. EKSTREMALNI GRAFOVI U KLASI KAKTUSA SA FIKSIRANIM BROJEM ^VOROVA n k Graf Najmawa sopstvena Indeks Raspon vrednost grafa grafa grafa 10 2 B(2, 0, 5) −2.8201 3.2790 6.099 B(1, 1, 4) −2.8518 3.0813 5.9332 B(0, 2, 3) −2.8766 2.8766 5.7532 3 B(3, 0, 3) −2.7177 3.3923 6.1101 B(2, 1, 2) −2.7652 3.2084 5.9735 B(1, 2, 1) −2.8005 3.0191 5.8196 B(0, 3, 0) −2.8284 2.8284 5.6569 4 B(4, 0, 1) −2.6039 3.4940 6.0978 B(3, 1, 0) −2.6728 3.3209 5.9937 11 1 B(1, 0, 8) −3.0839 3.2971 6.3810 B(0, 1, 7) −3.0872 3.0872 6.1745 2 B(2, 0, 6) −3.0000 3.4142 6.4142 B(1, 1, 5) −3.0112 3.2214 6.2327 B(0, 2, 4) −3.0204 3.0204 6.0409 3 B(3, 0, 4) −2.9095 3.5188 6.4283 B(2, 1, 3) −2.9308 3.3388 6.2696 B(1, 2, 2) −2.9478 3.1523 6.1001 B(0, 3, 1) −2.9618 2.9618 5.9235 4 B(4, 0, 2) −2.8108 3.6139 6.4247 B(3, 1, 1) −2.8453 3.4439 6.2893 B(2, 2, 0) −2.8718 3.2687 6.1405 5 B(5, 0, 0) −2.7016 3.7016 6.4031 12 1 B(1, 0, 9) −3.2448 3.4381 6.6829 B(0, 1, 8) −3.2361 3.2361 6.4721 2 B(2, 0, 7) −3.1687 3.5456 6.7143 B(1, 1, 6) −3.1652 3.3584 6.5237 B(0, 2, 5) −3.1623 3.1623 6.3246 3 B(3, 0, 5) −3.0874 3.6428 6.7302 B(2, 1, 4) −3.0906 3.4671 6.5577 B(1, 2, 3) −3.0933 3.2842 6.3775 B(0, 3, 2) −3.0956 3.0956 6.1911 4 B(4, 0, 3) −3.0000 3.7320 6.7320 B(3, 1, 2) −3.0117 3.5654 6.5771 B(2, 2, 1) −3.0212 3.3930 6.4142 B(1, 3, 0) −3.0292 3.2158 6.2449 5 B(5, 0, 1) −2.9050 3.8148 6.7198 B(4, 1, 0) −2.9278 3.6557 6.5835 13 1 B(1, 0, 10) −3.3978 3.5745 6.9723 B(0, 1, 9) −3.3800 3.3800 6.7600 71 5.2. EKSTREMALNI GRAFOVI U KLASI KAKTUSA SA FIKSIRANIM BROJEM ^VOROVA n k Graf Najmawa sopstvena Indeks Raspon vrednost grafa grafa grafa 13 2 B(2, 0, 8) −3.3280 3.6737 7.0017 B(1, 1, 7) −3.3139 3.4921 6.8060 B(0, 2, 6) −3.3014 3.3014 6.6027 3 B(3, 0, 6) −3.2542 3.7644 7.0185 B(2, 1, 5) −3.2445 3.5929 6.8374 B(1, 2, 4) −3.2361 3.4142 6.6503 B(0, 3, 3) −3.2287 3.2287 6.4574 4 B(4, 0, 4) −3.1755 3.8482 7.0238 B(3, 1, 3) −3.1714 3.6851 6.8565 B(2, 2, 2) −3.1679 3.5159 6.6839 B(1, 3, 1) −3.1649 3.3412 6.5061 B(0, 4, 0) −3.1623 3.1623 6.3246 5 B(5, 0, 2) −3.0912 3.9265 7.0177 B(4, 1, 1) −3.0942 3.7703 6.8645 B(3, 2, 0) −3.0967 3.6091 6.7057 6 B(6, 0, 0) −3.0000 4.0000 7.0000 14 1 B(1, 0, 11) −3.5440 3.7066 7.2506 B(0, 1, 10) −3.5193 3.5193 7.0385 2 B(2, 0, 9) −3.4795 3.7986 7.2781 B(1, 1, 8) −3.4573 3.6225 7.0798 B(0, 2, 7) −3.4373 3.4373 6.8746 3 B(3, 0, 7) −3.4117 3.8834 7.2951 B(2, 1, 6) −3.3926 3.7163 6.5561 B(1, 2, 5) −3.3756 3.5419 6.9175 B(0, 3, 4) −3.3603 3.3603 6.7206 4 B(4, 0, 5) −3.3402 3.9624 7.3026 B(3, 1, 4) −3.3248 3.8028 7.1277 B(2, 2, 3) −3.3113 3.6372 6.9485 B(1, 3, 2) −3.2993 3.4655 6.7648 B(0, 4, 1) −3.2886 3.2886 6.5773 5 B(5, 0, 3) −3.2642 4.0365 7.3007 B(4, 1, 2) −3.2535 3.8833 7.1368 B(3, 2, 1) −3.2442 3.7250 6.9692 B(2, 3, 0) −3.2361 3.5615 6.7976 6 B(6, 0, 1) −3.1830 4.1064 7.2894 B(5, 1, 0) −3.1781 3.9588 7.1369 Tabela 5.1. Najmawe sopstvene vrednosti, indeksi i rasponi sve`wevaBk,s za 3 6 n 6 14 i 1 6 k 6 1 2 (n− 1) 72 Glava 6 Grafovi sa malim brojem kontura i maksimalnim rasponom Raspon grafa G (engl. spread), kao {to je ve} pomenuto, defini{e se kao razlika najve}e i najmawe karakteristi~ne vrednosti grafa G, odnosno s(G) = ρ(G) − λ(G). Prvi rezultati u vezi ove spektralne invarijante pomiwu se jo{ 1983. godine. Naime, Petrovi} [30] odre|uje sve grafove ~iji raspon nije ve}i od 4. Posledwih godina, ispitivawe raspona grafa postaje sve prisutnija tema u spektralnoj teoriji grafova. Liu iHuo [26] kao i Gregory, Hershkowith i Kirkland [18] odre|uju neke gorwe i dowe grani e za raspon grafa, na primer s(G) 6 ρ(G) + √ 2m− ρ(G)2 6 2√m, gde je G graf fiksiranog reda i veli~ine m. Tako|e je dokazano da je put jedinstveni graf sa minimalnim rasponom me|u povezanim grafovima datog reda [18]. Grafovi sa maksimalnim rasponom, me|utim, jo{ uvek nisu poznati. Odre|ivawe takvih grafova,datog reda, je te`ak problem. Ukoliko se razmatrawe ovog problema suzi na neke klase grafova, problem postaje jednostavniji a tematika je i daqe interesantna. Ovaj problem je, na primer, mogu}e posmatrati u klasi povezanih grafova fiksiranog reda i veli~ine. O~igledno je da zvezda i put imaju maksimalni, odnosno minimalni raspon me|u svim stablima datog reda, respektivno. U vezi sa grafovima ~iji je raspon maksimalan Gregory, Hershkowith i Kirkland [18] iznose slede}u hipotezu. Hipoteza 1. Ako je G graf koji ima maksimalni raspon me|u svim grafovima sa n ~vorova im < ⌊n2 4 ⌋ grana, tada on mora biti bipartitan. Ve} u klasi uni ikli~nih grafova se, me|utim, pokazuje da navedena hipoteza ne va`i za svaki prirodan broj n. U ovom poglavqu, hipoteza 1 }e biti opovrgnuta i za neke druge klase grafova. Prikaza}emo grafove sa maksimalnim rasponom me|u grafovima fiksiranog reda sa malim brojem kontura. Kako je problem odre|ivawa 73 6. GRAFOVI SAMALIM BROJEM KONTURA I MAKSIMALNIM RASPONOM grafa sa maksimalnim rasponom u bliskoj vezi sa problemom odre|ivawa minimalne najmawe karakteristi~ne vrednosti u datoj klasi grafova, to }e rezultati dobijeni u poglavqima 4 i 5 biti od velike koristi. U glavi 4 (sek ija 4.3) dokazano je da je graf G0 (slika 4.9) ekstremalni graf u smislu minimalne najmawe karakteristi~ne vrednosti u klasi pove- zanih grafova reda n i veli~ine n + k (0 6 k 6 4, n > k + 4) za dovoqno veliko n (teorema 14). Brualdi i Solheid [7] tako|e dobijaju graf G0, ali bave}i se problemom grafova sa maksimalnim indeksom u klasi povezanih grafova sa n ~vorova i n + k grana. Oni su pokazali da je G0 jedinstveni graf sa maksimalnim indeksom za 0 6 k < 2, kao i za 3 6 k 6 5 i dovoqno veliko n. Cvetkovi} i Rowlinson [12] dopuwuju wihove rezultate dokazom da graf G0 ima mak- simalni indeks u klasi svih povezanih grafova reda n i veli~ine n + k za k > 3 i dovoqno veliko n. Teorema 19 ([7],[12]). Graf G0 (slika 4.9) je jedinstven graf sa maksimalnim indeksom u klasi povezanih grafova reda n i veli~ine n+ k (0 6 k 6 1). Graf G0 je tako|e jedinstveni graf sa maksimalnim indeksom u klasi povezanih grafova reda n i veli~ine n+ k (k > 3) za dovoqno veliko n. Kao neposredna posledi a teorema 14 i 19 dobija se graf sa maksimalnim rasponom u klasi povezanih grafova reda n i veli~inen+k za k ∈ {0, 1, 3, 4} i dovoqno veliko n. Teorema 20. Neka je G0 graf sa slike (slika 4.9). (i) Graf G0 je jedinstven graf sa maksimalnim rasponom u klasi povezanih uni ikli~nih grafova reda n za n > 11. (ii) GrafG0 je jedinstveni graf sa maksimalnim rasponom u klasi povezanih bi ikli~nih grafova reda n za n > 27. (iii) Postoji prirodan broj n0 > 83 takav da je graf G0 jedinstveni graf sa maksimalnim rasponom u klasi povezanih grafova reda n i veli~ine n + 3 za n > n0. (iv) Postoji prirodan broj n0 > 123 takav da je graf G0 jedinstveni graf sa maksimalnim rasponom u klasi povezanih grafova reda n i veli~ine n + 4 za n > n0. Ozna~imo saC(n, 1) skup svih kaktusa sa n ~vorova i ta~no jednom kontu- rom (videti glavu 5). Kako su povezani uni ikli~ni grafovi redan (n > 4) u stvari kaktusi sa ta~no jednom konturom, problem grafova sa maksimalnim rasponom u klasi povezanih uni ikli~nih grafova reda n je ekvivalentan problemu grafova sa maksimalnim rasponom u klasi C(n, 1) (n > 4). Ozna~imo sa U1 i U2 uni ikli~ne grafove prikazane na sli i 6.1. Pri- metimo da je U1 u stvari graf B1,1 = B(0, 1, n− 4) sa slike 5.2, a graf U2 je graf G0 sa slike 4.9 za k = 0, odnosno graf B1,0 = B(1, 0, n− 3) sa slike 5.2. 74 6. GRAFOVI SAMALIM BROJEM KONTURA I MAKSIMALNIM RASPONOM PSfrag repla ements n− 3 U1 v0v0 n− 4 U2 Slika 6.1. Uni ikli~ni grafovi U1 i U2 Slede}a teorema je deo jednog op{tijeg rezultata dobijenog u glavi 5 (teo- rema 16), a koji se odnosi na problem maksimalnog raspona u klasi kaktusa sa n ~vorova i k kontura. Teorema 21 ([16]). GrafU1 je jedinstven graf samaksimalnim rasponom u klasi povezanih uni ikli~nih grafova reda n za 4 6 n 6 5, a graf U2 jedinstven graf sa maksimalnim rasponom u istoj klasi za n > 6. Do ovog rezultata do{li su i Fan, Wang i Gao [16] koriste}i druga~iju tehniku. U nastavku }emo razmatrati problem grafova sa maksimalnim rasponom u klasi povezanih bi ikli~nih grafova reda n. Da bismo formulisali i dokazali glavnu teoremu, koristi}emo rezultate koje navodimo u slede}im lemama. PSfrag repla ements n− 4n− 4 B′4B4 v0v0 Slika 6.2. Grafovi B4 i B ′ 4 Lema 38. Neka su B4 i B ′ 4 grafovi reda n prikazani na sli i 6.2. Tada je λ(B4) = λ(B ′ 4) za n = 6, i λ(B4) < λ(B ′ 4) za n > 7. Dokaz. Primenom leme 6 dobijamo karakteristi~ne polinome φ(B4, λ) = λ n−4(λ4 − (n + 1)λ2 − 4λ+ 2n− 8),(6.1) φ(B′4, λ) = λ n−5(λ+ 1)(λ4 − λ3 − nλ2 + (n− 4)λ+ 2(n− 4)). Za n = 6 je λ(B4) = λ(B ′ 4) = −2. Ako je n > 7 grafovi B4 i B′4 sadr`e graf C3(v) · S1,3(v) kao indukovani podgraf, gde je v entralni ~vor zvezde S1,3. Odatle, na osnovu leme 5 sledi da je λ(B4) 6 λ(C3(v) · S1,3(v)) = −2.0861 i λ(B′4) 6 λ(C3(v) · S1,3(v)) = −2.0861. Posmatrajmo razliku φ(B4, λ)− φ(B′4, λ) = −(n− 4)λn−5(λ+ 2). 75 6. GRAFOVI SAMALIM BROJEM KONTURA I MAKSIMALNIM RASPONOM Primetimo da za n > 7 i λ < −2 va`i φ(B4, λ) < φ(B ′ 4, λ), kada je n paran broj, φ(B4, λ) > φ(B ′ 4, λ), kada je n neparan broj. Zakqu~ujemo da je λ(B4) < λ(B ′ 4) za n > 7. PSfrag repla ements n− 5 n− 5 n− 5 B6 B ′′ 6B ′ 6 v0 v0 v0 Slika 6.3. Grafovi B6, B ′ 6 i B ′′ 6 Lema 39. Neka su B6, B ′ 6 i B ′′ 6 grafovi prikazani na sli i 6.3 i neka je n > 6. Tada va`i: (i) λ(B6) < λ(B ′′ 6 ) < λ(B ′ 6), (ii) ρ(B′′6 ) < ρ(B ′ 6) < ρ(B6). Dokaz. Primenom leme 6 dobijamo φ(B6, λ) = λ n−6(λ6 − (n + 1)λ4 − 2λ3 + (3n− 11)λ2 − (n− 5)),(6.2) φ(B′6, λ) = λ n−4(λ4 − (n + 1)λ2 − 2λ+ 4(n− 4)), φ(B′′6 , λ) = λ n−6(λ6 − (n + 1)λ4 − 2λ3 + 4(n− 4)λ2 + 2(n− 5)λ − (n− 5)). (i) Primetimo da grafovi B6 i B ′′ 6 sadr`e graf C4 · P2 kao indukovani podgraf. Odatle, na osnovu leme 5 va`i da je λ(B6) 6 λ(C4 · P2) = −2.1358 i λ(B′′6 ) 6 λ(C4 · P2) = −2.1358. Sli~no, graf B′6 sadr`i konturu C4 kao indukovani podgraf pa je λ(B′6) 6 λ(C4) = −2. Razlika polinoma φ(B6, λ) i φ(B′′6 , λ) jednaka je φ(B6, λ)− φ(B′′6 , λ) = −λn−5(n− 5)(λ+ 2). Odatle zakqu~ujemo da je za λ < −2 i n > 6 ispuweno φ(B6, λ) < φ(B ′′ 6 , λ), kada je n paran broj, φ(B6, λ) > φ(B ′′ 6 , λ), kada je n neparan broj, odnosno (6.3) λ(B6) < λ(B ′′ 6 ), za n > 6. 76 6. GRAFOVI SAMALIM BROJEM KONTURA I MAKSIMALNIM RASPONOM Sli~no, razlika karakteristi~nih polinoma grafova B′6 i B ′′ 6 jednaka je (6.4) φ(B′′6 , λ)− φ(B′6, λ) = λn−6(n− 5)(2λ− 1). Vidimo da za λ 6 −2 i n > 6 va`e nejednakosti φ(B′′6 , λ) < φ(B ′ 6, λ), kada je n paran broj, φ(B′′6 , λ) > φ(B ′ 6, λ), kada je n neparan broj, pa je (6.5) λ(B′′6 ) < λ(B ′ 6), za n > 6. Iz (6.3) i (6.5) dobijamo da je λ(B6) < λ(B ′′ 6 ) < λ(B ′ 6) za n > 6. (ii) Kako grafoviB6,B ′ 6 iB ′′ 6 sadr`e konturuC4 kao indukovani podgraf, onda na osnovu leme 5 va`i ρ(B6) > ρ(C4) = 2, ρ(B ′ 6) > ρ(C4) = 2 i ρ(B′′6 ) > ρ(C4) = 2. Razlika karakteristi~nih polinoma grafova B6 i B ′ 6 jednaka je φ(B6, λ)− φ(B′6, λ) = −λn−6(n− 5)(λ2 + 1). Odatle je φ(B6, λ) < φ(B ′ 6, λ) za λ > 2 i n > 6, pa zakqu~ujemo da je (6.6) ρ(B′6) < ρ(B6), za n > 6. Sli~no, na osnovu (6.4) znamo da je φ(B′′6 , λ)− φ(B′6, λ) = λn−6(n− 5)(2λ− 1). Odatle je φ(B′6, λ) < φ(B ′′ 6 , λ) za λ > 2 i n > 6, odnosno (6.7) ρ(B′′6 ) < ρ(B ′ 6), za n > 6. Iz (6.6) i (6.7) sledi da je ρ(B′′6 ) < ρ(B ′ 6) < ρ(B6) za n > 6. Lema 40. Neka je B4 graf prikazan na sli i 6.2,B5 graf prikazan na sli i 6.4 i B6 graf prikazan na sli i 6.3 . Tada va`i: (i) λ(B4) < λ(B5) za n > 5, (ii) λ(B4) < λ(B6) za n > 9. PSfrag repla ements n− 5 v0 Slika 6.4. Graf B5 77 6. GRAFOVI SAMALIM BROJEM KONTURA I MAKSIMALNIM RASPONOM Dokaz. Na osnovu (6.1), (6.2) i primenom leme 6 dobijamo polinome φ(B4, λ) = λ n−4(λ4 − (n+ 1)λ2 − 4λ+ 2n− 8), φ(B5, λ) = λ n−6(λ+ 1)2(λ− 1)(λ3 − λ2 − (n− 1)λ+ n− 5), φ(B6, λ) = λ n−6(λ6 − (n+ 1)λ4 − 2λ3 + (3n− 11)λ2 − (n− 5)). (i) Grafovi B4 i B5 sadr`e zvezdu S1,n−3 kao indukovani podgraf, pa na osnovu leme 5 sledi λ(B4) 6 − √ n− 3 i λ(B5) 6 − √ n− 3. Posmatrajmo razliku (6.8) φ(B4, λ)− φ(B5, λ) = −λn−6(3λ2 + 4λ− n+ 5). Primetimo da je λ0 = −2−√3n−11 3 mawa nula polinomaP (λ) = 3λ2+4λ−n+5. Kako za n > 5 va`i −√n− 3 < −2− √ 3n− 11 3 , dobijamo da je P (λ) = 3λ2 + 4λ− n+ 5 > 0 za svako λ 6 −√n− 3 i n > 5. Na osnovu (6.8) zakqu~ujemo da je za λ 6 −√n− 3 i n > 5 φ(B4, λ) < φ(B5, λ), kada je n paran broj, φ(B4, λ) > φ(B5, λ), kada je n neparan broj. Dakle, λ(B4) < λ(B5) za n > 5. (ii) Neka je u nastavkun > 9. Razlika karakteristi~nih polinoma grafova B4 i B6 je (6.9) φ(B4, λ)− φ(B6, λ) = λn−6(λ+ 1)P (λ), gde je P (λ) = −2λ2− (n− 5)λ+n− 5. Polinom P (λ) ima dva korena: λ1 > 0 i λ2 = −n+5−√n2−2n−15 4 < −2. Na osnovu (6.9) vidimo da za svako λ ∈ (λ2,−1) va`i φ(B4, λ) < φ(B6, λ), kada je n paran broj, φ(B4, λ) > φ(B6, λ), kada je n neparan broj. (6.10) Fokusirajmo se sada na najmawe sopstvene vrednosti ova dva grafa. Na osnovu jednakosti (6.1) znamo da je φ(B4, λ) = λ n−4f1(λ), gde je f1(λ) = λ 4 − (n+ 1)λ2 − 4λ+ 2(n− 4). Funk ija f1(λ) ima dva negativna korena i mawi koren je najmawa karak- teristi~na vrednost λ(B4) grafa B4. Koriste}i softver Mathematica 7 dobijamo da je f1(λ2) > 0 za n > 9. Kako je f1(−2) = −2(n − 6) < 0 i 78 6. GRAFOVI SAMALIM BROJEM KONTURA I MAKSIMALNIM RASPONOM f1(0) = 2(n − 4) > 0 zakqu~ujemo da graf B4 ima ta~no jednu sopstvenu vrednost mawu od −2 i da (6.11) λ(B4) ∈ (λ2,−2). Sli~no, na osnovu jednakosti (6.2) znamo da je φ(B6, λ) = λ n−6f2(λ), gde je f2(λ) = λ 6 − (n + 1)λ4 − 2λ3 + (3n− 11)λ2 − (n− 5). Funk ija f2(λ) ima tri negativna korena i najmawi od wih predstavqa naj- mawu karakteristi~nu vrednost λ(B6) grafaB6. Koriste}i softverMathe- matica 7 dobijamo da je f2(λ2) > 0 za n > 9. Kako je f2(−2) = −5(n− 5) < 0, f2(−1) = n− 4 > 0 i f2(0) = −n + 5 < 0 zakqu~ujemo da graf B6 ima ta~no jednu sopstvenu vrednost mawu od −2 i da (6.12) λ(B6) ∈ (λ2,−2). Na osnovu (6.10), (6.11) i (6.12) sledi da je λ(B4) < λ(B6) za n > 9. Graf sa maksimalnim rasponom u klasi bi ikli~nih grafova reda n > 27 neposredno dobijamo iz teoreme 20 (ii). Primetimo da je G0 ∼= B4 za k = 1. Preostaje jo{ da ovaj problem re{imo za bi ikli~ne grafove reda 4 6 n 6 27. Pri tome, koristi}emo neke grafove koji su ve} prikazani u sek iji 4.2, pa }e ovde biti kori{}ene iste oznake kao u toj sek iji. Ozna~imo saB(n) skup svihpovezanihbi ikli~nih grafova san~vorova. Tada je (6.13) B(n) = C(n, 2) ∪ B̂(n), gde je C(n, 2) skup svih kaktusa reda n sa ta~no dve konture, a B̂(n) skup svih povezanih bi ikli~nih grafova reda n koji sadr`e dve konture koje imaju vi{e od jednog zajedni~kog ~vora. O~igledno, C(n, 2) ∩ B̂(n) = ∅. Ako G ∈ B̂(n), tada u grafu G postoji indukovani podgraf G0 koji sadr`i tri disjunktna puta P1, P2 i P3 sa zajedni~kim po~etnim ~vorom v1 i zajedni~kim krajwim ~vorom v2 (slika 6.5). Graf G 0 nazivamo osnovom grafa G i on je funk ija odgovaraju}ih parametara, tj. G0 = G0(p, q, r) gde je p = |V (P1)|, q = |V (P2)| i r = |V (P3)| (p 6 q 6 r). PSfrag repla ements v1 v2 P1 P2 P3 Slika 6.5. Graf G0 Problemmaksimalnograsponarazmatra}emoodvojeno u skupovimaC(n, 2) i B̂(n). 79 6. GRAFOVI SAMALIM BROJEM KONTURA I MAKSIMALNIM RASPONOM Neka jeB0 bi ikli~ni graf prikazan na sli i 6.6 aB5 bi ikli~ni graf prikazan na sli i 6.4. Primetimo da je B0 u stvari graf B1,1 = B(1, 1, 0) sa slike 5.2, a B5 graf B2,0 = B(2, 0, n − 5) sa slike 5.2. Slede}i rezultat je tako|e deo teoreme 16 dobijene u glavi 5, a koja se odnosi na problem maksimalnog raspona u klasi kaktusa sa n ~vorova i k kontura. PSfrag repla ements v0 Slika 6.6. Graf B0 Lema 41. GrafB0 je jedinstven graf sa maksimalnim rasponom u klasi C(n, 2) za n = 6, a graf B5 jedinstveni graf sa maksimalnim rasponom u istoj klasi za n > 5 i n 6= 6. Fokusirajmo se sada na klasu B̂(n). Lema 42. Ako graf G ∈ B̂(n) sadr`i bar dva stabla zaka~ena za razli~ite ~vorove osnoveG0, onda postoje grafoviG′, G′′ ∈ B̂(n) koji se sastoje iz osnove G0 i jednog stabla zaka~enog za neki ~vor osnove, takvi da je (i) λ(G′) 6 λ(G), (ii) ρ(G) < ρ(G′′). Dokaz. Neka je T1 stablo zaka~eno za ~vor u ∈ V (G0), a T2 stablo zaka~eno za ~vor v ∈ V (G0), u grafu G ∈ B̂(n). (i) Ozna~imo sa Y karakteristi~ni vektor koji odgovara λ(G), a sa yu i yv wegove koordinate koje odgovaraju redom~vorovimaui v. Pretpostavimoda je |yu| > |yv|. GrafG se mo`e posmatrati kao koales en ijaG = B(v) ·T2(v). Neka je G∗ = B(u) · T2(v). Tada, na osnovu leme 4 va`i λ(G∗) 6 λ(G). Primenom ovog postupka na svaka dva stabla zaka~ena za razli~ite ~vorove osnove G0, dobijamo graf G′ ∈ B̂(n) koji se sastoji iz osnove G0 i ta~no jednog stabla zaka~enog za neki ~vor osnove, za koji je λ(G′) 6 λ(G). (ii) Neka je X Peronov vektor grafa G, a xu i xv wegove koordinate koje odgovaraju redom ~vorovima u i v. Pretpostavimo da je xu > xv . Kao i u slu~aju (i), neka je G = B(v) · T2(v) i G∗ = B(u) · T2(v). Na osnovu leme 3 sledi da je ρ(G) < ρ(G∗). Ponavqaju}i ovaj postupak za svaka dva stabla zaka~ena za razli~ite ~vorove osnove G0, dobijamo graf G′′ ∈ B̂(n) koji se sastoji iz osnove G0 i ta~no jednog stabla zaka~enog za neki ~vor osnove, za koji va`i ρ(G) < ρ(G′′). Lema 43. Ako je G ∈ B̂(n) graf sa osnovom G0 = G0(2, 3, r) (r > 4), a B6 graf prikazan na sli i 6.3, tada je ρ(G) 6 ρ(B6). Jednakost je ispuwena ako i samo ako je G ∼= B6. 80 6. GRAFOVI SAMALIM BROJEM KONTURA I MAKSIMALNIM RASPONOM Dokaz. Neka je G ∈ B̂(n) graf sa osnovom G0 = G0(2, 3, r) (r > 4) i neka je P3 = u0u1 · · ·ur−2ur−1, pri ~emu je u0 = v1 i ur−1 = v2. Ako grafG sadr`i bar dva stabla zaka~ena za razli~ite ~vorove osnove G0, tada na osnovu leme 42 (ii) postoji grafG′ ∈ B̂(n) koji sadr`i samo jedno stablo zaka~eno za neki ~vor u ∈ V (G0) i za koji je ρ(G) < ρ(G′). Ukoliko je r > 4, posmatrajmo graf G′′ ∈ B̂(n) definisan na slede}i na~in. Ako je u = ui (1 6 i 6 r 2 ; simetri~ni slu~ajevi se defini{u ana- logno), neka je G′′ = G′ − uiui−1 + uiv1 − ui+1ui+2 + ui+1v2. Ako je u 6= ui (1 6 i 6 r−2), neka jeG′′ = G′−u2u3+u2v2. Na osnovu lema 8 i 5 vidimo da je ρ(G′) < ρ(G′′) i (G′′)0 = (G′′)0(2, 3, 4). Graf G′′ se sastoji iz osnove (G′′)0 i najvi{e tri stabla zaka~ena za razli~ite ~vorove osnove. Ako grafG′′ sadr`i bar dva stabla zaka~ena za razli~ite ~vorove osnove, tada na osnovu leme 42 (ii) postoji grafG′′′ ∈ B̂(n) koji se mo`e predstaviti u obliku G′′′ = (G′′)0(u) · T (u), za koji je ρ(G′′) < ρ(G′′′). Neka je sada G∗ = (G′′)0(u) · S1,k−1(u), gde je k red stabla T . Na osnovu leme 10 sledi da je ρ(G′′′) 6 ρ(G∗) i jednakost va`i ako i samo ako je T ∼= S1,k−1. Naovaj na~indobili smo grafG∗ ∈ B̂(n) sa osnovom (G∗)0 = (G∗)0(2, 3, 4), takav da je G∗ ∼= B6 ili G∗ ∼= B′6 ili G∗ ∼= B′′6 i ρ(G) 6 ρ(G∗). Iz ove ne- jednakosti i leme 39 (ii) neposredno sledi da je ρ(G) 6 ρ(B6). Na osnovu opisanog postupka mo`e se zakqu~iti da je jednakost ispuwena ako i samo ako je G ∼= B6. U nastavku }e nam biti potrebna i slede}a teorema. Teorema 22 ([7]). Neka je G povezan bi ikli~ni graf sa n ~vorova. Tada je ρ(G) 6 ρ(B4) i jednakost va`i ako i samo ako G ∼= B4 (slika 6.2). PSfrag repla ements v0 n− 5 Slika 6.7. Graf B2 U narednoj lemi dolazimo da rezultata koji opisuje strukturu grafa koji ima maksimalni raspon u klasi B̂(n). Lema 44. Neka je G proizvoqan graf iz skupa B̂(n). (i) Ako je 5 6 n 6 8, tada je s(G) 6 s(B2) i jednakost va`i ako i samo ako je G ∼= B2 (slika 6.7). (ii) Ako je n = 4 ili n > 9, tada je s(G) 6 s(B4) i jednakost va`i ako i samo ako je G ∼= B4 (slika 6.2). 81 6. GRAFOVI SAMALIM BROJEM KONTURA I MAKSIMALNIM RASPONOM Dokaz. Za 4 6 n 6 5 dokaz sledi na osnovu tabeleA.1 svih povezanih grafova reda n 6 5 (dodatak A). Naime, postoji samo jedan povezan bi ikli~ni graf reda 4 (grafB4) i pet povezanih bi ikli~nih grafova reda 5 od kojih najve}i raspon ima graf B2. Pretpostavimo da je n > 6 i da jeX Peronov vektor proizvoqnog grafa G ∈ B̂(n) sa osnovom G0 = G0(p, q, r) (p 6 q 6 r). Dokaza}emo da za graf G 6∈ {B2, B4} va`i (6.14) s(G) < max{s(B2), s(B4)}. Ako je G bipartitan graf i G 6= B2, tada na osnovu teoreme 10 va`i λ(B2) < λ(G). Kako je i graf B2 bipartitan, onda je ρ(G) < ρ(B2), odakle je s(G) < s(B2). Neka je u nastavku G nebipartitan graf i G 6= B4. Tada mo`emo razli- kovati slede}a dva slu~aja. 1◦ p = 2, q > 4, r > q ili p > 3, q > 3, r > 3 i parametri p, q i r nisu iste parnosti. 2◦ p = 2, q = 3, r > 3. Razmotrimo svaki slu~aj posebno. 1◦ Pretpostavimo da su p i q iste parnosti, a parametar r razli~ite par- nosti od p i q. Ako graf G sadr`i bar dva stabla zaka~ena za razli~ite ~vorove osnove G0, tada na osnovu leme 42 (ii) postoji graf G′ ∈ B̂(n) koji sadr`i ta~no jedno stablo zaka~eno za neki ~vor osnove G0 i za koji va`i ρ(G) < ρ(G′). U ovom slu~aju je r > 4. Neka je v ∈ V (P3) \ {v1, v2, u} proizvoqan ~vor, neka su ~voroviw1, w2 ∈ V (P3)wegovi susediineka jeG∗ = G′ − w1v + w1w2. Vidimo da G∗ ∈ B̂(n) i (G∗)0 = (G∗)0(p, q, r − 1). Na osnovu lema 8 i 5 do- bijamo da je ρ(G′) < ρ(G∗). Kako je graf G∗ bipartitan i G 6= B2, onda je ρ(G∗) < ρ(B2). Odatle sledi da je ρ(G) < ρ(B2), odnosno λ(B2) = −ρ(B2) < −ρ(G) < λ(G). Dakle, s(G) < s(B2). Sli~no, u slu~aju kada su p i r, ili q i r iste parnosti mo`emo dobiti graf G′ ∈ B̂(n) koji sadr`i samo jedno stablo zaka~eno za osnovu. Zatim, primenom opisanog postupka na jedan ili dva puta grafaG′ dobija se bipar- titan graf G∗ (G∗ 6= B2), za koji je ρ(G) < ρ(G′) < ρ(G∗) < ρ(B2). Odatle zakqu~ujemo da je s(G) < s(B2). 2◦ Neka je G nebipartitan graf sa osnovom G0 = G0(2, 3, r) (r > 3). Ako grafG sadr`i bar dva stabla zaka~ena za razli~ite ~vorove osnoveG0, tada na osnovu leme 42 (i) postoji graf G′ ∈ B̂(n) koji sadr`i samo jedno stablo zaka~eno za neki ~vor u ∈ V (G0) i za koji je λ(G′) 6 λ(G). Graf G′ mo`emo 82 6. GRAFOVI SAMALIM BROJEM KONTURA I MAKSIMALNIM RASPONOM posmatrati kao koales en ijuG′ = G0(u) ·T (u), gde je stablo T reda k. Neka je sada G′′ = G0(u) · S1,k−1(u). Tada G′′ ∈ B̂(n) i (G′′)0 = (G′′)0(2, 3, r). Na osnovu leme 10 va`i λ(G′′) 6 λ(G′). Ako je r = 3 ili r = 4, neka je G∗ = G′′. Ako je r > 4, neka je P3 = u0u1 · · ·ur−2ur−1 (u0 = v1, ur−1 = v2) i neka je Y = (y1, y2, . . . , yn) sopstveni vektor koji odgovara λ(G ′′). Tada se mogu dogoditi slede}a dva slu~aja. a) Postoji ~vor u ∈ V (P3) takav da je yu = 0. Neka je v ∈ V (P3) ~vor susedan sa ~vorom u, a w ∈ V (P3) ~vor koji nije susedan sa ~vorom u, pri ~emu ~vorove v i w biramo na slede}i na~in (simetri~ni slu~ajevi se defini{u analogno). Ako je u = v1, tada je v = u1 i w = ur−2. Ako je u = ui (1 6 i 6 r2), tada je v = ui+1 i w = v2. Rota ijom grane uv oko ~vora u, u pozi iju uw, dobijamo grafG∗ = G′′−uv+uw ~ija se najmawa sopstvena vrednost ne pove}ava,tj. λ(G∗)−λ(G′′) = 2yu(yw−yv) 6 0. Vidimo da G∗ ∈ B̂(n), (G∗)0 = (G∗)0(2, 3, r′) (r′ < r) i λ(G∗) 6 λ(G′′). b) Za svaki ~vor u ∈ V (P3) va`i yu 6= 0. Tada mo`emo razlikovati slede}e dve mogu}nosti. b.1) U grafu G′′, na putu P3 postoje dva susedna ~vora u = ui i v = ui+1 (i ∈ {0, . . . , r − 2}), za koje va`i yuyv > 0. Bez gubitka op{tosti pretpostavimo da je yu > yv > 0. Tada, pomo}u (λ,X)karakteristi~nih jedna~ina (2.4) zakqu~ujemo da postoji ~vor w ∈ V (P3) (w 6= u i w 6= v) takav da je yw < 0. Ako je w = uj (j > i + 1), onda rota ijom grane uv oko ~vora u, u pozi iju uw, dobijamo graf G∗ = G′′ − uv + uw. Tada, G∗ ∈ B̂(n), (G∗)0 = (G∗)0(2, 3, r′) (r′ < r) i imamo da je λ(G∗) − λ(G′′) = 2yu(yw − yv) < 0, tj. λ(G∗) < λ(G′′). Ako je w = uj (j < i), onda rota ijom grane uv oko ~vora v, u pozi iju vw, dobijamo grafG∗ = G′′−uv+ vw za koji je λ(G∗)− λ(G′′) = 2yv(yw− yu) < 0. Tako|e, G∗ ∈ B̂(n), (G∗)0 = (G∗)0(2, 3, r′) (r′ < r) i λ(G∗) < λ(G′′). b.2) U grafu G′′ za svaka dva susedna ~vora u, v ∈ V (P3) va`i yuyv < 0. Bez gubitka op{tosti, pretpostavimo da je yu0 > 0. Sledi da je yu1 < 0, yu2 > 0, yu3 < 0, yu4 > 0, . . .. Ako je yu3 6 yu1 , neka je G ∗ = G′′ − u0u1 + u0u3. Sli~no, ako je yu3 > yu1 ,neka je G ∗ = G′′ − u3u4 + u1u4. U prvom slu~aju dobijamo da jeλ(G∗)−λ(G′′) = 2yu0(yu3−yu1) 6 0, a u drugomλ(G∗)−λ(G′′) = 2yu4(yu1 − yu3) < 0. U oba slu~aja G∗ ∈ B̂(n), (G∗)0 = (G∗)0(2, 3, r′) (r′ < r), i λ(G∗) 6 λ(G′′). Graf G∗, dobijen u slu~ajevima a) i b), sastoji se iz osnove (G∗)0(2, 3, r′) (r′ < r) i jednog ili dva stabla prika~enih za razli~ite ~vorove osnove. Opisanipostupak sadamo`emoponoviti sve dokne dobijemo grafG∗ ∈ B̂(n), 83 6. GRAFOVI SAMALIM BROJEM KONTURA I MAKSIMALNIM RASPONOM koji se sastoji iz (G∗)0 = (G∗)0(2, 3, 3) ili (G∗)0 = (G∗)0(2, 3, 4), i jedne zve- zde prika~ene za neki ~vor osnove (G∗)0, takav da je (6.15) λ(G∗) 6 λ(G). Ako je G∗ ∼= B4 ili G∗ ∼= B′4 tada iz leme 38, i nejednakosti (6.15) dobijamo λ(B4) 6 λ(G). Na osnovu teoreme 22 vidimo da je ρ(G) < ρ(B4), odakle sledi da je s(G) < s(B4). Ako je n > 9 i G∗ ∼= B6 ili G∗ ∼= B′6 ili G∗ ∼= B′′6 , onda na osnovu lema 39 (i) i 40 (ii) i nejednakosti (6.15) zakqu~ujemo da je λ(G) < λ(B4). Tako|e, na osnovu teoreme 22 je ρ(G) < ρ(B4), odakle sledi s(G) < s(B4). Ako je 6 6 n 6 8 i G∗ ∼= B6 ili G∗ ∼= B′6 ili G∗ ∼= B′′6 , tada na osnovu leme 39 (i) i nejednakosti (6.15) va`i λ(B6) 6 λ(G). Sli~no, na osnovu leme 43 va`i ρ(G) 6 ρ(B6), pa zakqu~ujemo da je s(G) 6 s(B6). Kako je s(B6) = 4.7411 za n = 6, s(B6) = 5.0325 za n = 7 i s(B6) = 5.3378 za n = 8, analizom vrednosti za s(B4) prikazanih u tabeli 6.1 vidimo da je s(B6) < s(B4) za 6 6 n 6 8. Stoga, s(G) < s(B4) za 6 6 n 6 8. n 5 6 7 8 9 10 s(B2) 4.8990 5.1152 5.3525 5.6050 5.8670 6.1336 s(B4) 4.4347 4.8136 5.1844 5.5350 5.8674 6.1839 n 11 12 13 14 15 16 s(B2) 6.4008 6.6663 6.9282 7.1856 7.4380 7.6850 s(B4) 6.4866 6.7773 7.0571 7.3272 7.5886 7.8418 n 17 18 19 20 21 22 s(B2) 7.9267 8.1631 8.3942 8.6204 8.8417 9.0584 s(B4) 8.0878 8.3269 8.5598 8.7869 9.0086 9.2251 n 23 24 25 26 27 − s(B2) 9.2708 9.4789 9.6830 9.8834 10.0800 − s(B4) 9.4370 9.6443 9.8475 10.0467 10.2422 − Tabela 6.1. Rasponi grafova B2 i B4 za 5 6 n 6 27 Na ovaj na~in dokazali smo nejednakost (6.14). U tabeli 6.1 prikazani su rasponi grafova B2 i B4 za 5 6 n 6 27, dobijeni kori{}ewem softvera NewGraph. Jasno je da je s(B4) < s(B2) za 5 6 n 6 8 i s(B2) < s(B4) za 9 6 n 6 27. Tako|e, iz teoreme 20 (ii) vidimo da je s(B2) < s(B4) za n > 28, {to kompletira dokaz teoreme. Na osnovu prethodnih rezultata dobijamo jedinstveni graf sa najve}im rasponom u klasi povezanih bi ikli~nih grafova reda n. 84 6. GRAFOVI SAMALIM BROJEM KONTURA I MAKSIMALNIM RASPONOM Teorema 23. Neka je G povezan bi ikli~ni graf reda n. (i) Ako je 5 6 n 6 8, tada je s(G) 6 s(B2) i jednakost va`i ako i samo ako je G ∼= B2 (slika 6.7). (ii) Ako je n = 4 ili n > 9, tada je s(G) 6 s(B4) i jednakost va`i ako i samo ako je G ∼= B4 (slika 6.2). Dokaz. Za n = 4 postoji samo jedan povezan bi ikli~ni graf reda 4 (graf B4) i tvr|ewe teoreme je ta~no. Neka je daqe n > 5. Ozna~imo sa B∗ graf sa maksimalnim rasponom u klasi B(n). Na osnovu rela ije (6.13) i lema 41 i 44 dolazimo do slede}ih zakqu~aka. Ako je n = 6, tada B∗ ∈ {B0, B2}. Kako je s(B0) = 4.6947 < 5.1152 = s(B2), o~igledno je B ∗ ∼= B2. Ako je n = 5 ili 7 6 n 6 8, onda B∗ ∈ {B2, B5}. Na osnovu leme 40 (i) i teoreme 22 sledi da je s(B5) < s(B4), a na osnovu rezultata iz tabele 6.1 dobijamo da je s(B4) < s(B2). Prema tome, B ∗ ∼= B2. Ako je n > 9, tada B∗ ∈ {B4, B5}. Kako je s(B5) < s(B4) na osnovu leme 40 (i) i teoreme 22, zakqu~ujemo da je B∗ ∼= B4, {to kompletira dokaz ove teoreme. 85 Dodatak A Dodatne tabele U spektralnoj teoriji grafova, ~esto se de{ava da se pri dokazivawu ne- kih osobina grafova, tehnika koja se koristi ne mo`e primeniti na grafove sa malim brojem ~vorova. To je bio slu~aj i u ovoj doktorskoj diserta iji. Da bi teza bila kompletna, na kraju navodimo sve povezane grafove reda n za 2 6 n 6 5, wihove najmawe karakteristi~ne vrednosti, indekse i ra- spone, kao i sve bi ikli~ne grafova reda n = 6 i wihove karakteristike. Prikazane spektralne invarijante dobijene su pomo}u softvera NewGraph. A.1 Povezani grafovi sa 2 do 5 ~vorova PSfrag repla ements 1 2 3 PSfrag repla ements 4 5 6 86 A.1 POVEZANI GRAFOVI REDA 2 6 n 6 5 PSfrag repla ements 7 8 9 PSfrag repla ements 10 11 12 PSfrag repla ements 13 14 15 PSfrag repla ements 16 17 18 87 A.1 POVEZANI GRAFOVI REDA 2 6 n 6 5 PSfrag repla ements 19 20 21 PSfrag repla ements 22 23 24 PSfrag repla ements 25 26 27 PSfrag repla ements 28 29 30 Slika A.1. Povezani grafovi reda 2 6 n 6 5 Sa slike A.1 primetimo da me|u povezanim grafovima reda 4 grafovi 6 i 7 su uni ikli~ni, a graf 8 je bi ikli~an graf. Sli~no, me|u povezanim grafovima reda 5 grafovi 13, 14, 15, 16 i 17 su uni ikli~ni a grafovi 18, 19, 20, 21 i 22 su bi ikli~ni grafovi. 88 A.1 POVEZANI GRAFOVI REDA 2 6 n 6 5 n Redni broj Najmawa sopstvena Indeks Raspon grafa vrednost grafa grafa grafa 2 1 −1.000 1.000 2.000 3 2 −1.414 1.414 2.828 3 −1.000 2.000 3.000 4 4 −1.618 1.618 3.236 5 −1.732 1.732 3.464 6 −1.481 2.170 3.651 7 −2.000 2.000 4.000 8 −1.562 2.562 4.123 9 −1.000 3.000 4.000 5 10 −1.732 1.732 3.464 11 −2.000 2.000 4.000 12 −1.848 1.848 3.696 13 −1.675 2.214 3.889 14 −1.814 2.343 4.156 15 −1.618 2.303 3.921 16 −2.136 2.136 4.272 17 −1.618 2.000 3.618 18 −1.562 2.562 4.123 19 −1.749 2.685 4.435 20 −1.776 2.641 4.417 21 −2.000 2.481 4.481 22 −2.449 2.449 4.899 23 −2.177 2.856 5.033 24 −1.514 3.086 4.600 25 −2.000 3.000 5.000 26 −1.618 2.935 4.553 27 −2.000 3.236 5.236 28 −1.681 3.323 5.005 29 −1.000 4.000 5.000 30 −1.646 3.646 5.292 Tabela A.1. Najmawe sopstvene vrednosti, indeksi i rasponi povezanih grafova reda 2 6 n 6 5 89 A.2. POVEZANI BICIKLI^NI GRAFOVI SA 6 ^VOROVA A.2 Povezani bi ikli~ni grafovi sa 6 ~vorova PSfrag repla ements 1 2 PSfrag repla ements 3 4 PSfrag repla ements 5 6 7 PSfrag repla ements 8 9 10 90 A.2 POVEZANI BICIKLI^NI GRAFOVI REDA 6 PSfrag repla ements 11 12 13 PSfrag repla ements 14 15 PSfrag repla ements 16 17 PSfrag repla ements 18 19 Slika A.2. Povezani bi ikli~ni grafovi reda 6 91 A.2 POVEZANI BICIKLI^NI GRAFOVI REDA 6 n Redni broj Najmawa sopstvena Indeks Raspon grafa vrednost grafa grafa grafa 6 1 −1.732 2.414 4.146 2 −1.903 2.709 4.612 3 −1.678 2.628 4.306 4 −2.191 2.503 4.694 5 −1.903 2.709 4.612 6 −1.791 2.791 4.582 7 −1.894 2.753 4.647 8 −2.000 2.813 4.813 9 −2.000 2.732 4.732 10 −1.851 2.705 4.556 11 −1.866 2.655 4.521 12 −2.557 2.557 5.114 13 −2.524 2.524 5.048 14 −2.136 2.539 4.675 15 −2.141 2.599 4.740 16 −2.000 2.561 4.561 17 −2.164 2.391 4.555 18 −1.756 2.438 4.194 19 −2.414 2.414 4.828 Tabela A.2. Najmawe sopstvene vrednosti, indeksi i rasponi povezanih bi ikli~nih grafova reda 6 92 Dodatak B Summary The great book of Nature lies ever open before our eyes and the true philosophy is written in it. We cannot read it unless we have first learned the language and the characteristics in which it is written. And it is written in mathematical language.  Galileo Galilei. Spectral graph theory is an important interdisciplinary field of science and mathematics in which methods of linear algebra are used to solve problems in graph theory. It has numerous applications for modelling problems in che- mistry, computers science, medicine, economy, and physics, to name just a few. By representing a graph as an adjacency matrix, matrix theory can be applied to graph theory. Features of the graph can be investigated using the eigenvalues and the eigenvectors of the adjacency matrix, and these give us information about the graph’s structure. The eigenvalues of a graph G can be ordered decreasingly, where the first is denoted by ρ(G) and is called the index of the graph and the least eigenvalue is denoted by λ(G). A graph’s spread s(G) is defined as the difference between the greatest and the least eigenvalue of the graph’s adjacency matrix, i.e. s(G) = ρ(G)− λ(G). The principal topic of this doctoral thesis is the least eigenvalue of a graph. The structure of a graph G that has the minimum least eigenvalue within a certain class of graphs is determined. This graph is referred to as an extremal graph. The first chapter of the thesis contains a short history of Spectral Graph Theory along with a motivation for the research that is presented within this thesis. Definitions and features of a graph’s spectra are presented in the second chapter, as well as the lemmas that are used in subsequent chapters. The third chapter presents and extends the latest results found in the literature concerning extremal graphs [4, 5, 37], specifically those found within the class of graphs that have a prescribed number of nodes and edges. These 93 results form a recent publication [31]. The sign pattern of an eigenvector that corresponds to G determines a partition of the vertex set, which affects the structure of the graph G. This graph is either bipartite or the join of two nested split graphs (also known as threshold graphs). A subsection of this chapter concerning the case of bipartite graphs is also presented (advances regarding threshold graphs are presented in subsequent chapters). The fourth chapter investigates extremal graphs within the classes of con- nected unicyclic, bicyclic, tricyclic, tetracyclic and pentacyclic graphs. The unique extremal graphs of these classes are obtained. This chapter utilises existing results [16, 31, 33] and simplifies existing proofs. The fifth chapter is based upon the results presented in published work derived from this thesis [2, 32]. It presents a study into the least eigenvalue, the index and the spread of cacti with a prescribed number of nodes and number of cycles. A cactus is a graph in which any two cycles have at most one mutual vertex. A unique cactus whose least eigenvalue is minimal, along with a unique cactus whose spread is maximal, is determined and it is shown that these two graphs are the same, except in a finite number of cases. The sixth chapter of this thesis presents a study of the maximal spread within the classes of connected unicyclic, bicyclic, tricyclic, tetracyclic and pentacyclic graphs and the unique graphs with this property are obtained. The results of this chapter are based on work found in the literature [1, 6, 12, 16, 31, 32, 33]. Appendix A, presented at the end of this thesis, contains figures depicting all the connected graphs with less than six vertices and all the connected bicyclic graphs with six vertices, their indices, least eigenvalues and spreads. Some of these values are utilised within the proofs that are presented in the previous chapters. Since new applications of spectral graph theory are constantly being di- scovered, the investigation into spectral properties of graphs has become an important topic in sciences and in mathematics. It is therefore hoped that the findings of this thesis will find application in these new fields. 94 Literatura [1] T. Aleksic´ and M. Petrovic´, “Bicyclic graphs whose spread is maximal,” Linear Algebra and its Applications, under review, 2012. [2] T. Aleksic´ and M. Petrovic´, “Cacti whose spread is maximal,” Graphs and Combinatorics, under review, 2012. [3] F. K. Bell, “On the maximal index of connected graphs,” Linear Algebra and its Applications, vol. 144, pp. 135–151, 1990. [4] F. K. Bell, D. Cvetkovic´, P. Rowlinson, and S. K. Simic´, “Graphs for which the least eigenvalue is minimal, I,” Linear Algebra and its Applications, vol. 429, pp. 234–241, 2008. [5] F. K. Bell, D. Cvetkovic´, P. Rowlinson, and S. K. Simic´, “Graphs for which the least eigenvalue is minimal, II,” Linear Algebra and its Applications, vol. 429, pp. 2168–2179, 2008. [6] B. Borovic´anin and M. Petrovic´, “On the index of cactuses with n verti- ces,” Publications de l’Institut Mathe´matique, vol. 79, no. 93, pp. 13–18, 2006. [7] R. Brualdi and E. S. Solheid, “On the spectral radius of connected graphs,” Publications de l’Institut Mathe´matique, vol. 39, no. 53, pp. 45– 54, 1986. [8] L. Collatz and U. Sinogowitz, “Spektren endlicher grafen,” Abhandlungen aus dem Mathematischen Seminar der Universita¨t Hamburg, vol. 21, pp. 63–77, 1957. [9] G. Constantine, “Lower bounds on the spectra of symmetric matrices with nonnegative entries,” Linear Algebra and its Applications, vol. 65, no. 1, pp. 171–178, 1985. [10] D. Cvetkovic´, M. Doob, I. Gutman, and A. Torgasˇev, Recent Results in the Theory of Graph Spectra. Amsterdam: Elsevier, 1988. [11] D. Cvetkovic´, M. Doob, and H. Sachs, Spectra of Graphs: Theory and Applications, 3rd ed. Heidelberg, Leipzig: Johann Ambrosius Barth, 1995. 95 LITERATURA [12] D. Cvetkovic´ and P. Rowlinson, “On connected graphs with maximal index,” Publications de l’Institut Mathe´matique, vol. 44, no. 58, pp. 29– 34, 1988. [13] D. Cvetkovic´, P. Rowlinson, and S. K. Simic´, Eigenspaces of Graphs. Cambridge: Cambridge University Press, 1997. [14] D. Cvetkovic´, P. Rowlinson, and S. K. Simic´, Spectral Generalizations of Line Graphs, On graphs with least eigenvalue −2. Cambridge: Cambridge University Press, 2004. [15] D. Cvetkovic´, P. Rowlinson, and S. K. Simic´, An Introduction to the The- ory of Graph Spectra. Cambridge: Cambridge University Press, 2010. [16] Y.-Z. Fan, Y. Wang, and Y. B. Gao, “Minimizing the least eigenvalues of unicyclic graphs with application to spectral spread,” Linear Algebra and its Applications, vol. 429, pp. 577–588, 2008. [17] Y.-Z. Fan, F.-F. Zhang, and Y. Wang, “The least eigenvalue of the com- plements of trees,” Linear Algebra and its Applications, vol. 435, pp. 2150– 2155, 2011. [18] D. A. Gregory, D. Hershkowith, and S. J. Kirkland, “The spread of the spectrum of a graph,” Linear Algebra and its Applications, vol. 332, pp. 23–35, 2001. [19] C.-X. Hea, J.-Y. Shaob, and J.-L. Heb, “On the laplacian spectral radii of bicyclic graphs,” Discrete Mathematics, vol. 308, pp. 5981–5995, 2008. [20] A. J. Hoffman and J. H. Smith, “On the spectral radii of topologically equivalent graphs,” in Recent Advances in Graph Theory, M. Fiedler, Ed. New York: Academia Praha, 1975, pp. 273–281. [21] B. Horoldagva and S.-G. Lee, “Comparing zagreb indices for connected graphs,” Discrete Applied Mathematics, vol. 158, pp. 1073–1078, 2010. [22] Z. Huang, H. Deng, and S. K. Simic´, “On the spectral radius of cactuses with perfect matchings,” Applicable Analysis and Discrete Mathematics, vol. 5, pp. 14–21, 2011. [23] B. Huoa, X. Li, and Y. Shi, “Complete solution to a conjecture on the maximal energy of unicyclic graphs,” European Journal of Combinatorics, vol. 32, pp. 662–673, 2011. [24] S. Li and M. Zhangb, “Sharp bounds on the zeroth-order general randic´ indices of conjugated bicyclic graphs,” Mathematical and Computer Mo- delling, vol. 53, pp. 1990–2004, 2011. 96 LITERATURA [25] X. Li and J. Zhang, “On bicyclic graphs with maximal energy,” Linear Algebra and its Applications, vol. 427, pp. 87–98, 2007. [26] B. Liu and L. M.-Huo, “On the spread of the spectrum of a graph,” Discrete Mathematics, vol. 309, pp. 2727–2732, 2009. [27] H. Liu and M. Lu, “A unified approach to extremal cacti for different in- dices,” Match, Communications in Mathematical and in Computer Che- mistry, vol. 58, pp. 183–194, 2007. [28] L. Lovasz and J. Pelikan, “On the eigenvalues of trees,” Periodica Mathe- matica Hungarica, vol. 3, pp. 175–182, 1973. [29] L. Pavlovic´, M. Lazic´, and T. Aleksic´, “More on “Connected (n,m)– graphs with minimum and maximum zeroth-order general randic´ index“,” Discrete Applied Mathematics, vol. 157, pp. 2938–2944, 2009. [30] M. Petrovic´, “On graphs whose spectral spread does not exceed 4,” Pu- blications de l’Institut Mathe´matique, vol. 34, no. 48, pp. 169–174, 1983. [31] M. Petrovic´, T. Aleksic´, and S. K. Simic´, “Further results on the least eigenvalue of connected graphs,” Linear Algebra and its Applications, vol. 435, pp. 2303–2313, 2011. [32] M. Petrovic´, T. Aleksic´, and V. Simic´, “On the least eigenvalue of cacti,” Linear Algebra and its Applications, vol. 435, pp. 2357–2364, 2011. [33] M. Petrovic´, B. Borovic´anin, and T. Aleksic´, “Bicyclic graphs for which the least eigenvalue is minimal,” Linear Algebra and its Applications, vol. 430, pp. 1328–1335, 2009. [34] S. Poljak, “Minimum spectral radius of a weighted graph,” Linear Algebra and its Applications, vol. 171, pp. 53–63, 1992. [35] D. L. Powers, “Bounds on graph eigenvalue,” Linear Algebra and its Ap- plications, vol. 117, pp. 1–6, 1989. [36] P. Rowlinson, “On the maximal index of graphs with a prescribed number of edges,” Linear Algebra and its Applications, vol. 110, pp. 43–53, 1983. [37] A. Sawikowska, “Graphs with minimum eigenvalue for the number of ver- tices and edges,” Ph.D. dissertation, University in Poznan, Poland, 2009. [38] A. Schwenk, “Computing the characteristic polynomial of a graph,” in Graphs and Combinatorics, ser. Lecture Notes in Mathematics, R. Bari and F. Harary, Eds., vol. 406. New York: Springer Berlin/Heidelberg, 1974, pp. 153–172. 97 LITERATURA [39] S. K. Simic´, “On the largest eigenvalue of unicyclic graphs,” Publications de l’Institut Mathe´matique, vol. 42, no. 56, pp. 13–19, 1987. [40] S. K. Simic´, “On the largest eigenvalue of bicyclic graphs,” Publications de l’Institut Mathe´matique, vol. 46, no. 60, pp. 101–106, 1989. [41] A. Torgasˇev, “On infinite graphs with three and four nonzero eigenvalues,” Bulletin de l’Acade´mie Serbe des Sciences et des Arts, Classe des Sciences Mathe´matiques et Naturelles, Sciences mathe´matiques, vol. 76, no. 11, pp. 39–48, 1981. [42] A. Torgasˇev, “On infinite graphs with five nonzero eigenvalues,” Bulle- tin de l’Acade´mie Serbe des Sciences et des Arts, Classe des Sciences Mathe´matiques et Naturelles, Sciences mathe´matiques, vol. 79, no. 12, pp. 31–38, 1982. [43] Y. Wang and Y.-Z. Fan, “The least eigenvalue of a graph with cut verti- ces,” Linear Algebra and its Applications, vol. 433, pp. 19–27, 2010. [44] B. Wu, E. Xiao, and Y. Hong, “The spectral radius of trees on k pendant vertices,” Linear Algebra and its Applications, vol. 395, pp. 343–349, 2005. [45] J. Wu, H. Deng, and Q. Jiang, “On the spectral radius of cacti with k- pendant vertices,” Linear and Multilinear Algebra, vol. 58, pp. 391–398, 2010. [46] M. Xu, Y. Hong, J. Shu, and M. Zhai, “The minimum spectral radius of graphs with a given independence number,” Linear Algebra and its Applications, vol. 431, pp. 937–945, 2009. [47] X.-Y. Yuan, J.-Y. Shao, and Y. Liu, “The minimal spectral radius of graphs of order n with diameter n − 4,” Linear Algebra and its Applica- tions, vol. 428, pp. 2840–2851, 2008. [48] M. Zhai, Y. Wu, and J. Shu, “Maximizing the spectral radius of bicyclic graphs with fixed girth,” Linear Algebra and its Applications, vol. 431, pp. 716–723, 2009. [49] Q. Zhao and S. Li, “Sharp bounds for the zagreb indices of bicyclic graphs with k-pendant vertices,” Discrete Applied Mathematics, vol. 158, pp. 1953–1962, 2010. 98 Biografija Tatjana Aleksi} je ro|ena 17.06.1982. godine u Kragujev u. Osnovnu {koluRadoje Domanovi} zavr{ila je kao nosila diplomeVuk Karaxi} i |ak genera ije. PrvuKragujeva~ku gimnaziju, odeqewe za talentovane u~enike za matematiku i programirawe zavr{ila je 2001. godine kao nosila diplome Vuk Karaxi}. Nakon toga, upisala je Prirodno-matemati~ki fakultet u Kragujev u, smer matematika-informatika i diplomirala 2006. godine sa prose~nom o enom 9.88. Tokom studija vi{e puta je progla{ena za najboqeg studenta Prirodno- matemati~kog fakulteta i jednog od pet najboqih studenata Univerziteta u Kragujev u. Dobitnik je nagrade Kraqevine Norve{ke za 500 najboqih studenata u Srbiji i Crnoj Gori, kao i godi{we plaketeProf. dr Vojislav K. Stojanovi} Udru`ewa univerzitetskih profesora i nau~nika Srbije za najboqeg studenta u Srbiji u oblasti matemati~kih nauka u 2005. godini. Bila je stipendista Republi~ke fonda ije za razvoj nau~nog i umetni~kog podmlatka. Doktorske studije iz matematike na Prirodno-matemati~kom fakultetu u Kragujev u upisala je 2006. godine i sve predmete predvi|ene planom i programom polo`ila sa prose~nom o enom 10. Godine 2009. provela je tri mese a na stru~nom usavr{avawu na Depart- manu za kompjuterske nauke Univerziteta u Jorku u Velikoj Britaniji, u grupi prof. Edwin-a Hancock-a. Dobitnik je stipendije britanske fonda- ije British Scholarship Trust za studijski boravak u inostranstvu i dobit- nik nagrade Voya Kondic Prize za postignute najboqe rezultate u okviru studijskog boravka u inostranstvu. Na Institutu za matematiku i informatiku Prirodno-matemati~kog fakulteta u Kragujev u bila je anga`ovana kao istra`iva~-pripravnik od 2007. do 2008. godine, a zatim je izabrana u zvawe asistenta za u`u nau~nu oblast Algebra i logika. U dosada{wem radu na Institutu za matema- tiku i informatiku izvodila je ve`be iz predmeta: Diskretna matema- tika, Numeri~ka matematika, Opera iona istra`ivawa, Spe ijalni kurs elementarne matematike, Teorijske osnove informatike 1, Teorijske osnove informatike 3, Teorija grafova i Osnovi programirawa. Na Fakultetu in`ewerskih nauka u Kragujev u anga`ovana je na izvo|ewu ve`bi iz pred- meta: Matematika 1 i Matematika 2. 99 LITERATURA Tatjana Aleksi} aktivno se bavi nau~noistra`iva~kim radom iz obla- sti spektralne teorije grafova. U periodu od 2007. do 2011. godine bila je u~esnik projekta Teorija grafova i matemati~ko programirawe sa prime- nama u hemiji i tehni~kim naukama finansiranog od strane Ministarstva nauke Republike Srbije. Trenutno je anga`ovana na projektu Teorija gra- fova i matemati~ko programirawe sa primenama u hemiji i ra~unarstvu koji finansira Ministarstvo prosvete i nauke Republike Srbije. Rezultate istra`ivawa objavila je u okviru slede}ih nau~nih radova: 1. T. Aleksic´, I. Gutman, M. Petrovic´, “Estrada index of iterated line graphs,” Bulletin de l’Acade´mie Serbe des Sciences et des Arts, Classe des Sciences Mathe´matiques et Naturelles, Sciences mathe´matiques, vol. 134, no. 32, pp. 33–41, 2007; 2. B. Zhou, I. Gutman, T. Aleksic´, “A note on Laplacian energy of graphs,” MATCH Communications in Mathematical and in Computer Chemistry, vol. 60, no. 2, pp. 441–446, 2008; 3. T. Aleksic´, “Upper bounds for Laplacian energy of graphs,” MATCH Communications in Mathematical and in Computer Chemistry, vol. 60, no. 2, pp. 435–439, 2008; 4. M. Petrovic´, B. Borovic´anin, T. Aleksic´, “Bicyclic graphs for which the least eigenvalue is minimum,” Linear Algebra and its Applications, vol. 430, no. 4, pp. 1328–1335, 2009; 5. Lj. Pavlovic´, M. Lazic´, T. Aleksic´, “More on ‘Connected (n,m)-graphs with minimum and maximum zeroth-order general Randic´ index’,” Dis- crete Applied Mathematics, vol. 157, no. 13, pp. 2938–2944, 2009; 6. P. Ren, T. Aleksic´, R. Wilson, E. Hancock, “Hypergraphs, characteristic polynomials and the Ihara zeta function,” Computer Analysis of Images and Patterns, vol. 5702 of Lecture Notes in Computer Science, Springer, pp. 369–376, 2009; 7. P. Ren, E. Hancock, R. Wilson, T. Aleksic´, “Ihara coefficients: a flexi- ble tool for higher order learning,” Structural, Syntactic, and Statistical Pattern Recognition, vol. 6218 of Lecture Notes in Computer Science, Springer, pp. 18–21, 2010; 8. P. Ren, T. Aleksic´, R. Wilson, E. Hancock, “A polynomial characteriza- tion of hypergraphs using the Ihara zeta function,” Pattern Recognition, vol. 44, no. 9, pp. 1941–1957, 2011; 9. P. Ren, T. Aleksic´, D. Emms, R. Wilson, E. Hancock, “Quantum walks, Ihara zeta functions and cospectrality in regular graphs,” Quantum In- formation Processing, vol. 10, no. 3, pp. 405–417, 2011; 100 LITERATURA 10. M. Petrovic´, T. Aleksic´, V. Simic´, “On the least eigenvalue of cacti,” Linear Algebra and its Applications, vol. 435, no. 10, pp. 2357–2364, 2011; 11. M. Petrovic´, T. Aleksic´, S. Simic´, “Further results on the least eigenvalue of connected graphs,” Linear Algebra and its Applications, vol. 435, no. 9, pp. 2303–2313, 2011. Dobijene rezultate izlagala je na: • 12-tomMatemati~kom kongresu (28. avgust  2. septembar) 2008. godine u Novom Sadu; • II Me|unarodnoj konferen iji SPMMI, Savremeni problemi mate- matike, mehanike i informatike (17  19. jun) 2012. godine u Novom Pazaru. 101