Univerzitet u Kragujevcu Prirodno-matemati~ki fakultet Mirjana Lazi} RE[AVAWE NEKIH PROBLEMA SPEKTRALNE TEORIJE GRAFOVA Doktorska disertacija Kragujevac 2009 Sadr`aj Predgovor 2 1 Neki rezultati o redukovanoj energiji grafa 4 1.1 Osnovni pojmovi i definicije . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 O grafovima ~ija tre}a redukovana energija nije ve}a od 3 . . . . . . . . . 6 1.3 O predukovanoj energiji grafa . . . . . . . . . . . . . . . . . . . . . . . . . 17 2 Odre|ivawe svih kona~nih i beskona~nih grafova sa sedam sopstvenih vrednosti razli~itih od nule 20 2.1 Osnovni pojmovi i definicije . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2 Kanoni~ki grafovi koji imaju sedam sopstvenih vrednosti razli~itih od nule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Maksimalni kanoni~ki grafovi koji imaju sedam sopstvenih vrednosti razli~itih od nule . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3 Neki rezultati o integralnim grafovima 33 3.1 Uvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.2 Klasa integralnih grafova oblika G ⋃ G . . . . . . . . . . . . . . . . . . . 35 3.3 Dve beskona~ne familije integralnih kompletnih tripartitnih grafova . . . . . . . . . . . . . . . . . . . . . . . 37 4 Neki rezultati o simetri~nom dvostrukom zvezdolikom stablu 40 4.1 Uvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.2 Neki pomo}ni rezultati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.3 Glavni rezultat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Prilog 47 Literatura 106 Dodatak 109 1 Predgovor Ova doktorska disertacija pripada Spektralnoj teoriji kona~nih i beskona~nih grafova, koja objediwuje elemente teorije grafova, linearne algebre i op{te spektralne teorije operatora. Teorija grafova, kao posebna matemati~ka disciplina, stara je oko sedam decenija. Razvoj ra~unarske tehnike zahtevao je izgradwu adekvatnog matemati~kog aparata tako da je zahvaquju}i tome, posredno ili neposredno, teorija grafova do`ivela svoj intenzivan razvoj, primene u najrazli~itijim nau~nim disciplinama i veliku popularnost. Pojam grafa se defini{e i spada u grupu osnovnih matemati~kih pojmova, a figura obrazovana od niza ta~aka spojenih krivim linijama je samo geometrijska predstava ili crte` grafa kojim se slikovito predstavqaju razni problemi. Primena teorije grafova i wenih metoda zauzima zna~ajno mesto u teoriji elek- tri~nih kola, teoriji sistema automatskog upravqawa, teoriji kona~nih automata, op- eracionom istra`ivawu, ra~unarstvu, teoriji pouzdanog prenosa informacija, u hemiji, ekonomskim naukama, sociologiji, biologiji itd. Nave{}emo kratak opis sadr`aja ove disertacije po pojedinim poglavqima. Disertacija se sastoji iz ~etiri poglavqa podeqena na odeqke, priloga i literature. U prvom poglavqu su dati neki rezultati o redukovanoj energiji grafa. Poglavqe je podeqeno je na tri odeqka. U odeqku 1.1 su dati neki osnovni pojmovi koji }e se koristiti u ovom poglavqu, ali i u nekim narednim. Odeqak 1.2 sadr`i rezultate iz rada [9]. U potpunosti su opisani svi povezani grafovi ~ija redukovana energija, tj. suma modula svih sopstvenih vrednosti bez mini- malne i maksimalne, nije ve}a od 3. U radu [13]M. Lepovi}a, u potpunosti su opisani svi povezani grafovi ~ija redukovana energija nije ve}a od 2, 5. Posledwiodeqak ovog poglavqa 1.3 zasniva se na rezultatima iz rada [8]. Sadr`ineke rezultate o predukovanoj energiji grafa. U radu M. Lepovi}a [15] je uvedena definicija kpozitivne redukovane energije, knegativne redukovane energije i (k, l)redukovane energije i dokazana su neka osnovna svojstva ovih energija. U ovom poglavqu se vr{e uop{tavawa (k, l)redukovane energije. Naime, za neko fiksirano p ∈ N definisana je suma |λk+1|p+ |λk+2|p+ . . .+ |λn−l|p, ozna~ena sa Slk(G, p) i nazvana pta (k, l)redukovana energija grafaG. Tako|e se uvode definicije nekih drugih vrsta predukovanih energija i dokazuju neke wihove osobine. U drugom poglavqu posmatra se problem odre|ivawa kona~nih i beskona~nih grafova sa 7 sopstvenih vrednosti razli~itih od nule, ukqu~uju}i i wihove vi{estrukosti. Ovaj 2 3problem za p = 3, 4, 5 sopstvenih vrednosti posmatrao je A. Torga{ev u radovima [21] i [22], a za p = 6M. Lepovi} u radovima [12] i [14]. Ovo poglavqe podeqeno je na tri odeqka. U odeqku 2.1 dati su osnovni pojmovi i definicije. Dobijeni rezultat dat je u odeqku 2.2. U Listi 2.1 (str. 23) ovog poglavqa i Listi 2 (str. 56) u Prilogu rada dati su statisti~ki podaci o svim kanoni~kim grafovima sa ta~no 7 sopstvenih vrednosti razli~itih od nule ukqu~uju}i i wihove vi{estrukosti. U tre}em odeqku ovog poglavqa 2.3 bi}e dat spisak svih maksimalnih kanoni~kih grafova koji imaju 7 sopstvenih vrednosti razli~itih od nule (Lista 2.2, str. 25), a u Prilogu (str. 88) je data Lista 3, koja predstavqa statistiku o podgrafovima pojedinih maksimalnih kanoni~kih grafova. Tre}e poglavqe sadr`i neke rezultate dobijene za integralne grafove. Kao i u prethodnim poglavqima, i ovde prvi odeqak 3.1 sadr`i neke osnovne pojmove i definicije. U odeqku 3.2 defini{u se neophodni i dovoqni uslovi pod kojima je graf G ⋃ G integralan, gde je G regularan integralan graf reda n i stepena r. U tre}em odeqku ovog poglavqa 3.3 posmatra se familija integralnih kompletnih tripartitinih grafova Kk,m,n za k ≥ m ≥ n. Kompletno je opisana ta familija u slu~ajevima k > m = n i k = m > n. ^etvrto poglavqe sadr`i rezultate o simetri~nom dvostrukom zvezdolikom stablu iz rada [10]. U odeqku 4.1 dati su neki osnovni pojmovi. Za stablo se ka`e da je zvezdoliko ukoliko ima ta~no jedan ~vor stepena ve}eg od dva. Neki rezultati o zvezdolikim stablima mogu se na}i u radu [17]M. Lepovi}a. U radu [19]M. Lepovi} i I. Gutman su dokazali da su dva zvezdolika stabla kospektralna ako i samo ako su izomorfna. Stablo se naziva dvostruko zvezdoliko ako ima ta~no dva susedna ~vora stepena ve}eg od dva. Odeqak 4.2 sadr`i neke pomo}ne rezultate, a glavni rezultat ovog poglavqa je dat u odeqku 4.3 ([10]). Ovde je dokazano da ne postoje dva kospektralna neizomorfna simetri~na dvostruka zvezdolika stabla. Zahvalila bih se ovom prilikom vanrednom profesoru, dr Mirku Lepovi}u, mentoru pri izradi ove disertacije i inicijatoru ovih istra`ivawa. On je dao veliki doprinos ovom radu, najpre kroz razgovore o istra`ivawima, a zatim i kroz konkretne zadatke. Posebno bih se zahvalila na razumevawu, stalnim ohrabrewima i strpqewu svojim prijateqima i porodici. Autor Glava 1 Neki rezultati o redukovanoj energiji grafa Ovo poglavqe sadr`i tri odeqka. U prvom su dati neki osnovni pojmovi i defini- cije koje }e se koristiti u ostalim odeqcima ovog poglavqa, ali i u ~itavom radu. U drugom odeqku opisani su svi povezani grafovi kod kojih suma apsolutnih vrednosti svih sopstvenih vrednosti, bez minimalne i maksimalne, nije ve}a od 3 [9]. Odeqak 1.3 sadr`i neke rezultate o predukovanoj energiji grafa [8]. 1.1 Osnovni pojmovi i definicije Neka jeG proizvoqan kona~an povezan graf bez petqi i vi{estrukih grana. Relacija H ⊆ G je oznaka da je graf H indukovani podgraf grafa G. Za indukovani podgraf obi~no se pretpostavqa da je tako|e povezani graf. Od velike va`nosti u celom radu bi}e tzv. Teorema preplitawa ([3]), koja se navodi bez dokaza. TEOREMA 1.1. (TEOREMA PREPLITAWA) Neka je G graf sa spektrom λ1 ≥ λ2 ≥ . . . ≥ λn i neka je H wegov indukovani podgraf sa spektrom µ1 ≥ µ2 ≥ . . . ≥ µm. Tada va`e slede}e nejednakosti λn−m+i ≤ µi ≤ λi (i = 1, . . . ,m). Neka je daqe P izvesna grafovska osobina. Ka`e se da je osobina P hereditarna, ako iz uslova da graf G ima osobinu P sledi da svaki wegov indukovani podgraf tako|e ima ovu osobinu. Neki od problema posmatranih u ovom radu jesu hereditarni problemi ili se svode na takve probleme. Takvi su na primer problemi u ovom i narednom poglavqu. Hereditarni problemi su do sada vi{e puta prou~avani u matemati~koj literaturi (npr. u radovima [3], [21], [22], [12]). 4 5Kod posmatrawa bilo kog hereditarnog problema, grafovi koji imaju posmatranu osobinu nazivaju se dozvoqenim za odgovaraju}i problem, a ostali grafovi se nazivaju zabrawenim. Uloga zabrawenih grafova kod generisawa svih dozvoqenih grafova mo`e biti od bitnog zna~aja, a ~esto je i skup svih minimalnih zabrawenih grafova (minimal- nih u smislu relacije ⊆ ) u posmatranom problemu kona~an. Stoga je i ovaj, tzv. metod zabrawenih grafova, vrlo bitan kod re{avawa hereditarnih problema. ^esto se mo`e mnogo saznati o strukturi izvesnog grafa, ako je poznato da neki drugi konkretan graf ne mo`e biti wegov indukovani podgraf. U ovom i narednom poglavqu se tako|e koristi pojam kanoni~ki graf. Naime, na skupu ~vorova V (G) uvodi se relacija ekvivalencije. Za dva ~vora x, y ∈ V (G) se ka`e da su ekvivalentna (u relaciji) u grafu G, u oznaci x ∼ y, ako i samo ako imaju iste susede u grafu G. Odgovaraju}i koli~nik skup (graf) bi}e ozna~en sa g i zva}e se kanoni~ki graf grafa G. Graf g je tako|e povezan, i o~igledno va`i g ⊆ G. Na primer, ako je G = Kn1,n2,...,np (p ≥ 2) kompletan ppartitni graf, onda je wegov kanoni~ki graf kompletan graf Kp. Kanoni~ki graf kompletnog grafa Kn je tako|e grafKn. Za graf G se ka`e da je kanoni~ki ako je |G| = |g|, tj. ako graf G nema nijedan par ekvivalentnih ~vorova. Neka je g kanoni~ki graf grafa G, |g| = k i N1, N2, . . . , Nk odgovaraju}i skupovi ekvivalentnih ~vorova u G. Podskupovi N1, N2, . . . , Nk su klase ekvivalencije u odnosu na definisanu relaciju. Izborom po jednog ~vora iz svake klase dobija se odgovaraju}i koli~nik skup (graf) koji se ozna~ava sa G = g(N1, N2, . . . , Nk) ili jednostavnije G = g(n1, n2, . . . , nk), gde je |Ni| = ni (i = 1, 2, . . . , k). Skupovi N1, . . . , Nk }e se zvati karakteristi~ni skupovi grafa G. O~igledno, svaki skup Ni ⊆ V (G) (i = 1, . . . , k) sadr`i samo nesusedne ~vorove, i ako postoji bar jedna grana izme|u skupova Ni, Nj (i 6= j), onda postoje sve mogu}e grane izme|u ~vorova tih skupova. Stoga se skupovi Ni (i = 1, 2, . . . , k) mogu prikazati pomo}u belih (tj. praznih) kru- gova, a sve mogu}e grane izme|u ~vorova skupa Ni i skupa Nj sa samo jednom granom izme|u odgovaraju}ih krugova. Ako je, na primer, G kompletan bipartitan graf Kn1,n2 sa karakteristi~nim skupovima N1 i N2, onda se grafKn1,n2 jednostavno ozna~ava     N1 N2 G = pri ~emu je |Ni| = ni (i = 1, 2). Jasno je da se bilo koji graf G, ~iji je kanoni~ki graf g, mo`e dobiti varirawem, na odre|eni na~in, vrednosti parametara n1, n2, . . . , nk ∈ N. Dokazano je u [21] da karakteristi~ni polinom PG(λ) grafa G ima oblik PG(λ) = n1 · n2 · . . . · nkλn−k · ∣∣∣∣∣∣∣∣∣∣∣ λ n1 −a˜12 . . . −a˜1k −a˜21 λn2 . . . −a˜2k . . . . . . . . . . . . −a˜k1 −a˜k2 . . . λnk ∣∣∣∣∣∣∣∣∣∣∣ (1.1) 6gde je n = n1 + n2 + · · ·+ nk, a [a˜ij ] je matrica susedstva kanoni~kog grafa g. Suma S(G) = |λ1|+ |λ2|+ · · ·+ |λn| naziva se energijom grafa G. Suma R1(G) = |λ2|+ |λ3|+ · · ·+ |λn| naziva se prva redukovana energija grafa G. Suma S1(G) = |λ1|+ |λ2|+ · · ·+ |λn−1| naziva se druga redukovana energija grafa G. Suma T1(G) = |λ2|+ |λ3|+ · · ·+ |λn−1| naziva se tre}a redukovana energija grafa G. 1.2 O grafovima ~ija tre}a redukovana energija nije ve}a od 3 U ovom odeqku se posmatraju samo kona~ni povezani grafovi bez petqi i vi{estrukih grana. Skup ~vorova grafa G ozna~en je sa V (G), red grafa sa |G|, a spektar je familija λ1 ≥ λ2 ≥ · · · ≥ λn sopstvenih vrednosti wegove 0 − 1 matrice susedstva. Sopstvena vrednostλ1(G) = r(G) zove se spektralniradijus grafaG, dok jeλn(G)najmawa sopstvena vrednost grafa G. Za proizvoqnu realnu konstantu a > 0 razmatra}e se klasa grafova E1(a) = {G|T1(G) ≤ a}. U radu [13] M. Lepovi} je kompletno opisao klasu E1(2.5). Ovde }e kompletno biti opisana klasa E1(3), tj. klasa svih povezanih grafova ~ija tre}a redukovana energija ne prelazi 3 ([9]). Graf G koji pripada klasi E1(3) zove se dozvoqeni graf. U suprotnom se zove zabraweni za klasu E1(3). Ako jeH povezani podgraf (indukovani) grafaG, pi{e seH ⊆ G. Koriste}i poznatu teoremu o preplitawu va`i T1(H) ≤ T1(G). Na osnovu definicije tre}e redukovane energije, jasno je da je svaki povezani podgraf dozvoqenog grafa tako|e dozvoqen. Zato se mo`e primeniti postupak zabrawenih podgrafova za generisawe svih grafova koji pripadaju klasi E1(a). Kako kompletan mpartitan graf Kn1,n2,...,nm ima samo jednu pozitivnu sopstvenu vrednost i r(G) = |λ2| + |λ3| + · · · + |λn|, lako se vidi da on pripada klasi E1(a) ako i samo ako je λ1(G) + λn(G) ≤ a. S obzirom da kompletan bipartitni grafKm,n pripada klasi E1(a) za sve vrednosti parametaram,n ∈ N, klasa E1(a) je beskona~na za svaku konstantu a > 0. Ako je g kanoni~ki graf grafa G sledi da je g ⊆ G, pa se dobija G ∈ E1(3)⇒ g ∈ E1(3). Zato }e najpre biti opisan skup svih kanoni~kih grafova koji pripadaju klasi E1(3). Mo`e se primetiti da se i mnogi drugi hereditarni problemi u Spektralnoj teoriji grafova mogu redukovati na generisawe najpre odgovaraju}eg skupa kanoni~kih grafova. U tom smislu mogu se videti radovi [21], [22], [24] i drugi. 7Generisawe kompletnog skupa kanoni~kih grafova u ovom odeqku zasniva se na slede}oj op{toj teoremi koja je dokazana u [24] i koja mo`e biti vrlo korisna pri re{avawu drugih sli~nih problema. TEOREMA 1.2. U svim, osim u nizu konkretnih slu~ajeva, svaki povezani kanoni~ki graf sa n ~vorova (n ≥ 3) sadr`i bar jedan indukovani podgraf sa n − 1 ~vorova, koji je tako|e povezan i kanoni~ki. Izuzetak od ovog pravila su grafovi na slici 1.1 kod kojih su yi i xj susedni ~vorovi (i ≤ j; i, j = 1, . . . ,m). Za ove grafove va`i T0 ⊆ T1 ⊆ T2 ⊆ . . . . s s ss T0 s s s s s s T1 s s s s s sss T2 . . . s s s s s       s s s @@ s s s s " " " " " " " ""                  @ @ . . . . . . x1 x x0 x2 x3 xm y1 y y0 y2 y3 ym . . . Tm Slika 1.1 Sada }e biti data osnovna osobina op{te klase E1(a) (a > 0). Dokaz je ura|en u [13]. Baziran je na slede}oj teoremi koja je data u radu [21]. TEOREMA 1.3. Za svako n ∈ N skup svih kanoni~kih grafova koji imaju n nenula sopstvenih vrednosti je kona~an. TEOREMA 1.4. Za svaku konstantu a > 0, skup svih kanoni~kih grafova koji pripadaju klasi E1(a) je kona~an. Direktnim pretra`ivawem spektara svih povezanih grafova sa najvi{e 5 ~vorova (videti, na primer, tabelu u [3]), nalazi se da klasa E1(3) sadr`i ta~no 16 kanoni~kih grafova reda 2, 3, 4 ili 5. Pored toga, direktnom proverom spektara svih povezanih grafova sa 6 i 7 ~vorova, (videti, na primer [4]) mo`e se uo~iti da klasa E1(3) sadr`i 8 kanoni~kih grafova sa 6 ~vorova i ne sadr`i nijedan kanoni~ki graf sa 7 ~vorova. Na osnovu Teoreme 1.2. sledi da klasa E1(3) ne sadr`i nijedan kanoni~ki graf reda n ≥ 7. 8TEOREMA 1.5. Postoji ta~no 24 kanoni~ka grafa koja pripadaju klasi E1(3). Oni su prikazani na slici 1.2. s s m n g1 s s m n sk @ @ g2 s s n k s sm l g3 s s s s @@ m n k l g4 s s m n s sl k   HHHHH g5 s s s s s n k l m p g6 s ss s m n l p sk @ @ g7 s HHs s s s m n k l p g8 s s ss s@@@@ m n k l p g9 s s ss s @@ @@ m n k l p g10 s s s ss    HH HH H HH m n p l k g11 s ss s s @ @ @ n k l m p g12 s s s s s @ @ @ m n p l k g13 s s s s s @ @ @ m k p n l g14 s s s ss    HH HH H HH m n l p k J J JJ g15 s s s ssHH m n p l k g16 s ss s s s m n k q p l g17 s s s s s s m n k l q p g18 s s s s s s @ @ @ m n k q p l g19 s s s s s s    m n k q p l g20 s s s s s s   @ @ @ n k l m q p g21 s s s s s sHHHHHH m n k q p l g22 s s s s s s @ @ @ HHHHHH n k l m q p g23 s s s s s s   @ @ @ HHHHHH k l p n m q g24 Slika 1.2 PROPOZICIJA 1.1. Graf G = g1(m,n) ∈ E1(3) (m ≤ n) za sve vrednosti parametara m i n. DOKAZ. Po{to je g1 = K2, graf G = Km,n je kompletan bipartitan graf, pa ima ta~no jednu pozitivnu i ta~no jednu negativnu sopstvenu vrednost. Stoga je T1(G) = 0 za svaki kompletan bipartitan grafKm,n. 2 9PROPOZICIJA 1.2. Graf G = g2(m,n, k) (m ≤ n ≤ k) pripada klasi E1(3) ako i samo ako (m,n, k) ima jednu od slede}ih vrednosti: (1, 1˙, 1˙), (2, 6, 6˙), (2, 7, 15), (2, 8, 10), (2, 9, 9), (3, 3, 3˙), gde p˙ zna~i da je odgovaraju}i parametar ve}i ili jednak p. DOKAZ. Po{to je g2 = K3, graf G je kompletan 3partitan grafKm,n,k. On ima samo tri nenula sopstvene vrednosti, koje su koreni polinoma (videti (1.1)) P (λ) = λ3 − (mn+mk + nk)λ− 2mnk. Prema tome G ∈ E1(3) ako i samo ako je |λ2| ≤ 3, tj. ako i samo ako je P (−3) ≥ 0. Odavde se lako dobija dokaz tvr|ewa. 2 PROPOZICIJA 1.3. Graf G = g3(m,n, k, l) (m ≤ l) pripada klasi E1(3) ako i samo ako (m,n, k, l) ima jednu od slede}ih vrednosti: (1, 2, 1˙, 1˙), (1, 1˙, 1˙, 2), (1, 1˙, 1, 4), (1, 3, 1˙, 9), (1, 3, 2, 10), (1, 3, 1, 11), (1, 4, 1˙, 5), (1, 4, 1, 7), (1, 4, 2, 6), (1, 5, 1˙, 4), (1, 5, 1, 6), (1, 5, 2, 5), (1, 12, 1, 5), (1, 11, 13, 3), (1, 12, 9, 3), (1, 13, 8, 3), (1, 14, 7, 3), (1, 15, 6, 3), (1, 9, 1˙, 3), (1, 6, 5, 4), (1, 7, 3, 4), (1, 10, 2, 4), (1, 10, 23, 3), (1, 10, 1˙, 2), (1, 19, 5, 3), (1, 29, 4, 3), (1, 1˙, 3, 3), (2, 1, 1, 1˙), (2, 2, 1˙, 2), (2, 3, 11, 2), (2, 4, 5, 2), (2, 2, 5, 3), (2, 2, 1, 4), (2, 1, 1˙, 5), (3, 1, 1, 5), (3, 1, 2, 4). DOKAZ. Lako se proverava da svi prethodno navedeni grafovi pripadaju klasi E1(3). Daqe se, prema (1.1) lako vidi da su sopstvene vrednosti ovih grafova razli~ite od nule odre|ene jedna~inom λ4 − (mn+ nk + kl)λ2 +mnkl = 0. Dakle, ove sopstvene vrednostimogu se eksplicitno odrediti. Odavde je lako pokazati da graf G = g3(m,n, k, l) ∈ E1(3) ako i samo ako je ispuweno 16mnkl − 36(mn+ nk + kl) + 81 ≤ 0. Iz ove relacije se neposredno dobija dokaz tvr|ewa. 2 PROPOZICIJA 1.4. Graf G = g4(m,n, k, l) (k ≤ l) pripada klasi E1(3) ako i samo ako (m,n, k, l) ima jednu od slede}ih vrednosti: (1, 1, 1˙, 1˙), (1, 2, 2, 1˙), (1, 3, 2, 4), (1, 1˙, 2, 3), (2, 1˙, 1, 1˙), (1˙, 1˙, 1, 2), (2, 1˙, 2, 2), (2, 1, 4, 1˙), (2, 1, 5, 8), (2, 1, 6, 6), (4, 1, 1, 1˙), (4, 2, 2, 2), (3, 2, 1, 18), (3, 3, 1, 9), (3, 4, 1, 8), (3, 11, 1, 7), (3, 1˙2, 1, 6), (4, 2, 1, 6), (4, 1˙, 1, 5), (5, 1, 1, 6), (5, 1, 2, 2), (5, 1˙, 1, 4), (6, 3, 1, 4), (7, 1, 1, 4), (12, 2, 1, 3), (13, 1, 1, 3), (11, 1˙, 1, 3). 10 DOKAZ. Mo`e se pokazati da su sve nenula sopstvene vrednosti grafa G ~iji je kanoni~ki graf g4 koreni polinoma P4(λ) = λ4 − (mn+ nk + nl + kl)λ2 − 2nklλ+mnkl. Za proizvoqan graf G = g4(m,n, k, l) mo`e se odrediti konstanta c < 0 tako da je P (c) < 0 i P (3 + c) < 0. Ako takva konstanta postoji sledi da je |λ3| < |c|, |λ2| < 3− |c| i |λ2|+ |λ3| < 3, pa je graf G = g4(m,n, k, l) dozvoqen. Na primer, za graf G = g4(1, 3, 2, 4) mo`e se izabrati c = −2.596. Po{to je P (−2.596) < 0 i P (0, 404) < 0 sledi da je |λ3| < 2.596 i |λ2| < 0.404. Ovaj graf je dozvoqen, primenom teoreme prepli- tawa dolazi se do zakqu~ka da su dozvoqeni i grafovi sa parametrima (m,n, k, l) gde je m = 1, n = 1, 2, 3, k = 1, 2, l = 1, 2, 3, 4. S druge strane, za graf G = g4(1, 3, 2, 5) je P (−2.596) > 0 i P (0, 404) > 0, pa je |λ3| > 2.596 i |λ2| > 0, 404 {to zna~i da je on zabrawen. Primenom, ponovo teoreme preplitawa sledi da su svi grafovi sa parametrima (m,n, k, l) = (1, 3, 2, 5˙) tako|e zabraweni. Na sli~an na~in odre|uju se svi dozvoqeni grafovi ~iji je kanoni~ki graf g4. 2 PROPOZICIJA 1.5. Graf G = g5(m,n, k, l) (m ≤ n ≤ k ≤ l) pripada klasi E1(3) ako i samo ako (m,n, k, l) ima jednu od slede}ih vrednosti: (1, 1, 4, 1˙), (1, 1, 5, 8), (1, 1, 6, 6). DOKAZ. Nenula sopstvene vrednosti grafa G ~iji je kanoni~ki graf g5 su koreni polinoma P5(λ) = λ4 − (mn+mk +ml + nk + nl + kl)λ2 − 2(mnk +mnl +mkl + nkl)λ− 3mnkl. Kako su grafovi sa parametrima (m,n, k, l) = (1, 1, 5, 9), (1, 1, 6, 7), (1, 2, 2, 2) zabraweni, dolazi se do zakqu~ka da je graf ovakvog tipa dozvoqen ukoliko jem = n = 1 i k = 4. Za graf G = g5(1, 1, 4, l) va`i da je |λ2| = 1, pa je on dozvoqen ako i samo ako je P1(−2) > 0, gde je P1(λ) = λ3 − λ2 − (6l + 8)λ− 12l. Po{to je P1(−2) = 4 graf G = g5(1, 1, 4, l) je dozvoqen za svako l ∈ N. Mo`e se tako|e zakqu~iti da |λ3| −→ 2 ako l −→ ∞. Zaista, ako se stavi da je λ3 = −2 + ε (ε > 0) va`i da je P1(−2 + ε) < 0 za dovoqno veliko l, pa je |λ3| > 2 − ε. Prema tome dokazano je da va`i da |λ2|+ |λ3| −→ 3 kada l −→∞. 2 PROPOZICIJA 1.6. Graf G = g6(m,n, k, l, p) (m ≤ p ilim = p, n ≤ l) pripada klasi E1(3) ako i samo ako (m,n, k, l, p) ima jednu od slede}ih vrednosti: (1, 1, 1, 1˙, 1˙), (1, 2, 1˙, 2, 1), (1, 1, 1˙, 3, 2), (1, 1, 9, 4, 2), (1, 1, 6, 5, 2), (1, 1, 5, 6, 2), (1, 1, 4, 12, 2), (1, 1, 3, 1˙, 2), (1, 1, 3, 2, 3), (1, 1, 2, 1˙, 3), (1, 1, 1˙, 1, 3), (1, 1, 4, 1, 4), (1, 1, 2, 3, 4), (1, 1, 2, 1, 5), (2, 1, 1˙, 1, 2), (1, 1, 1˙, 1˙, 1), (1, 3, 1˙, 1, 2). 11 DOKAZ. Lako se proverava da svi prethodno navedeni grafovi pripadaju klasi E1(3). Prema (1.1) se vidi da su nenula sopstvene vrednosti ovih grafova odre|ene jedna~inom λ4 − (mn+ nk + kl + lp)λ2 +mnkl +mnlp+ nklp = 0. Odavde sledi da se nenula sopstvene vrednosti grafa G mogu eksplicitno odrediti. S druge strane, lako je dokazati da graf G = g6(m,n, k, l, p) ∈ E1(3) ako i samo ako je 16(mnkl +mnlp+ nklp)− 36(mn+ nk + kl + lp) + 81 ≤ 0. Iz ove relacije se neposredno dobija dokaz tvr|ewa. 2 PROPOZICIJA 1.7. Graf G = g7(m,n, k, l, p) (m ≤ p) pripada klasi E1(3) ako i samo ako (m,n, k, l) ima jednu od slede}ih vrednosti: (1, 1, 1, 1˙, 1˙), (1, 1, 1˙, 1, 3), (1, 1, 3, 1, 4), (1, 1, 2, 1, 5), (1, 3, 1, 1˙, 1), (1, 4, 1, 9, 1), (1, 5, 1, 5, 1), (1, 1, 6, 1˙, 1), (1, 1, 1˙, 4, 1), (1, 1, 7, 47, 1), (1, 1, 8, 13, 1), (1, 1, 9, 9, 1), (1, 1, 11, 7, 1), (1, 1, 12, 6, 1), (1, 1, 19, 5, 1), (1, 2, 1, 1˙, 2), (1, 2, 1, 2, 3), (1, 1˙, 2, 1, 2), (1, 4, 1, 1, 3), (1, 2, 1, 1, 4), (1, 1, 7, 2, 2), (1, 1, 2, 1˙, 5), (1, 1, 2, 5, 6), (1, 3, 1, 2, 2), (1, 1, 3, 1˙, 2), (1, 1, 4, 6, 2), (1, 1, 3, 3, 3). DOKAZ. Lako se pokazuje da su nenula sopstvene vrednosti grafa G, ~iji je kanoni~ki graf g7, koreni polinoma P7(λ) = λ4 − (mn+ nk + nl + kl + lp)λ2 − 2nklλ+mnkl +mnlp+ nklp. Za proizvoqan graf G = g7(m,n, k, l, p) odre|uje se konstanta c < 0 takva da je P (c) < 0 i P (3 + c) < 0. Ako takva konstanta postoji sledi da je |λ4| < |c|, |λ2| < 3 − |c| i |λ2| + |λ3| + |λ4| < 3. Jasno je da je graf G = g7(m,n, k, l, p) dozvoqen. Na sli~an na~in kao i u Propoziciji 1.4. odre|uju se svi dozvoqeni grafovi ~iji je kanoni~ki graf g7. 2 PROPOZICIJA 1.8. Graf G = g8(m,n, k, l, p) (m ≤ n) pripada klasi E1(3) ako i samo ako (m,n, k, l, p) ima jednu od slede}ih vrednosti: 12 (1, 1, 1, 3, 1˙), (1, 1, 1, 1˙, 1), (1˙, 1˙, 1, 1, 1), (1, 1˙, 1˙, 1, 1), (1, 1, 6, 1, 1˙), (1, 1, 7, 1, 114), (1, 1, 8, 1, 30), (1, 1, 9, 1, 19), (1, 1, 10, 1, 15), (1, 1, 11, 1, 13), (1, 1, 12, 1, 12), (1, 2, 2, 1, 1˙), (1, 2, 1˙, 1, 3), (1, 2, 2, 2, 1), (1, 2, 3, 1, 8), (1, 2, 4, 1, 6), (1, 2, 5, 1, 5), (1, 2, 15, 1, 4), (1, 3, 1, 2, 1), (1, 3, 1, 1, 12), (1, 3, 2, 1, 4), (1, 4, 1, 1, 4), (1, 5, 1˙, 1, 2), (1, 5, 1, 1, 3), (1, 6, 27, 1, 2), (1, 7, 6, 1, 2), (1, 8, 3, 1, 2), (1, 10, 2, 1, 2), (1, 17, 1, 1, 2), (1, 3, 10, 1, 3), (2, 2, 1, 1, 1˙), (2, 2, 2, 1, 5), (2, 2, 3, 1, 3), (2, 3, 1˙, 1, 1), (2, 3, 1, 1, 5), (2, 3, 3, 1, 2), (2, 4, 17, 1, 1), (2, 5, 10, 1, 1), (2, 6, 7, 1, 1), (2, 8, 6, 1, 1), (2, 11, 5, 1, 1), (2, 23, 4, 1, 1), (2, 1˙, 3, 1, 1), (2, 4, 1, 1, 3), (2, 4, 2, 1, 2), (2, 8, 1, 1, 2), (3, 1˙, 2, 1, 1), (3, 3, 1, 1, 3), (3, 4, 2, 1, 2), (3, 5, 3, 1, 1), (3, 6, 1, 1, 2), (4, 14, 2, 1, 1), (5, 5, 1, 1, 2). DOKAZ. Sopstvene vrednosti grafa G ~iji je kanoni~ki graf g8 su koreni polinoma P8(λ) = λP (λ) = λ(λ4−(nk+nm+kl+kp+lp+pm)λ2−2klpλ+nklp+nklm+nlmp+klpm). Napotpuno sli~anna~inkaoiuprethodnojPropoziciji nalaze se svi dozvoqeni grafovi ~iji je kanoni~ki graf g8. 2 PROPOZICIJA 1.9. Graf G = g9(m,n, k, l, p) (k ≤ l ≤ p) pripada klasi E1(3) ako i samo ako (m,n, k, l, p) ima jednu od slede}ih vrednosti: (1, 1, 1, 1, 1˙), (3, 1˙, 1, 1, 1), (4, 1, 1, 1, 1), (1, 3, 1, 1, 2). DOKAZ. Nenula sopstvene vrednosti grafa G ~iji je kanoni~ki graf g9 su koreni polinoma P9(λ) = λ5 − (nm+ nk + nl + np+ kl + kp+ lp)λ3 − 2(nkl + nkp+ nlp+ klp)λ2 + (mnkl +mnkp+mnlp− 3nklp)λ+ 2mnklp. Po{to je graf sa parametrima (m,n, k, l, p) = (1, 1, 1, 2, 2) zabrawen, dozvoqeni su samo grafovi kod kojih je k = l = 1. Za takav graf G = g9(m,n, 1, 1, p) je λ3 = −1 pa je tada P9(λ) = (λ+ 1)P (λ) = (λ+ 1)(λ4 − λ3 − (mn+ 2n+ np+ 2p)λ2 + n(m− 3p)λ+ 2mnp). Treba odrediti konstantu c < 0 tako da je P (c) < 0 i P (2 + c) < 0. Ako takva konstanta postoji sledi da je |λ4| < |c|, |λ2| < 2− |c| i |λ2|+ |λ4| < 2, tj. |λ2|+ |λ2|+ |λ4| < 3, pa je graf dozvoqen. Ako je k = l = p = 1, tada je za graf G = g9(m,n, 1, 1, 1) i λ4 = −1, tj. P9(λ) = (λ+ 1)2P1(λ) = (λ+ 1)2(λ3 − 2λ2 − (mn− 3n)λ+ 2mn), 13 pa je graf dozvoqen ako je P1(1) = mn − 3n − 1 ≤ 0 jer je tada λ2 ≤ 1. Time je dokazano da su G = g9(3, 1˙, 1, 1, 1) i G = g9(4, 1, 1, 1, 1) dozvoqeni grafovi. 2 PROPOZICIJA 1.10. Graf G = g10(m,n, k, l, p) (k ≤ p) pripada klasi E1(3) ako i samo ako (m,n, k, l, p) ima jednu od slede}ih vrednosti: (1, 1, 1, 1, 1˙), (1, 1˙, 1, 1, 1), (1, 1, 1, 1˙, 1), (1, 5, 1, 1, 2), (1, 2, 1, 1, 3), (1, 3, 1, 2, 1), (2, 5, 1, 1, 1), (3, 1, 1, 1, 1), (1, 1, 1, 2, 3). DOKAZ. Nenula sopstvene vrednosti grafa G ~iji je kanoni~ki graf g10 su koreni polinoma P10(λ) = λ5 − (nm+ nk + np+ kl + kp+ lp)λ3 − 2(nkp+ klp)λ2 + (mnkl +mnkp+mnlp)λ+ 2mnklp. S obzirom da je graf G = g10(1, 1, 2, 1, 2) zabrawen sledi da je k = 1. Za proizvoqan graf G = g10(m,n, k, l, p) mogu se odrediti konstante c1 < 0 i c2 < 0 tako da je P (c1) > 0, P (c2) < 0 i P (3 + c1 + c2) < 0. Ako takve konstante postoje sledi da je |λ4| < |c1|, |λ3| < |c2|, |λ2| < 3 − |c1| − |c2| i |λ2| + |λ3| + |λ4| < 3, pa je graf G = g10(m,n, k, l, p) dozvoqen. Na primer, za graf G = g10(1, 5, 1, 1, 2) mo`e se izabrati c1 = −1.366, c2 = −0.366. Po{to je P10(−1.366) > 0, P10(−0.666) < 0 i P10(0.968) < 0 sledi da je |λ4| < 1.366, |λ3| < 0.666, |λ2| < 0.968 i |λ2| + |λ3| + |λ4| < 3, pa je ovaj graf dozvoqen. Primenom teoreme preplitawa dolazi se do zakqu~ka da su dozvoqeni i grafovi sa parametrima koji su mawi od ovih. S druge strane, za grafG = g10(1, 6, 1, 1, 2) va`i da je P10(−1.366) < 0, P10(−0.666) > 0 i P10(0.968) > 0, pa je |λ4| > 1.366, |λ3| > 0.666, |λ2| > 0.968 i |λ2| + |λ3| + |λ4| > 3, pa je ovaj graf zabrawen. Primenom ponovo teoreme preplitawa sledi da su svi grafovi sa parametrima koji su ve}i od ovih tako|e zabraweni. Na sli~an na~in se odre|uju ostali dozvoqeni grafovi ~iji je kanoni~ki graf g10 i p 6= 1. U slu~aju kada je k = p = 1 va`i λ4 = −1, pa je P10(λ) = (λ+ 1)P (λ) = (λ+ 1)(λ4 − λ3 − (mn+ 2n+ 2l)λ2 +mnλ+ 2mnl). Tada, kao u dokazu prethodnog tvr|ewa (Propozicije 1.9.), treba odrediti konstantu c < 0 tako da je P (c) < 0 i P (2 + c) < 0. 2 PROPOZICIJA 1.11. Graf G = g11(m,n, k, l, p) (m ≤ n ilim = n, k ≤ p) pripada klasi E1(3) ako i samo ako (m,n, k, l, p) ima jednu od slede}ih vrednosti: (1, 1˙, 1, 1, 1), (1, 1, 1, 1˙, 1), (1, 1, 1, 1, 1˙), (1, 1, 1, 2, 7), (1, 1, 1, 4, 2), (1, 2, 1, 2, 1). DOKAZ. Nenula sopstvene vrednosti grafa G ~iji je kanoni~ki graf g11 su koreni polinoma P11(λ) = λ5 − (lp+ lk + pm+ pn+ pk +mn+mk + nk)λ3 − 2(lpk + pmn+ pmk + pnk +mnk)λ2 + (lpmn+ lmnk − 3pmnk)λ+ 2lpmnk. 14 S obzirom da su grafovi G = g11(2, 2, 1, 1, 1) i G = g11(1, 1, 2, 1, 2) zabraweni sledi da je m = k = 1. Tako|e su zabraweni i grafovi sa parametrima (m,n, k, l, p) = (1, 1, 1, 2, 8), (1, 1, 1, 5, 2), (1, 2, 1, 3, 1), (1, 3, 1, 2, 1) pa su dozvoqeni oni sa parametrima (m,n, k, l, p) = (1, 1, 1, 2, 7), (1, 1, 1, 4, 2), (1, 2, 1, 2, 1). Na sli~an na~in kao u Propozi- ciji 1.9. dokazuje se da su dozvoqeni grafovi sa parametrima (m,n, k, l, p) = (1, 1˙, 1, 1, 1), (1, 1, 1, 1˙, 1), (1, 1, 1, 1, 1˙), ~ime je dokazano tvr|ewe. 2 PROPOZICIJA 1.12. Graf G = g12(m,n, k, l, p) (l ≤ p) pripada klasi E1(3) ako i samo ako (m,n, k, l, p) ima jednu od slede}ih vrednosti: (1, 1, 1˙, 1, 1), (1, 1, 1, 1, 2), (1, 2, 3, 1, 1), (1, 3, 1, 1, 1). DOKAZ. Lako je videti da su nenula sopstvene vrednosti grafa G ~iji je kanoni~ki graf g12 koreni polinoma P12(λ) = λ5−(nm+nk+kl+kp+lp)λ3−2klpλ2+(mnkl+mnkp+mnlp+nklp)λ+2mnklp, kao i da su grafovi sa parametrima (m,n, k, l, p) = (1, 1, 1, 1, 3), (1, 4, 1, 1, 1), (1, 3, 2, 1, 1) i (1, 2, 4, 1, 1) zabraweni. Za graf G = g12(1, 1, k, 1, 1) polinom postaje P (λ) = (λ2 − 1)(λ3 − (3k + 1)λ− 2k). S obzirom da je |λ2| = |λ4| = 1, graf G je dozvoqen ako i samo ako je |λ3| ≤ 1. Kako je P (0) = 2k > 0 i P (−23) = − 50243 < 0 sledi da je −23 < λ3 < 0, odnosno da je graf G = g12(1, 1, k, 1, 1) dozvoqen za svako k ∈ N. 2 PROPOZICIJA 1.13. Graf G = g13(m,n, k, l, p) (m ≤ k ilim = k i n ≤ l pripada klasi E1(3) ako i samo ako (m,n, k, l, p) ima jednu od slede}ih vrednosti: (1, 1, 1˙, 1, 1), (1, 1, 1, 4, 1), (1, 1, 1, 1, 1˙), (2, 1, 3, 1, 1). DOKAZ. Nenula sopstvene vrednosti grafa G ~iji je kanoni~ki graf g13 su koreni polinoma P13(λ) = λ5 − (nm+ np+mk +mp+ kl + kp+ lp)λ3 − 2(mnp+mkp+ klp)λ2 + (mnkl + nklp+mnlp)λ+ 2mnklp. S obzirom da je graf sa parametrima (m,n, k, l, p) = (1, 2, 1, 2, 1) zabrawen, mora da va`i n = 1. Zabraweni su i grafovi sa parametrima (m,n, k, l, p) = (2, 1, 4, 1, 1), (1, 1, 1, 5, 1) pa su dozvoqeni grafovi G = g13(2, 1, 3, 1, 1) i G = g13(1, 1, 1, 4, 1). Na sli~an na~in kao u Propoziciji 1.10. dokazuje se da su dozvoqeni grafovi sa parametrima (m,n, k, l, p) = (1, 1, 1˙, 1, 1) i (1, 1, 1, 1, 1˙) pa je tako tvr|ewe dokazano. 2 PROPOZICIJA 1.14. Graf G = g14(m,n, k, l, p)m ≤ n, l ≤ p pripada klasi E1(3) ako i samo ako je (m,n, k, l, p) = (1, 1, 1˙, 1, 1). 15 DOKAZ. Nenula sopstvene vrednosti grafa G ~iji je kanoni~ki graf g14 su koreni polinoma P14(λ) = λ5 − (nm+mk + nk + kl + kp+ lp)λ3 − 2(mnk + klp)λ2 + (mnkl +mnkp+mnlp+mklp+ nklp)λ+ 4mnklp. Po{to je graf sa parametrima (m,n, k, l, p) = (1, 1, 1, 1, 2) zabrawen, graf posmatranog oblika je dozvoqen samo ukoliko jem = n = l = p = 1. Za graf G = g14(1, 1, k, 1, 1) je P (λ) = (λ− 1)(λ+ 1)2(λ2 − λ− 4k), tj. |λ2| = |λ3| = |λ4| = 1, {to zna~i da je dozvoqen za svako k ~ime je tvr|ewe dokazano. 2 PROPOZICIJA 1.15. Graf G = g15(m,n, k, l, p) (m ≤ n ≤ k ≤ l ≤ p) pripada klasi E1(3) ako i samo ako je (m,n, k, l, p) = (1, 1, 1, 1, 1˙). DOKAZ. Nenula sopstvene vrednosti grafa G ~iji je kanoni~ki graf g15 su koreni polinoma P15(λ) = λ5 − (nm+mk +ml +mp+ nk + nl + np+ kl + kp+ lp)λ3 − 2(mnk +mnl +mnp+mkl +mkp+mlp+ nkl + nkp+ nlp+ klp)λ2 − 3(mnkl +mnkp+mnlp+mklp+ nklp)λ− 4mnklp. Po{to je graf sa parametrima (m,n, k, l, p) = (1, 1, 1, 2, 2) zabrawen, graf posmatranog oblika je dozvoqen samo ukoliko jem = n = k = l = 1. Za graf G = g15(1, 1, 1, 1, p) je P (λ) = (λ+ 1)3(λ2 − 3λ− 4p), tj. |λ2| = |λ3| = |λ4| = 1, {to zna~i da je dozvoqen za svako p ~ime je tvr|ewe dokazano. 2 PROPOZICIJA 1.16. Graf G = g16(m,n, k, l, p) (m ≤ n ≤ k ≤ l ≤ p) pripada klasi E1(3) ako i samo ako je (m,n, k, l, p) = (1, 1, 1, 1, 1). DOKAZ. Po{to je odgovaraju}i graf zabrawen ako je (m,n, k, l, p, q) = (1, 1, 1, 1, 2), tvr|ewe je dokazano. 2 PROPOZICIJA 1.17. Graf G = g17(m,n, k, l, p, q) (m ≤ q) pripada klasi E1(3) ako i samo ako (m,n, k, l, p, q) ima jednu od slede}ih vrednosti: (1, 1, 1, 1, 3, 1), (1, 1, 1, 2, 1, 1). DOKAZ. Po{to su grafovi sa parametrima (m,n, k, l, p, q) = (1, 1, 1, 1, 4, 1), (1, 1, 1, 3, 1, 1), (1, 2, 1, 1, 2, 1) i (1, 1, 1, 2, 2, 1) zabraweni, tvr|ewe je dokazano. 2 16 PROPOZICIJA 1.18. Graf G = g18(m,n, k, l, p, q) (l ≤ p, k ≤ q) pripada klasi E1(3) ako i samo ako (m,n, k, l, p, q) ima jednu od slede}ih vrednosti: (1, 1, 1, 1, 3, 1˙), (1, 1, 2, 1, 1, 1˙), (1, 1, 1, 1, 6, 1), (1, 1, 1, 2, 2, 1), (1, 1, 1, 1, 4, 2), (1, 1, 3, 1, 1, 3). DOKAZ. Sopstvene vrednosti grafa G ~iji je kanoni~ki graf g18 su koreni polinoma P18(λ) = λ2(λ4 − (nm+ nk + nq + kl + kq + lp+ pq)λ2 − 2nkqλ + mnkl +mnkq +mnlp+mnpq + nklp+ nklq + nkpq + nlpq). S obzirom da su grafovi sa parametrima (m,n, k, l, p, q) = (2, 1, 1, 1, 1, 1), (1, 2, 1, 1, 1, 1) zabraweni, mora da va`i da je m = n = 1. Na sli~an na~in kao u Propoziciji 1.4. odre|uju se svi dozvoqeni grafovi ~iji je kanoni~ki graf g18. 2 PROPOZICIJA 1.19. Graf G = g19(m,n, k, l, p, q) (p ≤ q) pripada klasi E1(3) ako i samo ako je (m,n, k, l, p, q) = (1, 1, 1, 1, 1, 1). DOKAZ. Po{to je odgovaraju}i graf zabrawen ako je bilo koji od parametara m,n, k, l ili q jednak dva, tvr|ewe je dokazano. 2 PROPOZICIJA 1.20. Graf G = g20(m,n, k, l, p, q) (m ≤ l) pripada klasi E1(3) ako i samo ako je (m,n, k, l, p, q) = (1, 1, 1, 2, 1, 1). DOKAZ. Po{to su grafovi sa parametrima (m,n, k, l, p, q) = (1, 1, 1, 3, 1, 1), (2, 1, 1, 2, 1, 1) i (1, 1, 2, 1, 1, 1) zabraweni, tvr|ewe je dokazano. 2 PROPOZICIJA 1.21. Graf G = g21(m,n, k, l, p, q) (p ≤ q) pripada klasi E1(3) ako i samo ako (m,n, k, l, p, q) ima jednu od slede}ih vrednosti: (1, 4, 1, 1, 1, 1), (1, 1, 3, 1, 1, 1), (1, 1, 1, 2, 1, 1). DOKAZ. S obzirom da su grafovi sa parametrima (m,n, k, l, p, q) = (2, 1, 1, 1, 1, 1) i (1, 1, 1, 1, 1, 2) zabraweni sledi da je m = p = q = 1. Tako|e su zabraweni i grafovi kod kojih su parametri (m,n, k, l, p, q) = (1, 5, 1, 1, 1, 1), (1, 1, 4, 1, 1, 1), (1, 1, 1, 3, 1, 1), (1, 2, 2, 1, 1, 1), (1, 2, 1, 2, 1, 1) i (1, 1, 2, 2, 1, 1), pa je tvr|ewe dokazano. 2 PROPOZICIJA 1.22. Graf G = g22(m,n, k, l, p, q) (m ≤ n ≤ k ≤ l ≤ p ≤ q) pripada klasi E1(3) ako i samo ako je (m,n, k, l, p, q) = (1, 1, 1, 1, 1, 1). DOKAZ. Po{to je graf sa parametrima (m,n, k, l, p, q) = (1, 1, 1, 1, 1, 2) zabrawen tvr|ewe je dokazano. 2 17 PROPOZICIJA 1.23. Graf G = g23(m,n, k, l, p, q) pripada klasi E1(3) ako i samo ako je (m,n, k, l, p, q) = (1, 1, 1, 1, 1, 1). DOKAZ. Po{to je odgovaraju}i graf zabrawen ako je bilo koji od parametara m, n, k, l, p, q jednak dva, tvr|ewe je dokazano. 2 PROPOZICIJA 1.24. Graf G = g24(m,n, k, l, p, q) (p ≤ q, p = q im ≤ n ≤ k ≤ l) pripada klasi E1(3) ako i samo ako je (m,n, k, l, p, q) = (1, 1, 1, 1, 1, 4). DOKAZ. Po{to su grafovi sa parametrima (m,n, k, l, p, q) = (1, 1, 1, 2, 1, 1) i (1, 1, 1, 1, 1, 5) zabraweni, tvr|ewe je dokazano. 2 Teorema 1.5. i Propozicije 1.1.− 1.24. kompletno opisuju klasu E1(3), tj. klasu svih povezanih grafova ~ija tre}a redukovana energija ne prelazi 3. 1.3 O predukovanoj energiji grafa U ovom odeqku se posmatraju samo prosti povezani grafovi. Oznake su iste kao i do sada, tj. skup ~vorova grafa G ozna~en je sa V (G), a wegov red sa |G|. Spektar takvog grafa je skup λ1 ≥ λ2 ≥ . . . ≥ λn sopstvenih vrednosti wegove 0− 1 matrice susedstva. Neka je N0 skup svih nenegativnih celih brojeva i l ∈ N0 fiksiran broj. Za neki graf G, za koji je |G| = n > l, suma Sl+(G) = |λ1| + |λ2| + . . . + |λn−l| se naziva lpozitivna redukovana energija grafaG [15]. Suma Sl+(G, p) = |λ1|p+ |λ2|p+ . . .+ |λn−l|p, gde je p ∈ N, je nazvana pta lpozitivna redukovana energija grafa G. Za proizvoqno realno a ≥ 1, proizvoqno l ∈ N0 i p ∈ N, posmatra se klasa grafova El+(p, a) = {G : Sl+(G, p) ≤ a}. TEOREMA 1.6. [8] Za svaku realnu konstantu a ≥ 1 i bilo koje fiksirano l ∈ N0 i p ∈ N, skup povezanih grafova El+(p, a) = {G : |λ1|p + . . .+ |λn−l|p ≤ a} je kona~an. DOKAZ. Neka je a ≥ 1 proizvoqna realna konstanta i l nenegativan ceo broj. Neka je G proizvoqan graf reda n > l iz klase El+(p, a). Tada je Sl+(G, p) = |λ1|p + . . .+ |λn−l|p ≤ a, (1.2) pa je ∑ |λi|≥1 |λi|p ≤ n−l∑ i=1 |λi|p + n∑ i=n−l+1 |λi|p ≤ a+ n∑ i=n−l+1 |λ1|p = a+ l · |λ1|p ≤ a(l + 1). (1.3) Iz relacija (1.2) i (1.3) se dobija 18 2(n− 1) ≤ 2m = n∑ i=1 |λi|2 ≤ ∑ |λi|<1 |λi|+ ∑ |λi|≥1 |λi|p ≤ (n− 1) · 1 + a · (l + 1), (1.4) gde je m broj grana grafa G. Iz relacije (1.4) sledi da je n ≤ a(l + 1) + 1, odakle se neposredno dobija tvr|ewe. 2 Neka su daqe k, l ∈ N0 i p ∈ N proizvoqni fiksirani brojevi. Za proizvoqni graf G kod koga je |G| = n > k + l, suma Slk = |λk+1| + |λk+2| + . . . + |λn−l| se naziva (k, l) redukovana energija grafa G. Suma Slk(G, p) = |λk+1|p + |λk+2|p + . . .+ |λn−l|p se naziva pta (k, l)redukovana energija grafaG. Za proizvoqnu realnu konstantu a > 0, k, l ∈ N0 i p ∈ N, mo`e se posmatrati klasa grafova Elk(p, a) = {G : Slk(G, p) ≤ a}. Mo`e se primetiti da je pta (0, k)redukovana energija grafa G pta kpozitivna redukovana energija grafa G. Mo`e se uvek pretpostaviti da je k, l ∈ N0 i p ∈ N. S obzirom da kompletan bipartitan graf Km,n pripada klasi E l k(p, a) za svako m,n ∈ N, sledi da je klasa Elk(p, a) uvek beskona~na. Kasnije }e biti dokazana va`na osobina ove vrste energije na skupu svih kanoni~kih grafova. Zbog toga, za svako realno a > 0 i k, l, p ∈ N, posmatra se klasa odgovaraju}ih kanoni~kih grafova E˜lk(p, a) = {G : G ∈ Elk(p, a) je kanoni~ki graf}. Ako je k = l, tada se Skk (p, a), E k k (p, a), E˜ k k (p, a) jednostavno ozna~ava sa Sk(p, a), Ek(p, a) i E˜k(p, a), redom. Sada se navodi dokaz va`ne osobine klase E˜k(p, a) (a > 0, k, p ∈ N) koji je baziran na dve teoreme dokazane u [21]. TEOREMA 1.7. [8] Za svaku realnu konstantu a > 0 i sve k, p ∈ N, skup povezanih grafova E˜k(p, a) je kona~an. DOKAZ. Pretpostavimo suprotno, da postoji neka konstanta a > 0 i k, p ∈ N tako da je skup E˜k(p, a) beskona~an. Tada, prema teoremi dokazanoj u [21], za svaki realan broj A > 0, postoji graf G ∈ E˜k(p, a), koji ima q > A nenula sopstvenih vrednosti. Za ovaj graf va`i relacija |λk+1|p + |λk+2|p + . . .+ |λn−k|p ≤ a. (1.5) Neka va`i pretpostavka da je λr > λr+1 = . . . = λr+s = 0 > λr+s+1, gde je s = n − q vi{estrukost nule kao sopstvene vrednosti ovog grafa. Tada je odgovaraju}i karakteristi~ni polinom grafa G Pn(λ) = λs(λq + a1λq−1 + . . .+ aq), gde je |aq| = λ1 · . . . · λr · |λr+s+1| · . . . · |λn|. Prema teoremi tako|e dokazanoj u [21], pretpostavqa se da je s = 0 {to daje n = q. Tako|e, mo`e se pretpostaviti da je za n dovoqno veliko √ n ≥ a+ 6k. 19 Jasno je da je |λi| ≤ n− 1 za i ∈ {1, 2, . . . , k} ∪ {n− k+ 1, n− k+ 2, . . . , n}, a |λi| ≤ √ n za i = k + 1, k + 2, . . . , n− k. Neka je sa t ozna~en ukupan broj sopstvenih vrednosti λi, takvih da je |λi| ≤ 1/ √ n (i = k+ 1, k+ 2, . . . , n− k). Lako je pokazati da je t > a+ 4k. Zaista, u suprotnom slu~aju postojalo bi najmawe n− (2k + t) sopstvenih vrednosti λi (k + 1 ≤ i ≤ n− k) tako da je |λi| > 1/ √ n. Relacija (1.5) daje a ≥ n−k∑ i=k+1 |λi|p > n− (2k + t)√ n > √ n− a+ 6k√ n . (1.6) Po{to je √ n ≥ a+6k i va`i relacija (1.6) dobija se a > √n−1{to je u kontradikciji sa pretpostavkom. Neka je daqe t0 ukupan broj sopstvenih vrednosti λi(i = k+ 1, k+ 2, . . . , n− k) takvih da je |λi| > 1. Kori{}ewem relacije (1.5) dobija se a ≥ |λk+1|p + . . .+ |λn−k|p ≥ ∑ |λi|>1 |λi|p ≥ t0, (1.7) odakle sledi da je t0 ≤ a. Sada se kona~no dobija |an| = (|λ1| · . . . · |λk|)(|λk+1| · . . . · |λn−k|)(|λn−k+1| · . . . · |λn|) ≤ ≤ (n− 1)2k√n · √n · . . . · √n︸ ︷︷ ︸ t0 · 1√ n · 1√ n · . . . · 1√ n︸ ︷︷ ︸ t ·1 · 1 · . . . · 1︸ ︷︷ ︸ n−(t+t0+2k) < 1, {to je kontradikcija (|an| ∈ N , an 6= 0). Prema tome, skup E˜k(p, a) je kona~an za svako a > 0 i svako k, p ∈ N. 2 POSLEDICA 1.1. Za svaku realnu konstantu a > 0 i k, l, p ∈ N, skup povezanih grafova E˜lk(p, a) je kona~an. DOKAZ. Ne smawuju}i op{tost dokaza neka je k ≥ l. Neka je G proizvoqan graf iz skupa E˜lk(p, a). Tada iz relacije a ≥ n−l∑ i=k+1 |λi|p = n−k∑ i=k+1 |λi|p + n−l∑ i=n−k+1 |λi|p ≥ n−k∑ i=k+1 |λi|p, sledi da je G ∈ E˜k(p, a), tj. E˜lk(p, a) ⊆ E˜k(p, a). Kako je skup E˜k(p, a) kona~an za svako a > 0 i svako k, p ∈ N, sledi da je skup E˜lk(p, a) tako|e kona~an za svako a > 0 i svako k, l, p ∈ N ~ime je tvr|ewe dokazano. 2 Glava 2 Odre|ivawe svih kona~nih i beskona~nih grafova sa sedam sopstvenih vrednosti razli~itih od nule Uradovima [21] i [22]A.Torga{ev je opisao sve kona~ne i beskona~ne povezane grafove koji imaju 3, 4 ili 5 sopstvenih vrednosti razli~itih od nule (ukqu~uju}i tako|e i wi- hove vi{estrukosti). U tim radovima on je tako|e dao i op{ti metod opisivawa svih povezanih grafova sa bilo kojim fiksiranim brojem sopstvenih vrednosti razli~itih od nule. U radovima [12] i [14]M.Lepovi} je, primewuju}i pomenuti metod, opisao sve kona~ne i beskona~ne povezane grafove koji imaju ta~no 6 sopstvenih vrednosti razli~itih od nule (ukqu~uju}i i wihove vi{estrukosti), a dat je i skup svih maksimalnih kanoni~kih grafova koji imaju 6 sopstvenih vrednosti razli~itih od nule. Ovo poglavqe ima tri odeqka. Osnovni pojmovi i definicije koje se odnose na spektralnu teoriju kanoni~kih grafova dati su u odeqku 2.1 i poti~u iz radova [21] i [22]. U odeqku 2.2 su opisani svi kona~ni i beskona~ni grafovi sa 7 sopstvenih vrednosti razli~itih od nule. Odeqak 2.3 sadr`i kondenzovane rezultate dobijene u prethodnom razmatrawu, tj. navodi se skup svih maksimalnih kanoni~kih grafova koji imaju 7 sopstvenih vrednosti razli~itih od nule. 2.1 Osnovni pojmovi i definicije Posmatraju se povezani prebrojivo beskona~ni grafovi bez petqi i vi{estrukih grana. Skup ~vorova V (G) grafa G je skup prirodnih brojeva N. Matrica susedstva A(G) grafa G je matrica A(G) = [aij ] beskona~nog reda N× N, gde je 20 21 aij = { ai+j−2, (i,j) susedni; 0, (i,j) nisu susedni i a je konstanta iz intervala I = (0, 1). Od posebnog interesa su beskona~ni grafovi sa kona~nim spektrom σ(G) = {λ1, λ2, . . . , λp, 0, 0, . . .}. U ovom slu~aju λ = 0 je sopstvena vrednost beskona~ne mnogostrukosti. DEFINICIJA 2.1. ([21], [22]) Neka je G beskona~an graf sa spektrom σ(G) = {λ1, λ2, . . . , λp; 0} (λi 6= 0 za i ∈ {1, 2, . . . , p}). Tada je G graf sa p  kona~nim spektrom. DEFINICIJA 2.2. ([21], [22]) Graf G je kona~nog tipa ako i samo ako se skup V (G) = N mo`e razbiti na kona~an skup disjunktnih N1, N2, . . . , Nk karakteristi~nih skupova, tako da su bilo koja dva ~vora iz istog skupaNi nesusedna i bilo koja dva podskupaNi iNj su kompletno susedna ili kompletno nesusedna. Kao i u prethodnom poglavqu i ovde se koristi pojam kanoni~ki graf. Na skupu ~vorova V (G) uvodi se relacija ekvivalencije. Za dva ~vora x, y ∈ V (G) se ka`e da su ekvivalentna (u relaciji) u grafu G, u oznaci x ∼ y, ako i samo ako imaju iste susede. TEOREMA 2.1. ([21], [22]) Kanoni~ki graf g grafa G ima slede}e osobine: (i) Beskona~an graf kona~nog tipa k ima p  kona~an spektar, gde je p = p(G) ≤ k. (ii) Svaki graf sa p  kona~nim spektrom je kona~nog tipa k, gde je k ≤ 2p − 1. (iii) Ako je G = g(N1, N2, . . . , Nk) graf kona~nog tipa, onda je broj sopstvenih vred- nosti razli~itih od nule p(G) grafa G jednak broju sopstvenih vrednosti razli~itih od nule p(g) grafa g. Time se problem odre|ivawa svih beskona~nih grafova sa p sopstvenih vrednosti razli~itih od nule upravo svodi na problem nala`ewa svih kanoni~kih grafova tako|e sa p sopstvenih vrednosti razli~itih od nule. Sa g0 ozna~imo bazni podgraf grafaG sa p ~vorova koji ima svojstvo da su mu kolone (vektori) matrice susedstva A(g0) linearno nezavisne. TEOREMA 2.2. ([21], [22]) Bazni podgraf g0 grafa G ima slede}e osobine: (i) Graf g0 nema izolovanih ~vorova. (ii) Svaki ~vor x ∈ V (G) \ V (g0) je susedan bar jednom ~voru y ∈ V (g0). (iii)Matrica susedstva A(g0) grafa g0 je regularna. U slede}em odeqku dati su osnovni rezultati koji se odnose na problem odre|ivawa kanoni~kih grafova sa 7 sopstvenih vrednosti razli~itih od nule. 22 2.2 Kanoni~ki grafovi koji imaju sedam sopstvenih vrednosti razli~itih od nule Neka je T (7) oznaka skupa svih neizomorfnih grafova sa ta~no 7 sopstvenih vred- nosti razli~itih od nule, a Tc(7) oznaka skupa svih kanoni~kih grafova koji pripadaju skupu T (7). S obzirom da je, prema navedenoj teoremi (2.1.), broj sopstvenih vrednosti ra- zli~itih od nule n(g) kanoni~kog grafa g jednak broju sopstvenih vrednosti razli~itih od nule n(G) grafa G (graf g je kanoni~ki graf grafa G), jasno je da se skup T (7) mo`e generisati pomo}u skupa kanoni~kih grafova Tc(7). U radovima [21] i [22] je tako|e dokazano da je klasa Tc(7) kona~na. Dokazano je, u stvari, da svaki graf g ∈ Tc(7) sadr`i indukovan podgraf H sa 7 ~vorova koji tako|e pripada skupu Tc(7). Takav podgraf nema nulu u spektru i naziva se "jezgro" grafa g ili "bazni graf" grafa g. Neka je χ7 skup svih baznih grafova sa 7 ~vorova. Kako je χ7 ⊆ Tc(7), jasno je da je skup χ7 kona~an. O~igledno je da graf G mo`e imati razli~ita jezgra. Kako je svaki ~vor x ∈ V (g) \ V (H) susedan bar jednom ~voru y ∈ V (H) i bilo koja dva ~vora a, b ∈ V (g) nemaju iste susede, sledi da je |g| ≤ 27 − 1. Prema tome, jasna je metoda za generisawe skupa svih kanoni~kih grafova koji imaju 7 sopstvenih vrednosti razli~itih od nule. Polazi se od skupa baznih grafova, i za bilo koji fiksirani bazni grafH , primewuje se metod ekstenzije dodavawem novih ~vorova tako da je novi ~vor x susedan bar nekom od ~vorova baznog grafa H i bilo koja dva nova ~vora nemaju iste susede. Ispitivawem svih mogu}ih kombinacija "susedstva" novog ~vora x sa ~vorovima baznog grafa H i ve} dodatih ~vorova, generi{u se kanoni~ki grafovi koji pripadaju skupu Tc(7). Navedena procedura je kona~na. Ovako je opisana metoda za generisawe skupa svih kanoni~kih grafova koji imaju 7 sopstvenih vrednosti razli~itih od nule. Pretra`ivawem spektara svih povezanih grafova sa 7 ~vorova (postoji ta~no 853 takva grafa, videti [2]), lako se utvr|uje da postoji ta~no 342 kanoni~ka grafa koji nemaju nulu u spektru. Dakle, postoji ta~no 342 bazna grafa iz klase Tc(7) koji su dati u Prilogu (Lista 1, str. 48). Upotrebom kompjuterskog programa za navedeni metod ekstenzije 342 bazna grafa, posle du`eg rada dobijena je kompletna lista svih kanoni~kih neizomorfnih grafova sa ta~no 7 sopstvenih vrednosti razli~itih od nule, ~ime je navedeni problem za kona~ne i beskona~ne grafove potpuno re{en. Tako je dobijen glavni rezultat u ovom poglavqu. TEOREMA 2.3. Postojita~no 23413 neizomorfnih povezanih kanoni~kih grafova koji imaju 7 sopstvenih vrednosti razli~itih od nule. S obzirom na broj dobijenih grafova umesto kompletne liste u Prilogu (str. 56) se navodi Lista 2 sa statisti~kim podacima o dobijenim neizomorfnim povezanim kanoni~kim grafovima koji imaju 7 sopstvenih vrednosti razli~itih od nule. Ovde je data Lista 2.1 svih kanoni~kih grafova sa 7 sopstvenih vrednosti razli~itih od nule. 23 Lista 2.1 KANONI^KI GRAFOVI SA SEDAM SOPSTVENIH VREDNOSTI RAZLI^ITIH OD NULE n m k n m k n m k n m k n m k 7 7 6 13 83 30 52 24 34 39 173 8 17 14 166 31 35 25 75 40 146 9 37 15 276 32 13 26 123 41 140 10 52 16 370 33 9 27 174 42 126 11 60 17 445 34 1 28 247 43 90 12 57 18 468 36 1 29 318 44 64 13 45 19 463 37 1 30 397 45 57 14 31 20 396 31 399 46 26 15 19 21 290 11 17 3 32 407 47 17 16 10 22 193 18 8 33 367 48 18 17 4 23 124 19 34 34 330 49 5 18 2 24 82 20 68 35 311 50 8 19 1 25 39 21 145 36 280 51 6 21 1 26 21 22 231 37 174 52 6 27 7 23 376 38 137 53 1 8 8 1 28 3 24 479 39 82 9 13 29 1 25 568 40 52 14 35 7 10 36 30 2 26 645 41 32 36 11 11 88 27 597 42 28 37 21 12 130 10 13 2 28 553 43 21 38 30 13 193 14 8 29 551 44 15 39 50 14 216 15 30 30 442 45 6 40 56 15 214 16 71 31 337 46 5 41 58 16 177 17 161 32 227 48 1 42 54 17 135 18 263 33 138 43 74 18 90 19 423 34 85 13 28 6 44 59 19 48 20 553 35 65 29 14 45 65 20 29 21 633 36 45 30 30 46 49 21 9 22 614 37 33 31 54 47 54 22 3 23 660 38 14 32 94 48 53 23 1 24 600 39 8 33 110 49 45 24 1 25 470 40 3 34 122 50 20 26 350 45 1 35 160 51 24 9 10 1 27 212 36 197 52 17 11 8 28 132 12 22 4 37 190 53 12 12 28 29 106 23 12 38 177 54 6 24 n m k n m k n m k n m k n m k 55 4 47 22 59 5 57 5 17 62 1 56 1 48 20 60 5 58 3 63 1 57 2 49 19 61 3 59 1 64 3 58 2 50 16 62 3 60 2 65 3 59 2 51 15 63 2 61 3 70 1 60 1 52 14 67 2 62 4 71 1 61 1 53 15 63 8 72 3 54 17 16 52 3 64 9 15 43 6 55 19 53 2 68 2 18 73 2 44 7 56 16 54 5 69 1 81 1 45 9 57 6 55 6 70 1 46 15 58 2 56 10 Slog Liste 2.1 predstavqen je u obliku n m k gde je n broj ~vorova grafa,m je broj wegovih grana, a k je broj neizomorfnih grafova sa 7 nenula sopstvenih vrednosti koji imaju n ~vorova im grana. Napomenimo da lista sadr`i: sa 7 ~vorova : 342 grafa, sa 8 ~vorova : 1384 grafa, sa 9 ~vorova : 3466 grafova, sa 10 ~vorova : 5400 grafova, sa 11 ~vorova : 5656 grafova, sa 12 ~vorova : 4031 graf, sa 13 ~vorova : 2037 grafova, sa 14 ~vorova : 778 grafova, sa 15 ~vorova : 238 grafova, sa 16 ~vorova : 65 grafova, sa 17 ~vorova : 13 grafova, sa 18 ~vorova : 3 grafa. 2.3 Maksimalni kanoni~ki grafovi koji imaju sedam sopstvenih vrednosti razli~itih od nule U prethodnom odeqku su opisani svi kona~ni i beskona~ni grafovi koji imaju ta~no 7 sopstvenih vrednosti razli~itih od nule. U ovom su odeqku kondenzovani rezultati koji su dobijeni u prethodnom razmatrawu, tj. navodi se skup svih maksimalnih kanoni~kih grafova koji imaju 7 sopstvenih vred- nosti razli~itih od nule. 25 Za graf g ∈ Tc(7) }emo re}i da je maksimalan ako i samo ako nijedan wegov nadgraf ne pripada skupu Tc(7) (tj. bilo koji wegov nadgraf ili nema 7 sopstvenih vrednosti razli~itih od nule ili nije kanoni~ki). Koriste}i program za izdvajawe maksimalnih kanoni~kih grafova iz skupa Tc(7) dobija se slede}i rezultat. TEOREMA 2.4. Postoji ta~no 183 maksimalna kanoni~ka grafa sa 7 sopstvenih vrednosti razli~itih od nule. Svi ovi grafovi su predstavqeni u Listi 2.2. Navedeni grafovi imaju 7, 8, . . . , 16, 18 ~vorova. Slog Liste 2.2 svih maksimalnih kanoni~kih grafova sa 7 nenula sopstvenih vred- nosti predstavqen je u obliku n1 n2 n3 a1 a2 a3 . . . an2 , gde je n1 redni broj maksimalnog grafa, n2 je broj wegovih ~vorova, n3 je broj wegovih grana, a niz a1, a2, a3, . . ., an2 predstavqa niz vrsta matrice susedstva grafa. Zbog kra}eg i preglednijeg zapisa izvr{ena je konverzija vrsta matrice susedstva iz binarnog u heksadecimalni zapis. Lista 2.2 MAKSIMALNI KANONI^KI GRAFOVI SA SEDAM SOPSTVENIH VREDNOSTI RAZLI^ITIH OD NULE 001 18 73 00080 00840 008C0 0351E 05633 0632D 1803F 063AD 0359E 056B3 28747 180BF 03D5E 06B6D 05E73 05EF3 06BED 03DDE 002 18 73 00040 08E33 12783 03A99 0D83C 06C96 1718C 19329 1C526 08E73 0D87C 201BF 127C3 171CC 06CD6 03AD9 19369 1C566 003 18 81 080FF 00F1F 20F0F 03373 055B5 069D9 19636 1AA5A 1CC9C 1F0F0 23363 255A5 269C9 37F00 39626 3AA4A 3CC8C 3F0E0 004 16 52 0100 2221 4448 0096 0196 2321 4548 8E0F 187D 22B7 44DE 18EB 23B7 19EB 197D 45DE 005 16 56 0100 0065 060A 070A 0165 32D6 34B9 981F 066F 4CB9 4AD6 076F 33D6 4DB9 35B9 4BD6 006 16 64 207F 02BF 838F 0DD3 15D5 1AB9 6476 3879 7C70 9B89 C786 DF80 E546 EA2A F22C FD40 007 16 64 047F 149F 0BA7 49AB 3355 C372 2C6D 3C8D 7159 8EA6 B654 CCAA D392 EB60 F458 FB80 008 16 68 2000 0B1F 80FD 0D4F 52B3 1397 4C6B 54E3 2D4F 3397 2B1F 6C6B 72B3 74E3 5FFC 7FFC 009 15 43 0201 000C 0862 1190 020D 4532 0A63 086E 119C 1391 0A6F 24D7 24DB 139D 453E 010 15 44 0005 0028 0B10 10C2 002D 10EA 10C7 0B38 0B15 269E 10EF 26B3 4573 0B3D 455E 011 15 46 0401 0208 0066 0609 4898 2916 026E 0467 11B3 11D5 066F 2D17 13BB 13DD 48FE 26 012 15 47 0024 0108 00C3 012C 01CB 00E7 2C13 1655 16B2 4A5D 01EF 2C37 4ABA 175D 17BA 013 15 49 0801 1081 200E 40F0 033A 0556 066C 280F 0B3B 0D57 0E6D 15D7 13BB 16ED 60FE 014 15 49 1002 00E1 411C 0635 0A8D 0C59 10E3 2572 23A6 29CA 1A8F 1637 1C5B 41FD 2F1E 015 15 50 0110 0C6A 0E8A 3285 3065 19C9 428F 1B29 2636 24D6 406F 3395 0D7A 3175 0F9A 016 15 51 0011 14C6 2B28 1706 28E8 194B 1A9A 2565 26B4 14D7 416F 1717 28F9 2B39 42BE 017 15 51 0082 0B25 0D61 321C 1315 2C68 3458 407F 1397 329E 0DE3 0BA7 2CEA 40FD 34DA 018 15 52 081C 1541 22A2 4543 29C6 11AD 2E52 1639 2D2A 12D5 41AF 42D7 463B 1D5D 2ABE 019 15 53 0480 1090 202F 032B 4353 0D66 0E4D 6057 07AB 1A5D 24AF 1976 13BB 1EDD 1DF6 020 15 53 00F0 1503 2A0C 1603 290C 196A 2695 415F 42AF 425F 41AF 16F3 15F3 2AFC 29FC 021 15 54 0840 02D4 0D0A 501F 11A7 21A7 1639 2639 601F 079E 29E7 19E7 2E79 1E79 0FDE 022 15 54 0460 0450 0B83 12AD 602F 191E 129D 192E 601F 4C9B 2367 0FE3 0FD3 16FD 1D7E 023 15 54 1003 0203 421D 056C 09B4 30E2 0CD8 076F 0BB7 0EDB 156F 19B7 1CDB 62FC 70FC 024 15 55 018E 01C6 0638 0670 1A9B 1D2D 629B 652D 283F 1AD3 1D65 57C1 62D3 6565 07FE 025 15 59 3000 40BD 407D 054F 0A73 058F 0AB3 2357 1CAB 354F 358F 3A73 3AB3 0FFC 3FFC 026 15 60 0C4E 13B0 2177 4177 423F 25D3 3A2D 223F 5A2D 3DC1 3E89 45D3 5DC1 5E89 1FFE 027 15 63 047F 099F 02EF 22E7 43AB 1C5D 2477 3C55 5B89 5D19 63A3 7661 7B81 7D11 7FFE 028 14 41 080C 0414 2050 1023 0183 02E9 036A 098F 0597 182F 21D3 3073 06FD 077E 029 14 41 1018 2024 00C3 0303 0555 0695 096A 0AAA 10DB 2327 20E7 131B 0CFC 0F3C 030 14 43 1003 200C 04B2 0871 01D8 02E4 0B4D 078E 0D1B 0E27 12E7 11DB 287D 24BE 031 14 43 0301 0921 100E 0056 20F0 30A8 0357 069D 130F 06CB 0977 0CEB 0CBD 30FE 032 14 43 0601 008E 0194 2170 206A 0CD9 1971 0795 068F 0DC3 1327 186B 123D 21FE 033 14 45 0421 091C 109A 2076 01F1 12C3 0B45 0789 260E 1E0F 1877 14BB 0D3D 23DE 034 14 45 0070 0848 1207 03A3 0D0D 0696 0535 300F 249E 21AB 1277 0BEB 0D7D 0EDE 27 035 14 45 0250 0454 02AA 110B 28A5 04AE 0B63 309D 0B99 3067 0D67 135B 0D9D 06FE 036 14 45 0064 0834 104C 0303 0599 069A 0367 28B3 30CB 134F 0B37 389B 05FD 06FE 037 14 47 0248 0270 048D 0996 300F 04B5 0D23 3037 11DE 156B 2A37 0F6B 06FD 0BDE 038 14 51 1240 201F 05A3 083D 20CF 08ED 0B35 2317 0D9E 14EB 1733 17E3 1A7D 1FDE 039 13 32 0201 0424 0842 1068 0099 0116 0625 0A43 018F 0317 08DB 04BD 117E 040 13 33 0009 0444 0882 0116 0231 044D 088B 011F 032E 10F1 0AB3 0675 11EE 041 13 33 0011 0022 000C 002E 001D 0033 003F 0AC7 11C7 0747 0778 0AF8 11F8 042 13 35 0105 0411 0842 008A 103C 026C 049B 018F 0947 03E3 11B3 067D 187E 043 13 35 0201 008A 0116 1068 0425 0856 028B 0317 04AF 0A57 05B9 0CF9 117E 044 13 35 0048 0421 08C4 011A 0235 0469 1483 0996 032F 1297 053B 027D 09DE 045 13 36 0081 0411 084A 0146 02AC 1133 063C 01C7 08CB 0557 036B 06BD 18BE 046 13 36 0103 020C 00C4 0813 10B1 056A 04AD 01C7 030F 08D7 0C7A 12BD 137A 047 13 36 000A 0441 0886 0138 0265 044B 09B4 0357 026F 1297 0579 14B9 09BE 048 13 36 0821 100E 028A 0416 00F0 0555 01B3 114D 03C9 0C37 0AAB 0E4D 10FE 049 13 36 0210 0023 0154 1087 0469 0233 051E 098E 14CD 0177 0679 0AE9 0B9E 050 13 36 0030 0089 0252 0407 00B9 0907 0437 115B 156C 0937 02DB 06EC 0BEC 051 13 36 0042 0422 080D 0189 0215 0257 10B3 084F 01CB 0637 05AB 18FC 07FC 052 13 36 0081 0416 084C 010E 02AA 1171 0497 018F 08CD 0733 0E71 0B69 10FE 053 13 36 0812 1105 0189 0078 0C06 046C 02B3 02CB 1247 06A7 099B 117D 0C7E 054 13 36 0501 0056 10A8 0096 1068 0623 090D 0597 0A2F 0557 0A79 0AB9 10FE 055 13 36 0489 0485 180A 0078 0074 1806 0333 034B 0347 1627 099B 04FD 187E 056 13 37 008C 020C 0143 0869 04B2 1115 0632 034F 01CF 1A33 18B3 057D 06BE 057 13 37 00D0 0207 018A 0864 0407 1439 1239 02D7 10EE 04D7 0B39 0D39 09EE 28 058 13 37 020C 0414 0843 1116 02A9 016A 04B1 01CF 0A4F 11B3 1A33 06BD 057E 059 13 37 0828 1050 0207 041A 00E1 0107 092F 1157 0A2F 1257 04FB 06FC 05FC 060 13 37 0041 0086 0129 00C7 04B2 0B1C 122B 055C 01AF 04F3 0AB3 0B5D 165E 061 13 37 0203 0068 014C 1096 041E 026B 0CB1 08C7 034F 0D95 0739 13B1 10FE 062 13 37 00C4 0144 0229 0413 0871 100F 193A 0557 036D 04D7 18BA 02ED 07BA 063 13 37 010A 0464 0851 00CD 10B2 030D 0E32 095B 056E 12B5 0A9B 1175 06AE 064 13 37 0C05 140A 1830 0159 02A6 0166 0299 058F 064F 0A75 11BA 09B5 127A 065 13 37 040C 0430 1803 018D 024E 0272 01B1 08D7 08EB 1317 132B 05BD 067E 066 13 38 0110 0432 0858 0185 120E 026B 04A7 08CD 1C0F 05B7 037B 09DD 02FE 067 13 38 0070 0434 0898 0143 028D 0507 122E 184B 1C0F 0577 09DB 02FD 03BE 068 13 38 0148 022C 00D1 08A3 102D 0616 1417 0B16 04EB 1917 09EB 02FD 075E 069 13 38 0109 0206 00A9 08D4 106A 0633 030F 0595 02AF 1556 0A7B 09DD 14F6 070 13 38 0070 0492 0911 006C 048E 090D 122B 1247 1C0F 03D7 03BB 097D 04FE 071 13 38 088A 1109 0264 042B 0896 1115 0437 0653 01EC 1A17 05DB 136D 0AEE 072 13 39 0415 00E1 101A 01A2 029B 0B0E 0837 0A4D 154C 05B7 10FB 07CD 196E 073 13 39 00A1 0493 0A1C 054A 0265 1816 031D 1117 0CEA 0657 05EB 0ABD 196E 074 13 39 0506 00E8 1211 0456 1095 090F 0A33 085F 076A 08B7 13A9 12F9 05EE 075 13 39 0243 00B8 01C2 101C 04AB 0D25 140F 098E 0A0F 0B75 02FB 1575 11DE 076 13 39 0470 02A3 110D 0896 040F 0A4A 10B7 185E 126B 05B5 0769 0BF0 0D5C 077 13 39 0C02 104C 101C 00B1 00E1 031F 0937 034F 06CB 0CB3 0CE3 10FD 03FE 078 13 39 0046 0121 0216 0429 08CB 0167 1193 0A9B 046F 0337 149B 15FC 0BFC 079 13 40 0431 020B 1058 0886 00F0 036D 05A7 11CE 150F 0CB7 02FB 0A7D 18DE 080 13 40 0065 0618 081B 0986 02AD 0355 10AB 1153 0CAE 0D56 139B 067D 15E6 081 13 40 084A 1304 00B1 092A 0A52 044F 11AD 0657 052F 12D5 08FB 13B5 04FE 29 082 13 40 0034 020B 010B 0865 0496 013F 023F 12C7 11C7 0CC7 13F8 0DF8 0EF8 083 13 40 010E 0096 0168 00F0 145B 0A5B 07A5 065B 0BA5 15A5 185B 19A5 01FE 084 13 40 0402 002D 10D0 0165 021D 042F 061F 0A9B 0567 09E3 0BD3 10FD 0BFE 085 13 40 0818 1060 0107 0087 04B5 034B 089F 091F 1167 10E7 0779 06F9 07FE 086 13 41 0488 0233 100F 0855 00F1 1166 03AB 09CD 0B0F 1476 06BB 0CDD 0F76 087 13 41 0148 0087 0207 049B 1079 0A65 11B6 01CF 034F 1336 0CF9 0E79 0FB6 088 13 41 0104 004B 0263 041B 10B5 014F 0C9D 051F 0367 0AE5 11FA 0EB5 0FFA 089 13 41 004B 01B0 0263 041B 08B5 094E 149D 0D1E 0B66 12E5 01FB 16B5 174E 090 13 41 0099 0162 021B 0463 08D5 1156 0BAC 0A57 15AC 1457 01FB 0EAD 172E 091 13 42 0113 04A8 080F 0171 120F 086D 02BB 0AD6 126D 0DD6 05BB 156D 17D6 092 13 42 0848 1017 0293 0427 00EB 052D 111D 0399 0C6F 11F6 0ADB 0F1D 0FF6 093 13 42 0427 0217 1093 0954 02E9 052E 031E 119A 0E6D 01F7 1AD9 1CE9 1D1E 094 13 42 0810 100F 0267 04AB 00F3 0355 0599 070D 11CE 0A77 0CBB 0F1D 0FEE 095 13 42 0302 008D 0095 106B 1073 0C6B 038F 0397 052F 0AD3 0C73 13FC 0FFC 096 13 44 0870 100F 0393 05A5 068E 0749 10B7 125B 146D 09B7 0B5B 0D6D 0EFE 097 13 44 008D 0462 081D 01A7 02CB 1313 0937 0A5B 04EF 1537 165B 0BFC 17FC 098 13 45 020F 040F 0871 1192 02DB 0337 0537 04DB 07EC 1937 18DB 1BEC 1DEC 099 13 45 0309 0432 08C7 10C7 106F 066B 0793 0997 086F 1197 073B 0FFC 17FC 100 13 48 082D 10D2 0363 0517 068B 0977 0C9F 149F 0AEB 1177 12EB 0FFC 17FC 101 13 52 005F 003F 02AF 0537 02CF 0557 11BB 0E5D 1AEE 1D76 1FB9 1FD9 1FE6 102 12 26 001 306 498 468 262 194 195 263 307 469 499 83E 103 12 29 038 034 14A 289 146 285 C0B C07 B23 4D3 2BD 17E 104 12 30 004 20B 413 0C3 123 127 0C7 20F 417 879 7F8 7FC 105 12 31 018 092 14C 229 465 2A3 1C6 C0F B17 2BB 47D 1DE 106 12 32 202 210 C0C 0A7 14B 0B5 159 46F 2B7 35B 99D 1FE 107 12 33 101 23A 456 80F 073 2A9 4C5 68C 557 33B 78D 9EE 108 12 36 21F 0AF 837 07B 43D 13E 7C8 BC2 DE0 EC1 F50 F84 30 109 12 36 606 A28 C50 09B 165 2AF 4D7 32F 557 8F9 979 1FE 110 12 36 03F 0CF 197 26B 639 535 9C6 ACA D94 E68 F30 FC0 111 12 36 60F A17 C27 0F9 17A 1BC 3D8 5E8 9F0 E43 E85 F06 112 12 39 01F 16D 0E7 4B5 34B 693 719 96E CB6 F1A ADD FE2 113 12 46 400 81F 1F7 2FB 37D 3BE 3CF 7CF 5F7 6FB 77D 7BE 114 12 48 1DF 0FF 1BF A6F E73 DB5 7DA EEC F33 F53 FAC FCC 115 11 22 041 00A 092 10C 434 04B 14D 2B1 0D3 325 43E 116 11 22 021 041 098 106 234 44A 147 127 0D9 0B9 61E 117 11 23 012 0C1 061 226 30C 198 42D 073 0D3 48D 31E 118 11 23 022 030 0C1 11C 10E 60D 28B 0F1 0E3 455 13E 119 11 23 042 021 085 109 41C 213 063 0C7 14B 43D 3BE 120 11 23 021 041 098 106 215 40B 147 127 0D9 0B9 67E 121 11 24 005 021 0C2 138 11C 293 0E3 0C7 44B 13D 63E 122 11 24 10E 093 425 219 035 151 2E0 483 541 609 3EE 123 11 25 106 083 418 205 031 049 14F 137 49B 61D 2FE 124 11 25 08B 0A5 0B4 740 09A 30B 147 465 31A 474 638 125 11 25 018 012 0C6 123 129 0CC 60F 475 13B 395 0DE 126 11 26 090 146 229 40F 21D 11E 463 1E2 2E1 2B9 1D6 127 11 26 044 083 023 20F 439 153 067 0C7 499 3B8 3FC 128 11 26 10C 031 423 059 095 313 2E2 487 44B 13D 3EE 129 11 26 034 109 203 055 0A5 45A 4AA 237 4CB 13D 3CE 130 11 26 1C2 125 618 425 40F 28E 10F 171 2F0 471 2DA 131 11 27 003 164 298 136 239 2C9 1C6 167 29B 49D 46E 132 11 28 022 115 219 053 0B1 44F 3CC 137 23B 4AD 3EE 133 11 29 086 051 0E5 529 338 1C3 24F 0D7 51B 43D 3BE 134 11 31 201 402 03F 05F 0AF 157 1A7 1C7 1F8 3F9 5FA 135 11 31 017 00F 0AB 14D 0B3 155 467 387 6BA 75C 7F8 136 11 31 00F 017 0B3 153 0AB 14B 38E 475 61B 7F4 7EC 137 11 32 186 078 497 50F 23B 25D 369 2F1 5A3 5C5 1FE 138 11 32 02E 1D0 237 26B 2AD 5C9 30F 4F1 553 595 1FE 139 11 33 08F 117 227 447 0BB 15D 26D 473 7B2 7CC 7F8 140 11 33 06F 0AF 0D7 31B 535 656 1E9 696 768 7A8 7D0 141 11 34 0E0 11E 21D 46B 4B3 4C7 34F 397 33B 2FD 1FE 142 11 35 140 0B7 44F 23D 50F 29E 2AB 1F7 3EB 37D 3DE 143 11 35 14F 0B7 45B 23D 52B 2D5 3A5 5C3 6B1 749 7FE 144 11 36 300 50F 617 07B 0BD 0DE 1EF 2F7 37B 3BD 3DE 145 11 37 0E0 11B 217 46F 4BD 4DE 36F 2F7 1FB 3BD 3DE 146 11 40 107 0F0 47F 27F 3BB 3DD 3EE 1F7 5BB 5DD 5EE 147 10 27 038 0C5 146 183 21F 22F 237 1BB 0FD 17E 148 10 33 09F 06F 237 13B 1CB 2C7 363 393 3FD 3FE 149 09 14 018 006 00C 012 125 143 0D1 0A9 01E 150 09 16 038 052 094 111 1E0 107 04B 08D 02E 151 09 16 023 00B 015 105 049 091 061 181 1FE 152 09 17 011 00A 023 043 107 087 01B 0FC 17C 153 09 17 018 00F 033 055 161 186 0AA 0CC 0F0 31 154 09 18 081 102 017 00F 047 027 078 0F9 17A 155 09 18 081 101 017 00F 04B 035 069 071 1FE 156 09 18 02B 00F 01B 115 066 1C4 0B8 1D0 1E0 157 09 19 049 00E 130 055 063 187 0AB 09D 13E 158 09 21 0C0 10B 107 01D 02E 0B7 07B 0DD 0EE 159 09 22 088 10B 035 056 06F 197 07B 0BD 0DE 160 09 22 08B 10B 035 056 06C 197 07B 1AD 1CE 161 09 22 00D 070 08B 097 0AE 157 13B 07D 16E 162 09 22 081 104 03A 05F 06F 077 0BB 07D 13E 163 09 24 0F0 11B 127 14D 18E 0B7 07B 0DD 0EE 164 09 25 0A3 11C 03F 14F 0CF 0F5 0FA 175 17A 165 09 26 04B 035 11F 09F 0ED 173 0F3 16D 1FE 166 09 30 05F 03F 12F 0D7 1A7 1C7 1FB 1FD 1FE 167 08 13 25 26 C2 0B 13 C1 78 9C 168 08 15 0A 29 54 27 C3 33 9D 5E 169 08 17 1B 27 4D 8B B4 6A D5 F2 170 08 17 49 93 0F 47 A5 39 71 FE 171 07 09 06 03 0A 15 49 70 2C 172 07 09 09 05 03 41 21 11 7E 173 07 11 34 4A 45 23 51 29 1E 174 07 11 03 06 0D 15 3A 65 5A 175 07 12 15 0B 45 23 51 29 7E 176 07 12 31 49 45 23 13 0D 7E 177 07 12 30 49 46 27 1B 1D 2E 178 07 12 23 58 25 26 1B 4D 56 179 07 13 21 41 0F 17 1B 1D 7E 180 07 14 25 51 2B 17 4B 1D 7E 181 07 15 23 43 0F 17 1B 7D 7E 182 07 17 17 0F 47 27 7B 7D 7E 183 07 21 3F 5F 6F 77 7B 7D 7E Na osnovu Liste 2.2 se vidi da postoji ta~no: sa 7 ~vorova : 13 maksimalnih grafova, sa 8 ~vorova : 4 maksimalna grafa, sa 9 ~vorova : 18 maksimalnih grafova, sa 10 ~vorova : 2 maksimalna grafa, sa 11 ~vorova : 32 maksimalna grafa, sa 12 ~vorova : 13 maksimalnih grafova, sa 13 ~vorova : 63 maksimalna grafa, sa 14 ~vorova : 11 maksimalnih grafova, sa 15 ~vorova : 19 maksimalnih grafova, sa 16 ~vorova : 5 maksimalnih grafova i sa 18 ~vorova : 3 maksimalna grafa. 32 Prilikom izdvajawa maksimalnih kanoni~kih grafova sa 7 nenula sopstvenih vred- nosti iz skupa svih kanoni~kih grafova sa 7 nenula sopstvenih vrednosti, pored navedene liste svih maksimalnih kanoni~kih grafova sa 7 nenula sopstvenih vrednosti dobijena je i Lista 3 navedena u Prilogu (str. 88). U woj su dati podaci o broju neizomorfnih grafova (sa 7 nenula sopstvenih vrednosti, sa n ~vorova i m grana), koji su dobijeni od odre|enog maksimalnog grafa kao wegovi pravi indukovani podgrafovi. Glava 3 Neki rezultati o integralnim grafovima 3.1 Uvod U ovom poglavqu dati su neki rezultati dobijeni za integralne grafove. Graf ~iji se spektar sastoji samo od celih brojeva zove se integralan. Udeo takvih grafova u skupu povezanih grafova sa malim brojem ~vorova je zna~ajan (jedan je takav od dva grafa sa tri ~vora, dva su takva grafa od {est grafova sa ~etiri ~vora, a tri od 21 grafa sa pet ~vorova). Sa pove}awem broja ~vorova situacija se bitno mewa. Kako osim definicije nema uop{tene karakterizacije ovih grafova, problem wihovog nala`ewa razmatra se u nekim specijalnim klasama grafova, a svodi se na re{avawe odre|enih Diofantovih ( Diophantus) jedna~ina za koje je dokazano da u op{tem slu~aju ne postoji metod za odre|ivawe wihovih op{tih re{ewa. Pitawe o tome koji to grafovi imaju integralan spektar postavili su 1973. godine F. Harary i A. Schwenk. Wihov broj je ne samo beskona~an, ve} se takvi grafovi mogu na}i me|u grafovima bilo kog reda. Kako je spektar nepovezanog grafa unija spektara wegovih komponenata dovoqno je posmatrati samo povezane grafove. Primer skupa koji se sastoji samo od integralnih grafova je skup kompletnih grafovaKn. Kao {to je poznato, karakteristi~ne vrednosti grafa Kn su n − 1 i −1 vi{estrukosti n − 1. Sli~no je i sa ”coctail-party” grafom CP (n). Spektar ovog grafa se sastoji od 2n− 2, 0 vi{estrukosti n i −2 vi{estrukosti n − 1. Kompletan multipartitni graf Kn k ,n k ,...,n k (sa n ~vorova i k podskupova uzajamno nesusednih ~vorova, gde k|n) je uvek integralan, sa karakteristi~nim vrednostima n− nk , 0 vi{estrukosti n−k i−nk vi{estrukosti k−1. Svi ti grafovi su u stvari komplementi nepovezanih, regularnih grafova nK1, nK2 i kKn k , redom. Ako je G regularan graf stepena r sa n ~vorova, karakteristi~ni polinom wegovog komplementa je PG(λ) = (−1)n λ− n+ r + 1 λ+ r + 1 PG(−λ− 1) To zna~i da ako se spektar od G sastoji od λ1 = r, λ2, . . . , λn, tada je spektar wegovog komplementa SP (G) = (n − 1 − r,−λ2 − 1, . . . ,−λn − 1), pa komplement integralnog 33 34 regularnog grafa mora tako|e biti integralan. Skup Ir svih regularnih, povezanih integralnih grafova fiksiranog stepena r je kona~an. Neka je G komplementaran graf grafa G. Wegov skup ~vorova je tako|e V (G), a dva razli~ita ~vora x, y ∈ V (G) su susedna u G ako i samo ako x i y nisu susedni u G. Ako su G i H dva povezana grafa bez zajedni~kih ~vorova, tada je unija G ∪H graf ~iji je skup ~vorova V (G) ∪ V (H), a skup grana je E(G) ∪ E(H). Ako je G regularan integralni graf tada su G i G ∪G integralni grafovi. DEFINICIJA 3.1. (LEPOVI] [16]) Graf G reda n zove se spektralno komplementaran, ako je PG(λ)− PG(λ) = (−1)n(PG(−λ− 1)− PG(−λ− 1)). PROPOZICIJA 3.1. (LEPOVI] [16]) Ako je G spektralno komplementaran graf, tada je takav i G. PROPOZICIJA 3.2. (LEPOVI] [16]) Za svaki prost graf G, graf G ∪G je spektralno kom- plementaran. PROPOZICIJA 3.3. (LEPOVI] [16]) Neka je G regularan graf reda n i stepena r. Tada je G ∪G povezan spektralno komplementaran graf i σ(G ∪G) = (σ(G ∪G)r {r, n− r − 1}) ⋃{n− 1±√(n− 2r − 1)2 + 4n2 2 } . PROPOZICIJA 3.4. (LEPOVI] [16]) Neka je grafG regularan graf reda n i stepena r. Tada je G spektralno komplementaran ako je σ(G) = σ(G) za n neparno ili σ(G) = (σ(G)r {r, n2 − r − 1}) ⋃ {n− r − 1,−n2 + r} za n parno. 35 3.2 Klasa integralnih grafova oblika G ⋃ G U ovom delu se defini{u potrebni i dovoqni uslovi pod kojima jeG ⋃ G integralan, gde je G regularan integralan graf reda n i stepena r. Dokaz je baziran na slede}em tvr|ewu ([7]): TEOREMA 3.1. Op{te re{ewe jedna~ine x2 + y2 = z2, koje zadovoqava uslove x > 0, y > 0, z > 0, (x, y) = 1, 2|x, je x = 2ab, y = a2 − b2, z = a2 + b2, gde su a, b celi brojevi razli~ite parnosti i (a, b) = 1, a > b > 0. Postoji (1,1) korespondencija izme|u razli~itih vrednosti a, b i razli~itih vrednosti x, y, z. Mo`e se primetiti da, ako je x = 2ab, y = a2 − b2, z = a2 + b2 re{ewe Diofantove jedna~ine x2 + y2 = z2 tada je x = (2ab)t, y = (a2 − b2)t, z = (a2 + b2)t re{ewe jedna~ine x2 + y2 = z2 za svako t ∈ N. Kako je G regularan graf stepena (n − 1 − r), bez smawewa op{tosti mo`e se pret- postaviti da je r ≥ n2 . Neka je Crn klasa grafova G ∪G, gde je G regularan integralan graf reda n stepena r. TEOREMA 3.2. Neka je G regularan integralan graf reda n i stepena r. Tada je G ∪G integralan ako i samo ako pripada jednoj od slede}ih klasa Crn integralnih grafova, gde je: 1◦ n = 2r + 1, r ∈ N; 2◦ n = (2p− 1)(2q + 1)(2t− 1), r = (((2p− 1)(2q + 1)− (2p− 1)2 + (2q + 1)2)(2t− 1)− 1)/2, p, q, t ∈ N, q ≥ p i (2p− 1)(2q + 1) > (2q + 1)2 − (2p− 1)2; 3◦ n = 2p(2q + 1)(2t− 1), r = ((2p(2q + 1)− (2p)2 + (2q + 1)2)(2t− 1)− 1)/2, p, q, t ∈ N, q ≥ p i 2p(2q + 1) > (2q + 1)2 − (2p)2; 4◦ n = (2p− 1)2q(2t− 1), r = (((2p− 1)2q − (2p− 1)2 + (2q)2)(2t− 1)− 1)/2, p, q, t ∈ N, q ≥ p i (2p− 1)2q > (2q)2 − (2p− 1)2. 36 DOKAZ. Prema Propoziciji 3.3., ako je G regularan integralni graf tada je G ∪G integralni ako i samo ako je n−1± √ (n−2r−1)2+4n2 2 ceo broj. Jasno je da jeG ∪G integralan ako i samo ako (n, r, δ) predstavqa pozitivno celobrojno re{ewe Diofantove jedna~ine (n− 2r − 1)2 + 4n2 = δ2. (3.1) Tako se karakterizacija integralnih grafova koji su u vezi sa klasom G ∪G redukuje na problem nala`ewa najop{tijeg celobrojnog re{ewa jedna~ine (3.1). Lako se vidi da (2r+1, r, 2(2r+1)), r ∈ N, predstavqa pozitivno celobrojno re{ewe Diofantove jedna~ine (3.1) {to dokazuje 1◦. Prema Teoremi 3.1., va`i n = pqt, n− 2r − 1 = (p2 − q2)t, δ = (p2 + q2)t, (3.2) gde p, q, t ∈ N. Daqe se dobija r = ((pq − p2 + q2)t− 1)/2. Kako r ∈ N mora da bude (i) (pq−p2 + q2)t−1 > 0 i (ii) (pq−p2 + q2)t je neparno. To zna~i da je (i) pq−p2 +q2 > 1, (ii) t je neparno i pq−p2 +q2 je neparno. Neka t→ (2t−1), gde a→ b zna~i da 'a je zameweno sa b'. Sada }e biti razmatrana slede}a tri slu~aja: Slu~aj 1. (p je neparan i q je neparan) Neka je p→ (2p−1) i q → (2q+1). Prema relaciji (3.2), lako se dobija da je n = (2p− 1)(2q + 1)(2t− 1), r = (((2p− 1)(2q + 1)− (2p− 1)2 + (2q + 1)2)(2t− 1)− 1)/2, δ = ((2p− 1)2 + (2q + 1)2)(2t− 1), gde p, q, t ∈ N, q ≥ p i (2p − 1)(2q + 1) > (2q + 1)2 − (2p − 1)2 {to predstavqa odgovaraju}u klasu integralnih grafova predstavqenih u 2◦. Slu~aj 2. (p je paran i q je neparan) Neka je p → 2p i neka je q → (2q + 1). Na sli~an na~in se dobija n = 2p(2q + 1)(2t− 1), r = ((2p(2q + 1)− (2p)2 + (2q + 1)2)(2t− 1)− 1)/2, δ = ((2p)2 + (2q + 1)2)(2t− 1). gde je p, q, t ∈ N, q ≥ p i 2p(2q+1) > (2q+1)2−(2p)2. Tako se dolazi do odgovaraju}e klase integralnih grafova opisane u 3◦. Slu~aj 3. (p je neparan i q je paran) Neka je p→ (2p− 1) i neka je q → 2q. Sada je n = (2p− 1)2q(2t− 1), r = (((2p− 1)2q − (2p− 1)2 + (2q)2)(2t− 1)− 1)/2, δ = ((2p− 1)2 + (2q)2)(2t− 1). gde p, q, t ∈ N, q ≥ p i (2p − 1)2q > (2q)2 − (2p − 1)2. Na ovaj na~in dobija se odgovaraju}a klasa integralnih grafova predstavqena u 4◦, pa je tako dat kompletan dokaz teoreme. 2 37 3.3 Dve beskona~ne familije integralnih kompletnih tripartitnih grafova U ovom delu se posmatra familija integralnih kompletnih tripartitnih grafova Kk,m,n za k ≥ m ≥ n. Kompletno je opisana ta familija u slu~ajevima k > m = n i k = m > n. Kn ozna~ava kompletan graf sa n ~vorova. Kompletan tripartitni graf sa k+m+n ~vorova ozna~en je saKk,m,n (videti [3], str. 16). U slu~aju kada je k = m = n grafKk,k,k je integralan za svaki pozitivan ceo broj k. Daqe se pretpostavqa da je k ≥ m ≥ n. Neka je PG(λ) oznaka karakteristi~nog polinoma grafa G = Kk,m,n. Tada je PG(λ) = λk+m+n−3(λ3 − (km+ kn+mn)λ− 2kmn). Nenula sopstvene vrednosti grafaKk,m,n su koreni jedna~ine λ3 − (km+ kn+mn)λ− 2kmn = 0. (3.3) Daqe }e (m,n) biti oznaka za najve}i zajedni~ki delilac celih brojeva m,n ∈ N, a m |n zna~i dam deli n. Najpre se dokazuje slede}i rezultat: TEOREMA 3.3. Ako je Kk,m,m integralan graf tada indeksi k i m moraju imati jednu od slede}ih vrednosti: 1◦ k = (2p− 1)(s− t)(s+ t− 1)/2, m = (2p− 1)(2t− 1)2, gde p, s, t ∈ N, s > 3t− 1 i (2s− 1, 2t− 1) = 1; 2◦ k = (2p− 1)(s− t)(s+ t− 1), m = 2(2p− 1)(2t− 1)2, gde p, s, t ∈ N, s > 3t− 1 i (2s− 1, 2t− 1) = 1; 3◦ k = 2(2p− 1)(s− t)(s+ t− 1), m = 4(2p− 1)(2t− 1)2, gde p, s, t ∈ N, s > 3t− 1 i (2s− 1, 2t− 1) = 1; 4◦ k = p(s2 − t2), m = 8pt2, gde p, s, t ∈ N, s > 3t i (s, t) = 1. DOKAZ. Lako se proverava da se u slu~aju k > m = n prema relaciji (3.3) implicitno dobija (λ+m)(λ2 − λm− 2km) = 0. Kako su koreni ove jedna~ine dati sa λ1,2 = m±√m(m+ 8k) 2 , dobija se λ1 = m+ δ 2 , λ2 = −m, λ3 = m− δ2 gde je 38 δ2 = m(m+ 8k). (3.4) Neka je r = s1t1 tako da je (s1, t1) = 1 im+ 8k = rδ. Tada iz relacije (3.4) sledim = δ r . Odavde se nalazi da jem = t1s1 δ im+ 8k = s1 t1 δ. Kako je (s1, t1) = 1 sledi da je s1 | δ i t1 | δ i dobija se da je δ = p1s1t1. Stoga jem = p1t21 i k = p1(s 2 1−t21) 8 gde su p1, s1, t1 pozitivni celi brojevi takvi da je s1 > 3t1 i 8 | p1(s21− t21). Neka je (p1, 8) = q gde je q = 1, 2, 4 ili 8. Slu~aj 1. (q = 1) Za q = 1 je p1 = 2p − 1, s1 = 2s − 1, t1 = 2t − 1, p, s, t ∈ N, pa se daqe dobija: m = (2p− 1)(2t− 1)2, k = (2p− 1)(s− t)(s+ t− 1)/2 i λ1 = (2p− 1)(2t− 1)(t+ s− 1), λ2 = −(2p− 1)(2t− 1)2, λ3 = (2p− 1)(2t− 1)(t− s), gde p, s, t ∈ N. Uslovi (s1, t1) = 1 i s1 > 3t1 daju (2s − 1, 2t − 1) = 1 i s > 3t − 1 {to dokazuje 1◦. Slu~aj 2. (q = 2) Kako za q = 2 va`i p1 = 2(2p − 1) i 4 | (s21 − t21) daqe }e biti s1 = 2s− 1, t1 = 2t− 1, p, s, t ∈ N. Lako se vidi da je: m = 2(2p− 1)(2t− 1)2, k = (2p− 1)(s− t)(s+ t− 1) i λ1 = 2(2p− 1)(2t− 1)(s+ t− 1), λ2 = −2(2p− 1)(2t− 1)2, λ3 = 2(2p− 1)(2t− 1)(t− s), gde p, s, t ∈ N. Uslovi (s1, t1) = 1 i s1 > 3t1 daju (2s − 1, 2t − 1) = 1 i s > 3t − 1 ~ime je dokazano 2◦. Slu~aj 3. (q = 4) Ako je q = 4 dobija se p1 = 4(2p − 1) i 2 | (s21 − t21), pa je s1 = 2s− 1, t1 = 2t− 1, p, s, t ∈ N. Zatim se dobija m = 4(2p− 1)(2t− 1)2, k = 2(2p− 1)(s− t)(s+ t− 1) i λ1 = 4(2p− 1)(2t− 1)(s+ t− 1), λ2 = −4(2p− 1)(2t− 1)2, λ3 = 4(2p− 1)(2t− 1)(t− s), gde p, s, t ∈ N. Po{to je (s1, t1) = 1 i s1 > 3t1 mora biti (2s − 1, 2t − 1) = 1 i s > 3t− 1 ~ime je dokaz za 3◦ potpun. 39 Slu~aj 4. (q = 8) Za q = 8 je p1 = 8p, s1 = s, t1 = t, p, s, t ∈ N i m = 8pt2, k = p(s2 − t2) i λ1 = 4pt(t+ s), λ2 = −8pt2, λ3 = 4pt(t− s), gde (s, t) = 1, s > 3t, p, s, t ∈ N {to dokazuje 4◦. Time je dokaz zavr{en. 2 Na potpuno sli~an na~in se dokazuje slede}a teorema: TEOREMA 3.4. Ako je Kk,k,n integralan tada indeksi k i n moraju imati jednu od slede}ih vrednosti: 1◦ k = (2p− 1)(2t− 1)2, n = (2p− 1)(s− t)(s+ t− 1)/2, gde p, s, t ∈ N, t < s < 3t− 1 i (2s− 1, 2t− 1) = 1; 2◦ k = 2(2p− 1)(2t− 1)2, n = (2p− 1)(s− t)(s+ t− 1), gde p, s, t ∈ N, t < s < 3t− 1 i (2s− 1, 2t− 1) = 1; 3◦ k = 4(2p− 1)(2t− 1)2, n = 2(2p− 1)(s− t)(s+ t− 1), gde p, s, t ∈ N, t < s < 3t− 1 i (2s− 1, 2t− 1) = 1; 4◦ k = 8pt2, n = p(s2 − t2), gde p, s, t ∈ N, t < s < 3t i (s, t) = 1. Glava 4 Neki rezultati o simetri~nom dvostrukom zvezdolikom stablu Ovo poglavqe sadr`i rezultate o simetri~nom dvostrukom zvezdolikom stablu iz rada [10]. U odeqku 4.1 dati su neki osnovni pojmovi. Neki rezultati o zvezdolikim stablima mogu se na}i u radu [17]M. Lepovi}a. U radu [19]M. Lepovi} i I. Gutman su dokazali da su dva zvezdolika stabla kospektralna ako i samo ako su izomorfna. Odeqak 4.2 sadr`i neke pomo}ne rezultate, a glavni rezultat ovog poglavqa je dat u odeqku 4.3 ([10]). Dokazano je da ne postoje dva kospektralna neizomorfna simetri~na dvostruka zvezdolika stabla. 4.1 Uvod Stablo je povezani graf sa n(> 1) ~vorova im = n− 1 grana. S obzirom na stepene ~vorova, me|u stablima postoje dva ekstremna slu~aja, put (u oznaci Pn, ako ima n ~vorova) i zvezda. Stablo u kojem je jedan ~vor susedan svim ostalim ~vorovima, pa samim tim ima stepen n− 1, naziva se zvezda. Za stablo se ka`e da je zvezdoliko ukoliko ima ta~no jedan ~vor stepena ve}eg od dva. Stablo sa naziva dvostruko zvezdoliko ako ima ta~no dva susedna ~vora stepena ve}eg od dva. Za dva grafa G1 i G2 ka`e se da su kospektralna ako imaju jednake spektre (tj. jednake karakteristi~ne polinome). Ako su G1 i G2 izomorfni, tada su oni kospektralni. Neka je ∗n1,n2,...,nk oznaka za zvezdoliko stablo koje ima ~vor x stepena ve}eg od dva i koje ima osobinu ∗n1,n2,...,nk \ {x} = Pn1 ∪ Pn2 ∪ · · · ∪ Pnk . Ka`e se da zvezdoliko stablo ∗n1,n2,...,nk ima k grana, ~ije su du`ine redom n1, n2, . . . , nk. Jasno je da parametri n1 ≥ n2 ≥ . . . ≥ nk ≥ 1 odre|uju zvezdoliko stablo do na izomorfizam i da ∗n1,n2,...,nk ima ta~no n1 + n2 + · · ·+ nk + 1 ~vorova. Neka je ∗m1,m2,...,ml oznaka za zvezdoliko stablo koje ima ~vor y stepena ve}eg od dva sa osobinom da je ∗m1,m2,...,ml \ {y} = Pm1 ∪ Pm2 ∪ · · · ∪ Pml . 40 41 Daqe, neka je ∗∗n1,n2,...,nk;m1,m2,...,ml oznaka grafa dobijenog povezivawem granom ~vora x grafa ∗n1,n2,...,nk sa ~vorom y grafa ∗m1,m2,...,ml . Sa ∗′n1,n2,...,nk(∗′m1,m2,...,ml) je ozna~en indukovani podgraf grafa ∗n1,n2,...,nk (∗m1,m2,...,ml) dobijen brisawem ~vora x(y) iz grafa ∗n1,n2,...,nk (∗m1,m2,...,ml). Stablo ∗∗n1,...,nk;m1,...,ml ja nazvano dvostruko zvezdoliko. Ono ima ta~no dva susedna ~vora x i y stepena ve}eg od dva i osobinu ∗ ∗n1,...,nk;m1,...,ml \{x, y} = Pn1 ∪ Pn2 ∪ · · · ∪ Pnk ∪ Pm1 ∪ Pm2 ∪ · · · ∪ Pml . Ako je k = l i ni = mi za i = 1, 2, . . . , k, tada je ∗∗n1,...,nk;n1,...,nk nazvano simetri~no dvostruko zvezdoliko stablo. 4.2 Neki pomo}ni rezultati Da bi se dokazalo da su grafovi ∗∗n1,...,nk;n1,...,nk i ∗∗m1,...,ml;m1,...,ml izomorfni, ako su kospektralni, potrebna je slede}a priprema. Prema [3](Teorema 2.12, str. 59) je P∗∗n1,...,nk;n1,...,nk (λ) = P∗n1,...,nk (λ) 2 − P∗′n1,...,nk (λ) 2. (4.1) Daqe je prema [3](Teorema 2.4, str. 54) P∗′n1,...,nk (λ) = k∏ i=1 PPni (λ), gde PPni (λ) predstavqa karakteristi~ni polinom puta Pni , i = 1, . . . , k. Prema [19], smenom λ = 2 cos θ, t 1 2 = eiθ i n = (n1, . . . , nk) dobija se da je Pni(t 1/2 + t−1/2) = t− ni 2 (tni+1 − 1) t− 1 , i = 1, . . . , k i P∗n(t 1/2 + t−1/2) = [ t n1+n2+···+nk+1 2 (t− 1)k ]−1 ∆n(t), gde je ∆n(t) = ∑ x∈Ik∗ (−1)k−||x||[1− ||x|| − (k − 1− ||x||)t]t k∑ i=1 xi(ni+1) , a I∗ = {0, 1}, x = (x1, x2, . . . , xk) i ||x|| = k∑ i=1 xi. Relacija (4.1) se transformi{e u slede}i oblik P∗∗n;n(t 1/2 + t−1/2) = t−(n1+···+nk+1) (t− 1)2k ∆n;n(t), (4.2) gde je ∆n;n(t) = ∑ x∈Ik∗ [∑ y∈Ik∗ (−1)−||x||−||y||t k∑ i=1 (xi+yi)ni τ(t, ||x||, ||y||, k) ] , 42 τ(t, ||x||, ||y||, k) = [(1− ||x|| − (k − 1− ||x||)t)× ×(1− ||y|| − (k − 1− ||y||)t)− t]t||x||+||y||, y = (y1, y2, . . . , yk), a ||y|| = k∑ i=1 yi. Neka je Jk∗ = Ik∗ \ {(0, 0, . . . , 0)}. Tada je ∆n,n(t) = ∆ (1) n,n(t) + 2∆ (2) n,n(t) + ∆ (3) n,n(t), (4.3) gde je ∆(1)n,n(t) = ∑ x∈Jk∗ [∑ y∈Jk∗ (−1)||x||+||y||t k∑ i=1 (xi+yi)ni τ(t, ||x||, ||y||, k) ] , ∆(2)n,n(t) = ∑ y∈Jk∗ (−1)||y||t k∑ i=1 yini τ(t, 0, ||y||, k) = = ∑ x∈Jk∗ (−1)||x||t k∑ i=1 xini τ(t, ||x||, 0, k), ∆(3)n,n(t) = (k − 1)2t2 + (1− 2k)t+ 1. Koristi}e se slede}e oznake: (i) ti ≥ tj ako je i ≥ j i (ii) f(ts1 , ts2 , . . . , tsl) ≥ tj ako je tsi ≥ tj za i = 1, 2, . . . , l. Posebno f(ts1 , ts2 , . . . , tsl) > tj , podrazumevaju}i da f(ts1 , ts2 , . . . , tsl) ne sadr`i tj za j < min{s1, s2, . . . , sl}. Kao posledica, u skladu sa tom ~iwenicom, dobija se τ(t, ||x||, ||y||, k) = [(1− ||x|| − (k − 1− ||x||)t)× ×(1− ||y|| − (k − 1− ||y||)t)− t]t||x||+||y|| ≥ t0, za svako x ∈ Ik∗ i svako y ∈ Ik∗ . Neka je n1 ≥ n2 ≥ · · · ≥ np > np+1 = . . . = nk podrazumevaju}i da p mo`e da bude nula i da je k > p. Ako je P (λ) polinom koji zavisi od λ tada se sa cj(P ) ozna~ava koeficijent polinoma P koji odgovara λj . PROPOZICIJA 4.1. 10 ∆(2)n,n(t) ≥ tnk+2; 20 cj(∆ (2) n,n(t)) = 0 za j < nk + 2; 30 cnk+2(∆ (2) n,n(t)) = k − p. 43 DOKAZ. Zato {to je ∆(2)n,n(t) = ∑ ||y||=1 (−1)||y||t k∑ i=1 yini τ(t, 0, ||y||, k) + + ∑ ||y||>1 (−1)||y||t k∑ i=1 yini τ(t, 0, ||y||, k) = = k∑ i=1 −tniτ(t, 0, 1, k) + ∑ ||y||>1 (−1)||y||t k∑ i=1 yini τ(t, 0, ||y||, k), τ(t, 0, 1, k) = ((k − 1)(k − 2)t− k + 1)t2 ≥ t2, τ(t, 0, ||y||, k) ≥ t2, i k∑ i=1 −tniτ(t, 0, 1, k) ≥ tnk+2, t k∑ i=1 yini τ(t, 0, ||y||, k) ≥ t2nk+2 za y sa osobinom da je ||y|| > 1 dobija se da je ∆(2)n,n(t) ≥ tnk+2 i cnk+2(∆ (2) n,n(t)) = cnk+2 ( k∑ i=1 −tniτ(t, 0, 1, k) ) = k − p, tako da je dokaz tvr|ewa potpun. 2 PROPOZICIJA 4.2. 10 ∆(1)n,n(t) ≥ t2nk+2 > tnk+2; 20 cj(∆ (1) n,n(t)) = 0 za j < 2nk + 2. (cnk+2(∆ (1) n,n(t)) = 0) DOKAZ. 10 Kako je τ(t, ||x||, ||y||, k) = [(1− ||x|| − (k − 1− ||x||)t)× ×(1− ||y|| − (k − 1− ||y||)t)− t]t||x||+||y|| ≥ t2, za svako x ∈ Jk∗ i svako y ∈ Jk∗ mo`e se primetiti da je t k∑ i=1 (xi+yi)ni τ(t, ||x||, ||y||, k) ≥ t2+ k∑ i=1 (xi+yi)ni . Koriste}i ~iwenicu da je ||x|| ≥ 1 za svako x ∈ Jk∗ i ||y|| ≥ 1 za svako y ∈ Jk∗ , i neka je xi0 = 1 i yj0 = 1 dobija se t k∑ i=1 (xi+yi)ni τ(t, ||x||, ||y||, k) ≥ t2+ k∑ i=1 (xi+yi)ni ≥ ≥ t2+ni0+nj0 ≥ t2+2nk > t2+nk , ~ime je tvr|ewe dokazano. Dokaz relacije 20 je trivijalan.2 44 PROPOZICIJA 4.3. cnk+2(∆ (3) n,n(t)) = 0. DOKAZ. Jasno je da je cj(∆ (3) n,n(t)) = 0 za j > 2.2 Simetri~no dvostruko zvezdoliko stablo ∗∗n1,...,nk;n1,...,nk ima n = 2(n1 + · · · + nk + 1) ~vorova. Ako su dva simetri~na dvostruka zvezdolika sta- bla ∗∗n1,...,nk;n1,...,nk i ∗∗m1,...,ml;m1,...,ml kospektralna, tada je jasno da ona moraju imati jednak broj ~vorova. LEMA 4.1. Ako su dva simetri~na dvostruka zvezdolika stabla ∗∗n1,...,nk;n1,...,nk i ∗∗m1,...,ml;m1,...,ml kospektralna, tada mora da bude k = l. DOKAZ. Ako je T stablo sa n ~vorova, tada je koeficijent cn−4(P (T )) jednak broju parova nesusednih grana stabla T (videti [3]), {to se ra~una kao cn−4(P (T )) = ( n− 1 2 ) − n∑ i=1 ( deg(i) 2 ) , gde deg(i) ozna~ava stepen i-tog ~vora stabla T . Za simetri~na dvostruka zvezdolika stabla ∗∗n1,...,nk;n1,...,nk i ∗∗m1,...,ml;m1,...,ml ovaj izraz postaje cn−4(P (∗∗n1,...,nk;n1,...,nk)) = 1 2 [(n− 2)(n− 3)− 2k(k − 1)]. Tako da, ako je k 6= l gore pomenuta simetri~na dvostruka zvezdolika stabla imaju razli~ite karakteristi~ne polinome i onda nisu kospektralna. 2 4.3 Glavni rezultat TEOREMA 4.1. Neka su ∗∗n1,...,nk;n1,...,nk i ∗∗m1,...,mk;m1,...,mk dva kospektralna simetri~na dvostruka zvezdolika stabla. Tada su ∗∗n1,...,nk;n1,...,nk i ∗∗m1,...,mk;m1,...,mk izomorfna. DOKAZ. Zbog uslova da su ∗∗n1,...,nk;n1,...,nk i ∗∗m1,...,mk;m1,...,mk kospektralni grafovi, sledi da moraju imati jednaki broj ~vorova: 2(n1 + · · ·+ nk) + 2 = 2(m1 + · · ·+mk) + 2 pa, prema (4.2), va`i ∆n1,...,nk;n1,...,nk(t) = ∆m1,...,mk;m1,...,mk(t). (4.4) Kao posledica toga, iz (4.3) sledi ∆(1)n,n(t) + 2∆ (2) n,n(t) = ∆ (1) m,m(t) + 2∆ (2) m,m(t). (4.5) Najpre }e biti pokazano da je nk = mk. Zaista, neka je np > np+1 = . . . = nk i mq > mq+1 = . . . = mk, podrazumevaju}i da p i q mogu biti nule, k > p i k > q. Prema Propozicijama (4.1.), (4.2.) i (4.3.) je cnk+2(∆n,n(t)) = cnk+2(2∆ (2) n,n(t)) = 2(k − p) 45 i cmk+2(∆m,m(t)) = cmk+2(2∆ (2) m,m(t)) = 2(k − q). Kako je∆n,n(t) ≥ tnk+2 i ∆m,m(t) ≥ tmk+2 va`i da je tmk+2 ≥ tnk+2 i tnk+2 ≥ tmk+2. S obzirom na tu ~iwenicu i prema (4.4) lako se dobija nk = mk i p = q. Da bi se dokazalo da su ∗∗n1,...,nk;n1,...,nk i ∗∗m1,...,mk;m1,...,mk izomorfni grafovi, do- voqno je dokazati da je ni = mi za i = 1, 2, . . . , k. Pretpostavimo, suprotno tvr|ewu, da su ∗∗n1,...,nk;n1,...,nk i ∗∗m1,...,mk;m1,...,mk dva kospektralna neizomorfna grafa. Tada postoji najmawe jedan indeks l (1 ≤ l ≤ p < k) takav da je tnl+2 6= tml+2. Jasno je da se, bez smawewa op{tosti, mo`e pretpostaviti da je tnl+2 > tml+2 i tni+2 = tmi+2 za i > l. Neka su r i s brojevi terma tml+2 u k∑ i=1 tni+2 i k∑ i=1 tmi+2, redom. Jasno je da je s > r. Sada }e biti dokazano da svakox ∈ Jk∗ i svakoy ∈ Jk∗ koji generi{u term tml+2 u poli- nomu ∆(1)n,n(t) tako|e generi{u tml+2 u ∆ (1) m,m(t) (i obratno). Neka je t 2+ k∑ i=1 (xi+yi)ni = tml+2. Lako se vidi da je xi = 0 i yi = 0 za svako i ≤ l. Zaista, ako se pretpostavi da je xi0 = 1 za neko i0 ≤ l tada se, koriste}i ~iwenicu da je ||x|| ≥ 1 i ||y|| ≥ 1, dobija t 2+ k∑ i=1 (xi+yi)ni ≥ t2+ni0+nk ≥ t2+nl+nk > t2+nl > t2+ml . Tako je • t k∑ i=l+1 (xi+yi)(ni+1) = tml+2 ili • t 1+ k∑ i=l+1 (xi+yi)(ni+1) = tml+2 ili • t 2+ k∑ i=l+1 (xi+yi)(ni+1) = tml+2. Zato {to je tni+2 = tmi+2 za i > l, dobija se da isto x ∈ Jk∗ i y ∈ Jk∗ generi{u tml+2 u polinomu ∆(1)m,m(t). Na sasvim sli~an na~in pokazuje se da ako, s druge strane, x ∈ Jk∗ i y ∈ Jk∗ generi{u term tml+2 u polinomu ∆(1)m,m(t), tada isto x i y generi{u term tml+2 u∆ (1) n,n(t). Upravo je pokazano da je cml+2(∆ (1) n,n(t)) = cml+2(∆ (1) m,m(t)). (4.6) Kako je ∆(2)n,n(t) = k∑ i=1 −tniτ(t, 0, 1, k) + ∑ ||y||>1 (−1)||y||t k∑ i=1 yini τ(t, 0, ||y||, k) (4.7) i τ(t, 0, ||y||, k) = [(1− (k − 1)t)(1− ||y|| − (k − 1− ||y||)t)− t]t||y||, 46 najpre }e biti dokazano da svako y ∈ Jk∗ kod koga je ||y|| > 1 i koje generi{e term tml+2 u polinomu∆(2)n,n(t) tako|e generi{e tml+2 u∆ (2) m,m(t) (i obratno). Neka je t 2+ k∑ i=1 yini = tml+2. Lako se vidi da je yi = 0 za i ≤ l. Zaista, ako se pretpostavi da je yi0 = 1 za neko i0 ≤ l tada, koriste}i ~iwenicu da je ||y|| > 1, dobija se t 2+ k∑ i=1 yini ≥ t2+ni0+nk ≥ t2+nl+nk > t2+nl > t2+ml . Zna~i da je • t k∑ i=l+1 yi(ni+1) = tml+2 ili • t 1+ k∑ i=l+1 yi(ni+1) = tml+2 ili • t 2+ k∑ i=l+1 yi(ni+1) = tml+2. Po{to je tni+2 = tmi+2 za i > l, dobija se da isto y kod koga je ||y|| > 1 generi{e tml+2 u polinomu ∆(2)m,m(t). Na potpuno isti na~in pokazuje se da y ∈ Jk∗ kod koga je ||y|| > 1 i koje generi{e term tml+2 u polinomu ∆(2)m,m(t), tako|e generi{e term tml+2 u∆ (2) n,n(t). Kako je τ(t, 0, 1, k) = ((k − 2)(k − 1)t− k + 1)t2 i ∑ ||y||=1 (−1)||y||t k∑ i=1 yini τ(t, 0, ||y||, k) = ∑ki=1−tniτ(t, 0, 1, k) = = ((k − 2)(1− k)t+ k − 1)(tn1+2 + · · ·+ tnk+2), dobija se da je r = cml+2 ( k∑ i=1 −tniτ(t, 0, 1, k) ) < cml+2 ( k∑ i=1 −tmiτ(t, 0, 1, k) ) = s. Prema (4.7) va`i cml+2(∆ (2) n,n(t)) < cml+2(∆ (2) m,m(t)). (4.8) Zatim se, koriste}i relacije (4.3), (4.5), (4.6) i (4.8), direktno dobija da je cml+2(∆n,n(t)) 6= cml+2(∆m,m(t)), {to je u suprotnosti sa pretpostavkom da su ∗∗n1,...,nk;n1,...,nk i ∗∗m1,...,mk;m1,...,mk kospek- tralni grafovi. Time je dokaz tvr|ewa kompletan.2 Prilog U ovom delu date su tri liste. Lista 1 predstavqa 342 kanoni~ka grafa sa 7 ~vorova koji nemaju nulu u spektru. Dobijena je pretra`ivawem svih povezanih grafova sa 7 ~vorova (ima ih 853, videti [2]). Slog Liste 1 baznih kanoni~kih grafova sa 7 sopstvenih vrednosti razli~itih od nule predstavqen je u obliku n1 n2 a11 a12a22 a13a23a33 . . . a17a27 . . . a77 gde je n1 redni broj grafa, n2 je broj wegovih grana, a a11 a12a22 a13a23a33 . . . a17a27 . . . a77 je gorwi trougaoni oblik odgovaraju}e matrice susedstva grafa G. Upotrebom kompjuterskog programa dobijena je kompletna lista svih kanoni~kih neizomorfnih grafova sa ta~no 7 sopstvenih vrednosti razli~itih od nule. S obzirom na broj dobijenih grafova umesto kompletne liste se navodi Lista 2 sa statisti~kim podacima o dobijenim neizomorfnim povezanim kanoni~kim grafovima koji imaju 7 sopstvenih vrednosti razli~itih od nule. Slog Liste 2 svih kanoni~kih grafova sa 7 sopstvenih vrednosti razli~itih od nule predstavqen je u obliku l n m k gde je l redni broj baznog kanoni~kog grafa sa 7 nenula sopstvenih vrednosti, n je broj ~vorova grafa, m je broj wegovih grana, a k je broj neizomorfnih grafova sa 7 nenula sopstvenih vrednosti koji imaju n ~vorova i m grana i dobijeni su od tog baznog grafa dodavawem novih dozvoqenih ~vorova. Koriste}i program za izdvajawe maksimalnih kanoni~kih grafova sa 7 sopstvenih vrednosti razli~itih odnule iz skupa svih kanoni~kih grafova sa 7 sopstvenih vrednosti razli~itih od nule, dobijena je i Lista 3. Slog Liste 3 svih kanoni~kih grafova sa 7 sopstvenih vrednosti razli~itih od nule predstavqen je u obliku l n m k gde je l redni broj maksimalnog grafa sa 7 nenula sopstvenih vrednosti, n je broj ~vorova grafa,m je broj wegovih grana, a k je broj neizomorfnih grafova sa 7 nenula sopstvenih vrednosti koji imaju n ~vorova i m grana i dobijeni su od tog maksimalnog grafa kao wegovi pravi indukovani podgrafovi. 47 48 Lista 1. BAZNI KANONI^KI NEIZOMORFNI GRAFOVI SA SEDAM SOPSTVENIH VREDNOSTI RAZLI^ITIH OD NULE 001 07 0 00 100 0100 00000 000110 0010110 002 07 0 10 100 0100 00100 000100 0000110 003 07 0 00 110 0000 01000 000100 0001110 004 07 0 00 100 0100 01000 000100 0010110 005 07 0 00 100 0000 00010 000110 0110010 006 07 0 00 100 0100 00000 000010 0011110 007 08 0 00 000 0010 10000 010010 0011110 008 08 0 00 100 0100 00000 001010 0101110 009 08 0 00 010 0000 01100 100100 0001110 010 08 0 00 000 0100 00100 110100 1010100 011 08 0 00 010 0100 00010 100010 0010110 012 08 0 10 000 0100 00100 000110 0010110 013 08 0 00 000 0100 00110 110000 0010110 014 08 0 00 010 0000 10000 000110 0011110 015 08 0 00 010 0000 00110 100100 0001110 016 08 0 00 000 0100 00100 010100 1010110 017 08 0 00 100 0000 01000 000100 0111110 018 08 0 10 010 0000 00100 100100 0001110 019 08 0 00 100 0100 00000 110010 0011100 020 08 0 00 100 0000 00010 000110 0110110 021 08 0 00 000 0100 00110 100100 0010110 022 08 0 00 010 0000 10000 001110 0101100 023 08 0 00 000 0010 01000 101000 0101110 024 09 0 00 100 0100 00000 010110 1010110 025 09 0 00 010 0000 00010 100110 0011110 026 09 0 00 000 0010 10110 110000 0101010 027 09 0 10 010 0000 00010 000110 0011110 028 09 0 10 000 0000 10100 010100 0011110 029 09 0 00 100 0100 00100 000110 0011110 030 09 0 00 000 0010 10010 111000 0101100 031 09 0 00 100 0000 00110 010100 0101110 032 09 0 00 000 0100 10100 010100 0011110 033 09 0 10 000 0100 00100 100010 0011110 034 09 0 00 110 0000 01010 000110 0011010 035 09 0 00 100 0000 10110 010100 0101010 036 09 0 00 010 0010 01000 000110 1001110 037 09 0 10 000 0000 00010 001010 0111110 038 09 0 00 000 1000 00100 010110 0011110 039 09 0 00 100 0000 01000 001110 0101110 040 09 0 00 000 0100 10000 001010 0111110 041 09 0 00 000 0100 00100 010110 1010110 042 09 0 00 010 1000 00010 000110 0110110 49 043 09 0 00 100 0000 00010 000110 0111110 044 09 0 00 000 1000 01000 001000 1111110 045 09 0 00 010 0100 00010 000110 1010110 046 09 0 00 000 0010 01000 010010 1011110 047 09 0 00 110 0000 10010 010100 0001110 048 09 0 00 000 1000 00110 010100 0110110 049 09 0 00 000 0100 00110 010100 1010110 050 09 0 00 100 0000 10010 010010 0111010 051 09 0 00 000 0100 10100 001010 1101010 052 09 0 00 000 0100 10000 001110 0011110 053 09 0 00 100 0000 01000 001100 1101110 054 09 0 00 000 1010 00100 010010 0101110 055 09 0 00 000 0010 01000 100110 0110110 056 09 0 00 000 0010 01100 010100 1001110 057 09 0 00 100 0000 00110 000110 0111010 058 09 0 00 100 0100 00000 110010 0011110 059 09 0 00 000 1010 10000 011010 0101100 060 09 0 00 000 0100 10100 110000 0011110 061 10 0 00 010 0000 00010 100110 0111110 062 10 0 00 110 0000 00010 000110 0111110 063 10 0 10 110 0000 00010 000110 0011110 064 10 0 00 000 1000 00110 011010 0101110 065 10 0 10 010 0000 00010 100110 0011110 066 10 0 00 000 1000 01010 001110 0011110 067 10 0 00 100 0100 00010 101010 0101110 068 10 0 00 100 1000 00010 011010 0101110 069 10 0 00 100 0000 00110 010110 0101110 070 10 0 00 000 0100 00110 101010 0101110 071 10 0 00 110 0000 10010 000110 0111010 072 10 0 10 000 0110 00100 110010 0011100 073 10 0 00 000 1000 00100 010010 1111110 074 10 0 00 010 0000 10010 011100 0011110 075 10 0 00 010 1000 00100 000110 0111110 076 10 0 00 000 1000 01000 011010 1011110 077 10 0 10 000 0000 00010 001110 0111110 078 10 0 00 010 0000 00110 100110 0011110 079 10 0 10 000 0100 00100 001110 0011110 080 10 0 00 010 0000 00010 000110 1111110 081 10 0 00 100 0000 00010 001110 0111110 082 10 0 00 000 0100 00110 101010 1101010 083 10 0 00 000 0100 00100 100110 0111110 084 10 0 10 100 0100 00100 000110 0011110 085 10 0 00 000 0010 01000 010110 1011110 086 10 0 00 000 1000 01000 001110 0111110 087 10 0 00 000 1100 00100 011010 0011110 088 10 0 10 000 1000 01000 001110 0011110 089 10 0 00 100 0100 01100 001100 0101110 50 090 10 0 00 010 0000 01010 001100 1011110 091 10 0 00 010 0000 00010 010110 1011110 092 10 0 00 010 0000 00110 110100 0011110 093 10 0 00 100 0100 00100 010110 1011100 094 10 0 00 000 1100 00100 101010 0101110 095 10 0 00 000 1010 10000 010010 0111110 096 10 0 00 110 0100 00100 000110 1001110 097 10 0 00 100 0000 10010 010100 0111110 098 10 0 00 000 1000 00110 111000 0101110 099 10 0 00 010 0010 10010 000110 1110010 100 10 0 00 000 0010 01100 100110 0011110 101 10 0 00 100 0000 10010 010110 0110110 102 10 0 00 000 0110 10010 001010 1110010 103 10 0 00 000 0010 00110 110100 0110110 104 10 0 00 010 0000 00010 101110 0111100 105 10 0 00 000 1010 00100 011010 0101110 106 10 0 00 000 0010 01100 001100 1101110 107 10 0 10 000 0000 00010 101110 0111100 108 10 0 10 000 0000 00110 000110 1111010 109 10 0 00 100 0100 11000 001100 0011110 110 10 0 00 000 0010 01010 101010 0101110 111 10 0 00 100 0100 01100 100110 0111000 112 10 0 10 100 0000 00110 000110 0111010 113 11 0 10 000 0100 00100 001110 0111110 114 11 0 00 010 0000 00110 100110 0111110 115 11 0 10 000 0100 10100 001110 0111010 116 11 0 00 100 0100 00100 000110 1111110 117 11 0 00 000 0010 01100 010100 1111110 118 11 0 00 100 0000 01010 010110 1011110 119 11 0 10 100 0100 10100 010100 0011110 120 11 0 00 010 0000 10010 011100 1011110 121 11 0 00 010 0100 00100 100110 0111110 122 11 0 00 100 0100 10100 010100 0111110 123 11 0 10 000 1000 00110 011010 0011110 124 11 0 00 000 0100 00110 101010 1101110 125 11 0 00 100 0000 00110 010110 0111110 126 11 0 00 000 0010 01000 001110 1111110 127 11 0 00 000 0100 10010 001110 0111110 128 11 0 00 010 0000 00010 101110 0111110 129 11 0 00 000 0010 11000 001110 0111110 130 11 0 00 100 0000 00010 010110 1111110 131 11 0 00 000 1000 00110 001110 0111110 132 11 0 10 000 0010 00110 110010 0011110 133 11 0 00 010 0010 10010 001110 0011110 134 11 0 00 000 1100 00100 101010 0111110 135 11 0 00 010 0100 10010 101010 0111010 136 11 0 00 000 0100 10000 001110 1111110 51 137 11 0 00 000 0010 10000 011110 1101110 138 11 0 00 100 0100 00110 010110 0011110 139 11 0 00 000 0100 00110 010110 1011110 140 11 0 00 000 0110 10100 010110 0011110 141 11 0 00 000 0010 01100 001110 1101110 142 11 0 00 000 0110 10100 110010 0011110 143 11 0 00 100 0000 10010 010110 0111110 144 11 0 00 000 0010 01110 110010 1011010 145 11 0 00 000 1100 10100 011000 0111110 146 11 0 00 000 1010 10000 011010 0111110 147 11 0 00 000 1000 01110 101100 0110110 148 11 0 00 000 0110 00100 101010 1101110 149 11 0 00 000 1100 10100 010110 0011110 150 11 0 00 000 1100 10100 011010 0011110 151 11 0 00 000 0010 10010 010110 1110110 152 11 0 10 000 1000 00100 001110 0111110 153 11 0 00 100 0000 00010 011110 0111110 154 11 0 00 000 0010 11100 110100 0111010 155 11 0 10 100 0100 00100 010110 1011100 156 11 0 00 000 0010 10100 010110 0111110 157 11 0 10 000 0100 00110 001110 0110110 158 11 0 00 100 0100 00100 001110 1101110 159 11 0 00 010 0000 00110 001110 1101110 160 11 0 00 100 0100 01010 101010 0111010 161 11 0 00 100 0100 01100 010100 1011110 162 11 0 00 100 0000 01110 110100 0011110 163 11 0 00 000 0110 11000 001110 0011110 164 11 0 00 100 0100 00100 110110 0111100 165 11 0 00 000 0100 10110 011100 0110110 166 11 0 00 000 0110 10100 101010 0101110 167 11 0 00 000 0010 01010 101010 1101110 168 11 0 10 000 0010 10010 011010 0011110 169 11 0 10 100 0100 00100 100110 0111100 170 11 0 10 000 0010 10100 010110 0111010 171 11 0 00 000 0010 01000 011110 1111100 172 11 0 00 100 0100 00110 110010 0011110 173 12 0 00 000 0010 00110 011110 1011110 174 12 0 00 100 0100 10100 010100 1111110 175 12 0 00 000 0010 11000 011110 1011110 176 12 0 10 000 0010 00110 001110 0111110 177 12 0 00 010 0100 10100 100110 0111110 178 12 0 00 010 0000 00110 100110 1111110 179 12 0 00 000 0100 00110 001110 1111110 180 12 0 00 100 0000 01010 011110 1011110 181 12 0 10 010 0010 10010 001110 0011110 182 12 0 10 000 0010 00110 110010 0111110 183 12 0 10 000 0100 00100 001110 1111110 52 184 12 0 00 100 0010 01010 001110 0111110 185 12 0 00 000 0100 00110 101110 0111110 186 12 0 00 010 0000 10010 011110 0111110 187 12 0 10 000 0010 00110 001110 1101110 188 12 0 00 000 0010 01000 011110 1111110 189 12 0 00 000 0010 00110 110110 0111110 190 12 0 00 010 0100 00100 100110 1111110 191 12 0 10 100 0100 00100 000110 1111110 192 12 0 10 100 0100 00110 001110 0101110 193 12 0 10 000 0100 00110 101010 0111110 194 12 0 00 000 0100 10010 101110 0111110 195 12 0 00 110 1000 10010 010110 0110110 196 12 0 00 000 0010 10110 011100 1101110 197 12 0 00 000 1000 00110 011110 0111110 198 12 0 00 100 0000 00010 011110 1111110 199 12 0 00 000 0110 10100 010110 0111110 200 12 0 00 000 0010 01100 110110 0111110 201 12 0 00 100 0100 00110 010110 1110110 202 12 0 10 000 1000 01100 001110 0111110 203 12 0 10 000 0010 10010 001110 0111110 204 12 0 00 000 0010 10100 110110 0111110 205 12 0 00 100 0100 10100 110100 0111110 206 12 0 00 010 1000 10110 110100 0110110 207 12 0 10 000 0100 00110 001110 1110110 208 12 0 00 000 1010 01100 100110 0111110 209 12 0 00 100 0100 10110 011100 0101110 210 12 0 10 000 0100 00110 101010 1111010 211 12 0 00 000 1010 11000 001110 0111110 212 12 0 00 000 0010 11010 111000 0111110 213 12 0 10 000 0010 01110 101100 0101110 214 12 0 00 100 0100 00100 110110 0111110 215 12 0 00 000 0110 10100 110110 0111100 216 12 0 00 000 0010 01100 100110 1111110 217 12 0 00 000 0010 01100 110110 1111010 218 12 0 10 010 0100 00110 100110 1010110 219 12 0 00 010 1000 01110 101100 0101110 220 12 0 10 010 0010 10010 001110 0101110 221 12 0 00 000 0110 00110 010110 1110110 222 12 0 00 010 1000 00110 001110 1101110 223 12 0 00 010 0000 01110 100110 1111010 224 12 0 00 000 0110 00110 001110 1110110 225 12 0 00 100 0000 10010 011110 0111110 226 12 0 00 010 0100 10010 011010 1011110 227 12 0 00 100 0110 11000 110010 0011110 228 12 0 10 000 0010 01010 101010 0111110 229 12 0 00 010 0010 01110 110100 0011110 230 13 0 10 000 0010 00110 001110 1111110 53 231 13 0 00 100 0100 10100 010110 1111110 232 13 0 00 000 0010 01110 101110 0111110 233 13 0 10 000 0100 10100 001110 1111110 234 13 0 00 000 0010 11010 101110 0111110 235 13 0 00 100 0100 01010 101110 0111110 236 13 0 00 010 0000 10010 011110 1111110 237 13 0 00 000 0100 10110 011110 0111110 238 13 0 00 000 0010 01010 011110 1111110 239 13 0 00 100 0100 00110 010110 1111110 240 13 0 00 000 0010 00110 011110 1111110 241 13 0 10 000 0010 00110 011110 0111110 242 13 0 00 010 0010 10010 001110 1111110 243 13 0 00 000 0110 10100 110110 0111110 244 13 0 10 000 0010 10110 011100 1101110 245 13 0 00 000 1000 00110 011110 1111110 246 13 0 10 100 0010 01010 001110 0111110 247 13 0 00 010 1000 10010 011110 0111110 248 13 0 00 000 1000 01110 101110 0111110 249 13 0 00 010 1000 01010 101110 0111110 250 13 0 00 000 0110 10100 010110 1111110 251 13 0 00 110 0100 10010 100110 0111110 252 13 0 00 000 1100 10100 011110 0111110 253 13 0 00 000 0010 01100 110110 1111110 254 13 0 00 100 0100 00110 110110 0111110 255 13 0 00 100 0010 01010 011110 1111100 256 13 0 00 100 0100 10110 011100 1101110 257 13 0 00 100 0100 11000 101110 0111110 258 13 0 00 100 1100 01100 001110 0111110 259 13 0 10 000 0110 00110 001110 1110110 260 13 0 10 000 0100 10100 101110 0111110 261 13 0 00 010 1100 10100 101110 0111100 262 13 0 00 000 0010 01000 111110 1111110 263 13 0 00 000 0110 00110 111010 0111110 264 13 0 00 000 0110 00110 111010 1101110 265 13 0 00 000 1110 10100 011010 1101110 266 13 0 00 000 0110 00110 111010 1011110 267 13 0 00 100 0100 10110 010110 1111010 268 13 0 00 000 1100 10100 011110 1111100 269 13 0 00 100 0100 10010 011110 0111110 270 13 0 00 010 1010 11000 010110 1011110 271 13 0 10 000 0110 00110 111010 0111100 272 13 0 00 100 0100 11000 001110 1111110 273 13 0 00 010 0010 01110 110100 1011110 274 13 0 00 010 0100 01010 101110 1011110 275 14 0 10 000 0010 00110 011110 1111110 276 14 0 10 010 0010 10010 001110 1111110 277 14 0 00 100 0010 01010 011110 1111110 54 278 14 0 00 000 1100 10110 011110 0111110 279 14 0 00 000 0010 10110 011110 1111110 280 14 0 00 100 0100 01010 101110 1111110 281 14 0 00 000 0010 01110 011110 1111110 282 14 0 00 100 0100 01110 011110 0111110 283 14 0 00 010 1000 10110 011110 0111110 284 14 0 00 000 0100 10110 011110 1111110 285 14 0 00 000 1100 10100 011110 1111110 286 14 0 00 010 1100 10100 101110 0111110 287 14 0 00 000 0010 01010 111110 1111110 288 14 0 10 000 0110 00110 111010 0111110 289 14 0 00 100 0100 10010 011110 1111110 290 14 0 00 100 1100 01100 011110 0111110 291 14 0 10 000 0010 01110 101110 0111110 292 14 0 00 000 0110 11100 101110 0111110 293 14 0 00 010 0110 10010 111010 1011110 294 14 0 00 010 1100 10100 001110 1111110 295 14 0 00 000 1010 11100 110110 0111110 296 14 0 10 010 0010 10010 101110 0111110 297 14 0 00 000 0110 10110 111010 1111010 298 14 0 10 100 0100 10110 111100 0111100 299 14 0 00 100 1100 01100 011110 1111100 300 14 0 00 000 1010 11100 011110 0111110 301 14 0 10 000 1010 00110 111010 0111110 302 14 0 00 000 0110 00110 111010 1111110 303 14 0 00 100 1100 10100 011110 0111110 304 14 0 00 100 1000 01110 110110 0111110 305 14 0 10 000 0110 00110 111010 1111100 306 15 0 00 000 0110 10110 110110 1111110 307 15 0 00 100 0100 01110 101110 1111110 308 15 0 00 000 1010 01110 011110 1111110 309 15 0 00 100 0100 01110 011110 1111110 310 15 0 10 000 0010 00110 111110 1111110 311 15 0 00 010 1010 01110 011110 0111110 312 15 0 00 100 1100 01100 011110 1111110 313 15 0 00 010 0010 10010 111110 1111110 314 15 0 00 010 1010 01110 101110 0111110 315 15 0 00 000 0010 01110 111110 1111110 316 15 0 10 000 0110 00110 111010 1111110 317 15 0 00 010 1010 11010 101110 0111110 318 15 0 00 000 0110 11100 101110 1111110 319 15 0 00 010 1010 11010 111010 0111110 320 15 0 00 100 0110 11010 011110 0111110 321 15 0 10 000 1010 01110 101110 0111110 322 15 0 00 100 0110 11100 110110 1111010 323 15 0 10 100 0010 11010 011110 0111110 324 15 0 00 100 0100 11110 111100 1111010 55 325 16 0 00 010 0110 01110 011110 1111110 326 16 0 10 100 0100 00110 111110 1111110 327 16 0 00 100 0100 01110 111110 1111110 328 16 0 00 010 1010 01110 011110 1111110 329 16 0 00 100 0110 10110 011110 1111110 330 16 0 00 000 0110 10110 111110 1111110 331 16 0 00 100 0110 11010 011110 1111110 332 16 0 00 100 0110 11010 111010 1111110 333 16 0 10 100 0110 10110 110110 0111110 334 16 0 10 010 1010 01110 101110 0111110 335 17 0 00 010 0110 01110 111110 1111110 336 17 0 00 010 1010 01110 111110 1111110 337 17 0 00 100 0100 11110 111110 1111110 338 17 0 10 100 0110 10110 011110 1111110 339 18 0 00 100 0110 11110 111110 1111110 340 18 0 00 010 0110 11110 111110 1111110 341 19 0 00 010 1110 11110 111110 1111110 342 21 0 10 110 1110 11110 111110 1111110 56 Lista 2. KANONI^KI GRAFOVI SA SEDAM SOPSTVENIH VREDNOSTI RAZLI^ITIH OD NULE l n m k l n m k l n m k l n m k 1 7 7 1 30 4 1 14 35 5 61 1 31 7 36 11 62 2 1 8 9 3 32 1 37 15 10 5 38 25 1 17 62 1 11 6 1 12 22 1 39 37 63 1 12 3 23 7 40 40 64 3 24 21 41 41 65 2 1 9 11 1 25 41 42 41 70 1 12 9 26 64 43 50 13 20 27 90 44 28 1 18 73 2 14 35 28 134 45 24 15 36 29 167 46 9 2 7 7 1 16 20 30 179 47 9 17 12 31 149 48 1 2 8 11 2 18 5 32 109 50 1 33 63 51 1 2 9 15 4 1 10 14 2 34 40 52 1 16 9 15 10 35 16 16 25 36 16 1 15 43 5 2 10 20 7 17 55 37 7 44 7 21 11 18 94 39 2 45 9 22 8 19 113 46 11 20 108 1 13 28 4 47 19 2 11 25 1 21 51 29 10 48 15 26 8 22 40 30 22 49 17 27 12 23 12 31 37 50 13 28 6 24 10 32 61 51 9 29 2 25 1 33 65 52 6 34 77 53 5 2 12 32 2 1 11 18 4 35 100 54 3 33 4 19 13 36 117 55 1 34 2 20 33 37 90 35 2 21 59 38 59 1 16 52 3 22 108 39 48 53 2 2 13 39 1 23 151 40 16 54 5 24 197 41 10 55 5 3 7 7 1 25 157 42 11 56 9 26 132 43 3 57 4 3 8 8 1 27 71 44 2 58 3 9 1 28 40 45 2 59 1 10 6 29 30 60 1 11 7 57 l n m k l n m k l n m k l n m k 12 4 25 17 47 15 26 22 48 5 4 10 16 1 3 9 10 1 27 34 49 3 17 4 11 3 28 47 50 5 18 4 12 7 29 58 51 5 19 1 13 13 30 92 52 3 20 4 14 25 31 81 53 1 21 1 15 33 32 100 16 27 33 57 3 15 43 1 4 11 21 1 17 14 34 42 46 1 22 3 18 3 35 22 48 1 23 2 36 21 49 1 26 1 3 10 13 2 37 5 50 2 14 5 38 7 51 5 4 12 26 1 15 8 52 7 16 16 3 13 28 2 53 8 5 7 7 1 17 33 29 4 54 9 18 38 30 6 55 4 5 8 9 3 19 79 31 8 56 1 10 4 20 76 32 13 58 1 11 7 21 78 33 15 59 2 12 2 22 30 34 18 60 1 13 2 23 26 35 33 61 1 24 5 36 44 5 9 11 2 25 1 37 51 3 16 60 1 12 4 38 52 61 2 13 14 3 11 17 3 39 44 62 2 14 24 18 3 40 27 63 3 15 27 19 15 41 16 64 1 16 21 20 15 42 15 69 1 17 16 21 35 43 10 18 7 22 39 44 11 3 17 71 1 19 2 23 75 45 2 72 1 24 80 46 2 5 10 14 1 25 117 4 7 7 1 15 6 26 116 3 14 35 2 16 14 27 70 37 4 4 8 9 2 17 20 28 52 39 6 10 2 18 38 29 24 40 4 11 3 19 57 30 11 41 7 20 79 31 7 42 8 4 9 12 1 21 47 43 17 13 8 22 47 3 12 22 3 44 22 14 2 23 25 23 5 45 24 15 6 24 19 24 9 46 20 16 2 25 1 58 l n m k l n m k l n m k l n m k 44 1 10 3 31 5 5 11 18 1 45 1 11 3 32 4 19 2 12 2 33 3 20 10 5 14 37 1 34 2 21 24 38 3 6 9 11 1 36 2 22 32 39 5 12 3 38 1 23 51 40 10 13 7 24 66 41 7 14 9 6 13 31 3 25 77 42 3 15 10 32 4 26 96 43 1 16 8 33 6 27 79 44 6 17 3 34 2 28 61 45 10 18 2 35 3 29 47 46 14 36 3 30 26 47 16 6 10 15 3 37 2 31 1 48 30 16 6 38 1 49 22 17 12 39 1 5 12 24 2 50 5 18 12 41 1 25 10 51 2 19 20 26 18 20 11 6 14 38 2 27 23 5 15 46 2 21 14 39 1 28 27 47 3 22 3 40 2 29 41 48 4 23 4 43 2 30 45 49 1 24 1 31 68 51 1 25 1 6 15 46 1 32 60 53 2 33 81 54 4 6 11 19 1 7 7 8 1 34 64 55 11 20 4 35 68 56 11 21 10 7 8 10 2 36 25 57 3 22 10 11 1 37 9 23 17 12 3 5 16 55 1 24 13 13 1 5 13 30 1 56 1 25 16 14 1 31 5 57 1 26 12 32 13 63 5 27 5 7 9 12 1 33 17 64 6 28 3 13 1 34 15 29 3 14 2 35 12 5 17 65 1 30 1 15 7 36 18 31 2 16 5 37 23 5 17 72 2 17 6 38 31 6 12 25 5 18 3 39 39 5 18 81 1 26 6 19 3 40 38 27 9 21 1 41 56 6 7 7 1 28 8 42 37 29 8 7 10 16 1 43 12 6 8 9 2 30 12 17 4 59 l n m k l n m k l n m k l n m k 18 4 8 7 8 1 14 6 38 12 19 5 15 15 39 16 20 8 8 8 10 2 16 17 40 14 21 12 11 3 17 20 41 9 22 8 12 2 18 9 42 8 23 6 13 2 19 3 43 10 24 5 44 7 25 2 8 9 13 2 9 10 17 2 45 5 26 2 14 6 18 5 46 1 15 4 19 20 47 1 7 11 20 1 16 7 20 34 21 1 17 6 21 42 9 14 45 4 22 4 18 1 22 35 46 4 23 4 19 1 23 26 47 7 24 5 24 10 48 2 25 8 8 10 16 1 25 5 49 2 26 7 17 1 26 1 50 2 27 6 18 5 51 4 28 4 19 3 9 11 22 1 52 3 29 5 20 7 23 8 53 2 30 2 21 6 24 17 54 1 31 2 22 7 25 33 32 2 23 2 26 46 9 15 54 1 27 45 55 2 7 12 26 2 8 11 21 1 28 38 56 1 27 3 22 1 29 24 59 1 28 3 23 2 30 15 60 1 29 1 24 4 31 5 61 1 30 3 25 3 32 4 62 1 31 3 26 7 32 2 28 3 9 12 28 1 9 16 64 1 33 1 29 4 34 1 8 12 29 1 30 14 9 16 70 1 35 2 30 1 31 22 37 3 31 1 32 32 10 7 8 1 33 1 33 29 7 13 32 1 34 27 10 8 10 1 33 1 9 7 8 1 35 20 12 1 34 1 36 16 13 1 37 1 9 8 10 1 37 10 38 1 11 3 38 5 10 9 14 1 43 1 12 6 39 2 15 1 13 3 16 1 7 14 39 1 9 13 36 3 17 1 9 9 13 1 37 6 18 1 60 l n m k l n m k l n m k l n m k 19 1 24 22 39 10 13 10 18 4 25 5 40 20 19 10 10 10 20 1 26 1 41 14 20 31 21 1 42 9 21 61 22 1 12 11 19 2 43 9 22 68 24 1 20 2 44 8 23 67 21 8 45 8 24 48 10 11 27 1 22 7 46 3 25 6 23 17 47 1 11 7 8 1 24 17 13 11 23 4 25 34 12 14 37 1 24 8 11 8 11 2 26 46 41 1 25 21 13 1 27 55 43 1 26 38 28 45 46 2 27 65 11 9 14 1 29 43 47 4 28 67 15 1 30 33 48 8 29 80 17 1 31 16 49 5 30 57 32 2 50 2 31 9 11 10 19 1 51 2 12 12 24 2 52 2 13 12 29 2 12 7 8 1 25 2 53 3 30 4 26 6 54 1 31 13 12 8 9 1 27 4 32 18 11 6 28 6 12 15 56 1 33 25 12 7 29 11 57 2 34 36 13 4 30 10 58 1 35 56 31 19 59 1 36 50 12 9 12 3 32 27 62 2 37 15 13 3 33 39 38 1 14 7 34 28 12 16 68 1 15 17 35 24 13 13 37 2 16 23 36 24 13 7 8 1 38 4 17 30 37 15 39 5 18 14 38 15 13 8 11 5 40 9 19 4 39 2 12 10 41 12 13 5 42 18 12 10 15 2 12 13 30 1 14 1 43 18 16 4 31 1 44 1 17 7 32 2 13 9 14 3 45 1 18 11 33 1 15 11 19 20 34 4 16 36 13 14 45 1 20 35 35 1 17 33 47 1 21 50 36 3 18 29 48 3 22 45 37 3 19 7 49 8 23 51 38 11 50 1 61 l n m k l n m k l n m k l n m k 51 2 29 37 32 5 30 31 15 7 8 1 33 4 13 15 56 1 31 20 34 6 57 1 32 5 15 8 9 1 35 1 33 3 10 2 36 2 13 16 64 1 11 3 38 1 14 12 26 2 12 4 14 7 8 1 27 4 13 3 15 13 35 4 28 4 36 3 14 8 10 2 29 4 15 9 11 1 37 2 11 6 30 7 13 4 38 1 12 6 31 13 14 7 39 1 13 4 32 11 15 9 40 1 14 2 33 18 16 10 41 2 34 14 17 10 42 1 14 9 13 4 35 22 18 4 43 1 14 9 36 25 19 2 15 20 37 17 15 14 43 2 16 26 38 10 15 10 15 1 44 1 17 25 39 2 17 7 45 1 18 15 40 1 18 6 49 1 19 9 19 14 20 4 14 13 33 2 20 13 15 15 52 1 34 2 21 15 14 10 16 1 35 2 22 9 16 7 8 1 17 5 36 1 23 13 18 11 37 1 24 2 16 8 10 1 19 19 38 2 25 1 11 2 20 36 39 1 12 2 21 43 40 5 15 11 19 1 13 2 22 42 41 5 22 6 14 1 23 44 42 8 23 11 24 26 43 8 24 7 16 9 14 3 25 12 44 8 25 14 15 7 26 8 45 8 26 10 16 8 27 11 17 8 14 11 20 1 14 14 41 1 28 9 18 5 21 2 49 1 29 3 19 5 22 6 50 2 30 4 23 9 51 2 31 1 16 10 18 2 24 19 52 4 19 6 25 21 53 1 15 12 28 6 20 14 26 32 29 6 21 17 27 36 14 15 60 1 30 8 22 13 28 42 61 1 31 3 23 13 62 l n m k l n m k l n m k l n m k 24 11 19 1 29 7 25 4 20 9 13 4 30 8 17 10 18 1 14 6 31 3 16 11 23 1 24 1 15 15 32 5 24 6 25 1 16 18 33 7 25 9 17 21 34 8 26 13 17 11 22 1 18 11 35 4 27 13 30 1 19 4 36 6 28 16 20 3 37 9 29 11 17 12 36 1 21 1 38 7 30 12 39 11 31 3 18 7 8 1 20 10 16 1 40 5 17 7 41 4 16 12 29 1 18 8 11 1 18 9 42 1 30 3 12 3 19 13 43 1 31 3 13 2 20 19 32 7 21 28 20 13 33 3 33 8 18 9 16 4 22 30 34 2 34 5 17 4 23 22 35 4 35 5 18 4 24 23 36 3 36 9 19 2 25 8 37 1 37 1 26 7 39 2 38 2 18 10 21 1 27 1 40 2 22 4 28 2 41 2 16 13 37 3 23 4 42 1 39 1 24 1 20 11 20 1 43 1 40 4 25 1 21 2 44 1 42 1 22 10 45 1 43 3 18 11 27 1 23 11 46 2 44 1 29 2 24 13 47 2 25 11 48 7 16 14 47 1 19 7 8 1 26 14 49 1 51 1 27 19 50 1 19 8 10 1 28 19 17 7 8 1 12 1 29 25 20 14 41 1 30 14 42 2 17 8 11 1 19 9 14 1 31 20 43 1 12 1 32 9 48 1 13 1 20 7 8 1 33 6 56 1 14 1 34 2 57 1 20 8 10 2 35 2 58 1 17 9 14 1 11 6 15 1 12 5 20 12 26 2 20 15 50 1 17 1 13 3 27 5 67 1 18 2 14 1 28 7 63 l n m k l n m k l n m k l n m k 21 7 8 1 35 2 18 8 45 1 19 7 21 8 10 1 21 12 27 1 20 1 23 14 44 1 11 1 29 1 45 1 12 3 30 1 23 10 18 3 13 2 31 1 19 6 24 7 9 1 14 1 32 1 20 12 33 1 21 14 24 8 11 1 21 9 13 1 40 1 22 10 13 1 14 3 42 2 23 15 15 2 24 16 24 9 14 1 16 4 21 13 35 1 25 5 15 1 17 7 26 3 16 1 18 5 22 7 8 1 27 1 18 1 19 4 20 3 22 8 11 3 23 11 23 2 24 10 19 1 21 1 12 1 24 7 21 1 13 2 25 9 21 10 16 1 26 13 24 11 25 1 17 1 22 9 14 1 27 9 18 3 15 3 28 10 25 7 9 1 19 3 16 4 29 12 20 3 17 3 30 15 25 8 11 2 21 6 18 2 31 6 12 3 22 4 32 2 13 3 23 6 22 10 18 1 34 1 14 4 24 3 19 1 25 7 20 3 23 12 29 2 25 9 14 3 26 4 21 2 30 5 15 3 27 2 22 2 31 7 16 6 28 1 32 7 17 11 22 11 25 2 33 5 18 11 21 11 20 1 26 1 34 2 19 7 22 1 35 5 20 1 23 2 23 7 8 1 36 6 24 2 37 4 25 10 18 3 25 3 23 8 11 3 38 1 19 4 26 2 12 2 39 1 20 5 27 1 13 4 21 11 28 5 14 1 23 13 36 1 22 11 29 1 37 3 23 15 30 2 23 9 14 2 38 2 24 9 32 3 15 7 39 2 25 8 33 3 16 7 40 1 26 1 34 2 17 9 42 2 64 l n m k l n m k l n m k l n m k 25 11 23 1 16 4 19 1 29 14 53 1 24 5 17 4 25 4 18 5 29 7 9 1 30 7 9 1 26 3 19 4 27 9 20 1 29 8 11 1 31 7 9 1 28 8 13 5 29 6 27 10 21 6 14 3 31 8 11 1 30 9 22 6 12 2 31 4 23 7 29 9 15 1 13 10 32 1 24 4 16 3 14 6 33 1 25 5 17 4 26 1 18 17 31 9 14 1 25 12 29 1 27 1 19 13 15 3 30 1 20 3 16 8 31 2 27 11 26 1 17 19 32 2 27 6 29 10 20 2 18 38 34 5 28 5 21 4 19 25 36 2 29 5 22 10 20 6 37 2 30 2 23 11 38 2 31 2 24 26 31 10 19 2 32 3 25 17 20 2 25 13 37 1 33 1 26 4 21 18 44 1 22 28 45 1 27 12 33 1 29 11 26 1 23 50 34 5 27 4 24 56 26 7 9 1 35 3 28 6 25 38 36 1 29 14 26 7 26 8 12 1 37 1 30 12 13 2 39 1 31 14 31 11 24 1 14 1 40 1 32 11 25 3 33 1 26 6 26 9 16 1 27 13 41 1 27 17 17 2 42 2 29 12 34 2 28 29 19 2 43 2 35 3 29 46 48 1 36 4 30 44 26 10 23 1 37 7 31 42 27 14 50 1 38 7 32 18 27 7 9 1 51 1 39 4 33 1 40 1 27 8 10 1 28 7 9 1 31 12 32 4 12 2 29 13 43 1 33 6 13 2 28 8 13 1 44 2 34 13 14 2 14 1 45 1 35 16 46 4 36 21 27 9 13 1 28 9 18 1 37 28 65 l n m k l n m k l n m k l n m k 38 21 23 15 39 10 24 16 33 9 15 3 33 15 60 1 40 1 25 8 16 1 26 5 17 10 34 7 9 1 31 13 39 1 27 1 18 22 40 6 19 22 34 8 12 1 41 3 32 11 25 2 20 10 13 6 42 5 26 5 21 1 14 3 43 4 27 9 15 2 44 12 28 11 33 10 19 1 45 10 29 11 20 4 34 9 16 3 46 6 30 7 21 3 17 5 31 11 22 9 18 13 31 14 47 1 32 5 23 24 19 14 48 1 33 4 24 47 20 5 50 1 25 25 21 2 51 4 32 12 32 3 26 16 52 3 33 2 27 2 34 10 20 1 53 3 34 6 21 2 54 2 35 4 33 11 25 1 22 9 36 4 26 2 23 7 31 15 55 1 37 2 27 4 24 17 59 1 38 5 28 7 25 14 60 1 39 4 29 18 26 7 40 2 30 29 27 1 31 16 68 1 41 1 31 29 32 16 34 11 26 1 32 7 9 1 32 13 40 1 33 5 27 2 41 2 34 1 28 6 32 8 11 1 42 2 29 6 12 3 45 1 33 12 34 3 30 6 13 4 46 2 35 6 31 13 14 3 47 1 36 10 32 3 48 1 37 12 33 1 32 9 15 1 38 10 16 9 32 14 49 1 39 4 34 12 33 1 17 10 55 1 40 3 34 1 18 13 35 3 19 7 33 7 9 1 33 13 41 1 36 2 20 4 43 1 37 4 33 8 11 1 44 4 38 2 32 10 19 1 12 1 45 7 39 1 20 2 13 6 21 11 14 7 33 14 48 1 34 13 42 1 22 16 15 1 52 1 44 2 66 l n m k l n m k l n m k l n m k 36 8 12 1 38 3 38 11 21 1 35 7 9 1 13 1 39 1 22 1 40 1 23 4 35 8 12 2 36 9 16 1 24 4 13 4 17 1 37 13 40 1 25 4 14 2 18 1 41 5 26 5 42 4 27 3 35 9 16 3 37 7 9 1 43 2 28 4 17 5 45 1 29 3 18 10 37 8 12 2 31 3 19 6 13 3 37 14 48 1 34 1 20 2 14 3 49 2 15 1 38 12 27 1 35 10 21 2 37 15 56 1 28 3 22 6 37 9 15 1 29 1 23 14 16 3 38 7 9 1 31 1 24 13 17 9 32 1 25 8 18 11 38 8 11 1 33 1 26 3 19 8 12 3 35 1 20 5 13 5 35 11 27 2 21 1 14 4 38 13 34 1 28 3 16 1 29 12 37 10 20 1 39 7 9 1 30 9 21 4 38 9 14 3 31 10 22 11 15 3 39 8 12 4 32 4 23 18 16 6 13 4 24 15 17 11 14 6 35 12 34 1 25 10 18 13 15 1 35 3 26 7 19 4 36 7 27 1 20 5 39 9 15 1 37 6 21 4 16 2 38 4 37 11 26 2 22 1 17 11 39 3 27 7 18 17 28 11 38 10 17 1 19 15 35 13 44 3 29 19 18 4 20 9 45 3 30 8 19 5 21 2 46 2 31 11 20 5 32 3 21 9 39 10 20 1 35 14 53 1 33 4 22 11 21 2 54 1 23 9 22 4 37 12 33 3 24 6 23 16 35 15 63 1 34 7 25 3 24 17 35 12 26 7 25 20 36 7 9 1 36 6 28 2 26 14 37 3 27 2 67 l n m k l n m k l n m k l n m k 16 5 43 8 11 1 37 1 39 11 27 1 17 3 12 2 42 1 28 2 18 4 13 3 29 5 19 4 15 2 43 14 44 1 30 7 20 3 31 11 21 1 43 9 14 1 44 7 9 1 32 14 15 2 33 3 41 10 19 1 16 5 45 7 9 1 20 2 17 4 39 12 35 1 21 6 18 4 45 8 12 1 36 1 22 4 19 3 13 4 37 1 23 3 20 1 14 3 38 4 24 5 21 1 15 1 39 3 25 4 26 2 43 10 18 2 45 9 16 1 39 13 45 1 19 2 17 4 41 11 25 3 20 4 18 8 40 7 9 1 26 4 21 6 19 6 27 4 22 6 20 4 40 8 12 3 28 1 23 4 21 2 13 1 29 2 24 6 22 1 15 1 30 1 25 1 31 2 26 2 45 10 21 1 40 9 15 1 32 1 22 3 16 3 43 11 23 2 23 7 17 1 41 12 31 1 24 3 24 5 19 1 32 2 25 3 25 7 20 1 33 1 26 2 26 5 37 1 27 4 27 5 40 10 19 1 28 2 28 2 20 2 41 13 38 1 29 4 29 1 21 1 30 2 22 1 42 7 9 1 31 1 45 11 28 3 24 1 32 2 29 1 42 8 12 1 33 1 30 2 40 11 29 1 14 2 31 3 43 12 29 2 32 5 41 7 9 1 42 9 16 1 30 1 33 5 18 2 31 2 34 4 41 8 12 2 20 1 34 1 35 3 13 1 35 2 36 1 14 3 42 10 23 1 38 1 15 1 39 1 45 12 34 1 43 7 9 1 38 1 41 9 15 1 43 13 36 1 39 1 68 l n m k l n m k l n m k l n m k 40 3 33 2 18 1 41 3 48 12 39 1 42 3 46 12 30 1 50 10 20 2 43 1 32 1 49 7 9 1 21 1 44 1 33 1 34 3 49 8 12 2 51 7 9 1 45 13 48 1 35 3 13 6 49 1 36 1 14 3 51 8 11 1 50 1 40 1 15 1 12 1 51 1 13 1 46 13 41 1 49 9 15 1 14 4 45 14 59 1 16 2 47 7 9 1 17 7 51 9 14 1 46 7 9 1 18 14 15 1 47 8 13 1 19 7 16 1 46 8 12 5 14 2 20 7 17 2 13 2 18 1 15 1 47 9 19 2 49 10 19 1 19 5 20 1 21 2 20 5 46 9 15 1 22 6 16 7 47 10 26 1 23 6 51 10 17 1 17 6 24 12 19 1 18 7 48 7 9 1 25 8 20 1 19 1 26 4 21 1 20 1 48 8 12 1 23 3 22 1 13 1 49 11 26 2 24 1 14 2 28 2 25 2 46 10 19 2 15 1 29 4 26 4 20 2 30 3 27 2 21 9 48 9 15 1 31 3 22 10 17 1 32 2 51 11 23 1 23 6 18 3 25 1 24 4 19 3 49 12 34 1 26 1 25 2 20 2 35 1 27 1 26 1 21 2 38 1 32 1 27 1 34 1 48 10 22 1 50 7 9 1 46 11 24 1 23 1 51 12 30 1 25 2 24 2 50 8 11 1 26 2 26 4 12 2 52 7 9 1 27 6 27 1 13 5 28 7 52 8 11 1 29 5 48 11 31 1 50 9 15 2 12 1 30 1 32 1 16 3 13 3 31 1 33 2 17 5 14 1 69 l n m k l n m k l n m k l n m k 15 1 52 13 50 1 16 8 15 3 51 1 17 9 52 9 14 1 18 16 55 9 15 2 15 2 52 14 60 1 19 16 16 3 16 3 20 9 17 6 17 3 53 7 9 1 21 1 18 6 18 3 19 7 19 3 53 8 11 1 54 10 19 1 20 5 20 4 13 1 20 4 21 5 21 1 14 4 21 10 22 2 22 1 22 15 53 9 15 1 23 15 55 10 19 2 52 10 17 1 16 1 24 16 20 1 18 1 17 1 25 21 21 5 19 2 18 2 26 10 22 4 20 2 19 6 27 2 23 9 21 4 20 5 24 3 22 2 54 11 25 4 25 12 23 4 53 10 21 1 26 5 26 4 24 3 23 1 27 9 27 9 25 3 24 4 28 8 28 2 26 5 25 7 29 10 29 3 27 4 26 5 30 10 28 2 27 2 31 10 55 11 24 1 32 7 26 3 52 11 21 1 53 11 30 1 33 2 27 1 23 1 31 5 28 3 24 1 32 3 54 12 31 1 29 5 25 2 33 3 32 3 30 4 27 2 34 1 33 4 31 3 29 1 34 3 32 9 30 1 53 12 38 3 35 2 33 3 31 3 40 1 36 1 34 7 32 2 42 1 37 2 35 2 33 3 38 5 36 3 34 4 53 13 48 1 35 3 54 13 39 1 55 12 32 1 54 7 9 1 40 1 34 1 52 12 28 1 45 1 36 1 36 1 54 8 12 3 37 1 39 2 13 6 55 7 9 1 38 1 41 2 14 5 39 2 42 2 15 1 55 8 12 3 40 3 43 2 13 3 41 4 54 9 15 1 14 2 42 3 70 l n m k l n m k l n m k l n m k 44 1 34 1 62 13 43 1 57 10 18 1 49 1 55 13 45 1 19 1 61 7 10 1 48 1 20 2 63 7 10 1 49 1 22 2 61 8 13 1 50 1 23 1 14 1 63 8 14 1 24 1 15 2 55 14 57 1 26 1 61 9 17 1 27 1 18 1 63 9 19 1 56 7 9 1 19 2 20 1 57 11 24 1 21 4 56 8 12 1 25 1 61 10 24 1 13 1 26 1 63 10 24 1 14 1 29 1 62 7 10 1 25 1 15 1 26 1 57 12 31 1 62 8 13 1 27 1 56 9 15 1 14 2 28 2 17 1 58 7 9 1 15 1 18 1 63 11 30 1 19 1 58 8 13 1 62 9 17 2 32 1 20 1 18 2 34 1 59 7 9 1 19 5 36 1 56 10 24 1 20 2 25 1 59 8 13 3 21 1 63 12 36 1 56 11 30 1 60 7 9 1 62 10 22 2 64 7 10 1 23 3 56 12 36 1 60 8 12 1 24 3 64 8 13 1 13 2 25 4 15 3 57 7 9 1 14 8 26 2 16 1 27 1 57 8 11 1 60 9 17 1 28 1 64 9 16 1 12 1 18 2 19 4 13 2 19 10 62 11 28 2 20 1 14 1 20 13 29 1 21 3 15 2 30 2 22 1 60 10 23 2 32 2 57 9 14 1 24 2 33 1 64 10 23 2 15 2 25 7 34 1 25 1 16 1 26 10 26 3 17 2 27 3 62 12 35 1 27 1 18 2 36 1 28 1 19 2 60 11 31 1 40 1 20 1 32 3 41 1 64 11 30 1 21 2 33 1 31 1 71 l n m k l n m k l n m k l n m k 33 1 67 8 13 1 19 18 24 5 34 1 14 4 20 18 25 10 15 3 21 5 26 9 64 12 39 1 22 1 27 4 67 9 17 2 28 1 65 7 10 1 18 5 68 10 22 1 19 12 23 2 69 11 27 2 65 8 15 1 20 9 24 11 28 1 21 3 25 25 29 2 65 9 21 1 26 23 30 2 67 10 22 1 27 5 31 5 66 7 10 1 23 7 28 1 32 7 24 9 33 4 66 8 12 1 25 14 68 11 29 1 35 1 13 1 26 13 30 7 14 1 27 2 31 6 69 12 38 2 15 2 32 17 39 2 67 11 28 1 33 10 40 2 66 9 15 1 29 2 34 1 16 2 30 8 69 13 47 1 17 1 31 7 68 12 36 1 18 1 32 11 37 1 70 7 10 1 19 3 33 5 38 3 20 2 39 6 70 8 13 3 21 2 67 12 36 2 40 3 14 2 37 1 41 1 15 5 66 10 18 1 38 5 16 1 19 1 39 4 68 13 47 3 20 1 40 3 70 9 16 1 22 1 69 7 10 1 17 5 23 1 67 13 45 1 18 5 25 3 46 2 69 8 13 3 19 6 26 4 47 1 14 3 20 7 28 1 15 4 21 6 67 14 55 1 22 1 66 11 22 1 69 9 16 1 30 2 68 7 10 1 17 4 70 10 20 1 32 2 18 6 21 1 33 1 68 8 13 2 19 9 22 6 34 1 14 5 20 8 23 6 15 6 21 4 24 4 66 12 40 1 16 1 25 3 69 10 21 2 26 5 67 7 10 1 68 9 17 2 22 3 27 2 18 5 23 7 28 1 72 l n m k l n m k l n m k l n m k 26 6 77 8 13 2 70 11 26 1 74 9 17 1 27 1 14 2 27 3 18 2 28 1 15 2 28 2 19 10 16 1 29 1 20 10 75 11 28 1 30 1 21 2 29 5 77 9 17 3 32 3 30 11 18 2 74 10 23 2 31 6 19 4 70 12 33 1 24 5 32 4 20 3 25 9 21 2 71 7 10 1 26 10 75 12 35 1 27 3 36 4 77 10 22 3 71 8 13 1 37 3 24 4 15 1 74 11 30 3 38 1 25 2 31 4 26 2 72 7 10 1 32 5 75 13 43 2 33 5 77 11 30 3 72 8 14 2 34 1 76 7 10 1 32 1 15 2 74 12 37 1 76 8 12 1 78 7 10 1 72 9 19 2 38 1 13 1 20 2 39 2 14 1 78 8 12 1 21 2 40 3 16 2 13 1 41 1 14 2 72 10 25 2 76 9 15 1 15 3 27 2 74 13 47 2 16 2 17 2 78 9 15 1 72 11 32 1 75 7 10 1 18 1 16 1 19 3 17 2 73 7 10 1 75 8 13 1 20 1 18 3 14 5 22 1 19 2 73 8 13 1 15 3 20 3 14 1 16 2 76 10 20 1 21 3 21 1 73 9 16 1 75 9 17 1 22 1 78 10 19 1 17 1 18 5 23 2 21 1 18 1 19 13 24 1 22 1 20 8 25 1 23 2 73 10 21 1 21 4 26 1 24 1 22 1 25 2 74 7 10 1 76 11 26 1 27 2 75 10 22 1 31 2 28 1 74 8 13 1 23 6 14 4 24 13 77 7 10 1 78 11 26 1 15 4 25 13 32 1 73 l n m k l n m k l n m k l n m k 35 1 16 1 83 7 10 1 26 1 28 1 79 7 10 1 81 9 15 1 83 8 13 1 29 1 16 1 15 1 79 8 12 1 17 3 85 11 27 1 14 2 18 4 83 9 16 1 34 1 15 2 19 5 19 1 20 3 86 7 10 1 79 9 16 1 21 1 84 7 10 1 19 2 22 1 86 8 13 3 20 2 84 8 14 4 14 2 21 2 81 10 19 2 15 3 15 4 20 1 16 3 79 10 25 2 21 2 84 9 19 6 26 1 22 2 20 10 86 9 16 1 27 1 23 5 21 1 17 2 24 2 18 3 79 11 34 1 25 3 84 10 25 3 19 8 26 2 26 9 20 9 80 7 10 1 27 1 27 2 21 10 29 1 22 6 80 8 13 1 84 11 33 3 23 2 14 1 81 11 24 1 34 1 25 1 86 10 21 2 80 9 17 3 26 1 85 7 10 1 23 4 18 2 28 1 24 6 19 2 29 1 85 8 13 2 25 8 30 1 14 3 26 12 80 10 22 2 34 1 15 1 27 13 23 3 16 2 28 11 24 1 81 12 30 1 29 7 25 1 85 9 16 1 30 2 82 7 10 1 17 2 80 11 28 2 18 3 86 11 28 1 29 1 82 8 12 1 19 4 29 2 30 1 14 2 20 2 30 2 15 2 21 2 31 6 80 12 36 1 22 1 32 5 82 9 16 1 23 1 33 11 81 7 10 1 18 1 34 6 19 1 85 10 20 1 35 10 81 8 12 1 20 3 22 1 36 10 13 1 23 2 37 2 14 2 82 10 25 3 24 2 15 2 25 1 86 12 36 1 74 l n m k l n m k l n m k l n m k 37 1 31 3 89 7 10 1 24 2 38 2 32 4 25 1 39 4 33 2 89 8 14 2 27 1 40 3 15 4 41 2 87 12 35 1 16 1 91 11 29 1 42 5 36 1 31 1 43 8 38 1 89 9 19 4 44 3 39 1 20 11 92 7 10 1 40 1 21 3 86 13 46 1 22 3 92 8 14 4 47 1 87 13 46 1 15 6 49 1 89 10 25 5 16 2 50 4 88 7 10 1 26 9 51 3 27 6 92 9 18 1 52 1 88 8 14 2 28 2 19 7 15 2 29 2 20 14 86 14 54 1 16 1 21 8 58 1 89 11 31 1 22 6 59 1 88 9 19 3 32 2 23 1 20 5 33 5 86 15 67 1 21 4 34 1 92 10 23 1 22 1 35 3 24 1 87 7 10 1 23 1 36 1 25 7 26 11 87 8 13 1 88 10 25 3 89 12 40 2 27 9 14 3 26 2 43 2 28 7 15 4 27 5 29 5 16 1 28 4 90 7 10 1 30 1 29 2 87 9 17 2 90 8 13 1 92 11 30 1 18 3 88 11 31 1 15 1 31 1 19 7 33 1 32 1 20 8 34 3 91 7 10 1 33 6 21 6 35 4 34 3 36 3 91 8 13 2 35 3 87 10 22 2 14 1 36 5 23 4 88 12 42 2 16 1 37 2 24 4 43 2 25 8 44 2 91 9 17 2 92 12 39 1 26 10 18 2 42 1 27 3 88 13 51 1 19 2 43 2 52 1 21 1 44 2 87 11 28 2 45 1 29 1 88 14 61 1 91 10 22 1 30 2 23 2 92 13 52 1 75 l n m k l n m k l n m k l n m k 16 2 98 8 14 1 93 7 10 1 102 7 10 1 95 9 20 1 98 9 18 1 93 8 14 4 21 1 102 8 13 1 15 6 22 1 99 7 10 1 14 1 16 1 15 1 96 7 10 1 99 8 14 2 93 9 19 3 15 6 102 9 17 2 20 13 96 8 13 1 19 1 21 7 14 1 99 9 19 1 22 1 20 6 103 7 10 1 96 9 18 1 21 8 93 10 25 4 103 8 13 1 26 2 97 7 10 1 99 10 27 3 14 2 27 5 28 2 15 1 28 2 97 8 13 2 16 1 14 4 100 7 10 1 93 11 33 2 15 3 103 9 17 1 35 1 100 8 12 1 18 2 97 9 17 3 14 1 19 2 94 7 10 1 18 3 15 2 20 1 19 8 16 1 21 2 94 8 13 1 20 2 14 2 21 2 100 9 16 1 103 10 23 2 15 2 18 1 24 1 16 2 97 10 22 2 19 1 25 1 23 4 20 2 27 1 94 9 18 2 24 6 21 3 19 1 25 4 22 1 103 11 30 1 20 4 26 3 21 2 100 10 21 1 104 7 10 1 22 2 97 11 28 2 23 1 29 3 27 1 104 8 13 1 94 10 24 1 30 4 28 2 14 1 25 1 31 1 29 1 15 2 26 1 32 2 16 1 27 2 100 11 36 1 28 1 97 12 35 1 104 9 19 2 36 2 101 7 10 1 20 2 94 11 33 1 37 1 21 2 101 8 14 1 95 7 10 1 97 13 43 1 16 1 104 10 24 1 25 1 95 8 14 2 98 7 10 1 101 9 19 1 26 1 15 1 22 1 76 l n m k l n m k l n m k l n m k 104 11 32 1 109 9 20 1 112 9 21 5 115 7 11 1 21 1 105 7 10 1 112 10 28 1 115 8 15 3 110 7 10 1 16 2 105 8 13 1 113 7 11 1 14 1 110 8 13 2 115 9 20 4 15 5 14 2 113 8 15 3 21 6 16 1 15 2 16 3 22 1 16 1 105 9 17 1 113 9 19 1 115 10 26 3 19 4 110 9 16 1 20 6 27 6 20 4 17 3 21 8 28 2 21 5 18 2 22 1 22 2 19 3 115 11 33 2 20 3 113 10 25 2 34 3 105 10 24 2 21 2 26 3 35 1 25 1 22 2 27 9 26 1 23 1 115 12 41 1 27 5 113 11 31 1 42 1 110 10 20 1 32 1 105 11 32 1 21 1 33 1 116 7 11 1 22 2 106 7 10 1 23 2 113 12 38 1 116 8 14 1 24 2 15 1 106 8 14 3 26 2 114 7 11 1 15 1 27 1 116 9 18 2 28 2 114 8 14 1 20 1 106 9 19 3 29 1 15 2 20 1 30 1 16 5 117 7 11 1 106 10 25 2 110 11 26 1 114 9 19 2 118 7 11 1 27 1 20 3 107 7 10 1 32 1 21 9 118 8 14 1 35 1 22 3 15 2 108 7 10 1 36 1 16 1 114 10 25 1 108 8 15 1 111 7 10 1 26 5 118 9 18 2 27 3 19 2 108 9 21 1 111 8 15 1 28 4 20 6 21 3 109 7 10 1 112 7 10 1 114 11 32 1 22 2 33 1 109 8 14 1 112 8 15 4 34 1 118 10 23 1 15 2 16 1 35 1 24 2 25 3 77 l n m k l n m k l n m k l n m k 26 5 18 1 123 11 36 1 27 4 127 9 17 1 28 1 121 9 19 1 124 7 11 1 20 3 20 4 21 1 118 11 29 1 21 5 124 8 13 1 22 1 31 2 23 1 15 1 23 2 32 2 16 1 33 5 121 10 24 1 127 10 24 1 34 1 25 1 124 9 17 1 26 1 26 3 27 1 118 12 39 1 27 1 125 7 11 1 28 1 40 2 28 1 29 1 41 1 125 8 14 1 121 11 31 1 15 1 127 11 31 1 118 13 48 1 32 1 16 2 17 1 128 7 11 1 119 7 11 1 122 7 11 1 125 9 18 1 128 8 14 1 120 7 11 1 122 8 14 1 20 1 16 1 16 1 21 1 17 1 120 8 14 1 17 1 22 2 15 4 128 9 22 1 16 2 122 9 20 2 125 10 25 1 17 1 22 1 128 10 28 1 24 1 126 7 11 1 120 9 18 1 129 7 11 1 19 2 122 10 27 2 126 8 14 1 20 3 29 1 15 2 129 8 14 1 21 3 16 1 15 1 22 3 122 11 35 1 16 2 126 9 18 2 17 1 120 10 24 2 123 7 11 1 19 2 25 2 20 3 129 9 18 1 26 3 123 8 15 2 19 1 28 1 16 3 126 10 23 1 20 2 24 2 21 2 120 11 30 1 123 9 20 2 25 1 22 3 31 1 21 4 22 2 126 11 29 1 129 10 24 1 120 12 37 1 25 1 123 10 26 1 127 7 11 1 27 2 121 7 11 1 27 1 28 1 28 2 127 8 14 1 121 8 15 2 29 1 16 2 129 11 33 1 16 2 18 1 78 l n m k l n m k l n m k l n m k 130 7 11 1 134 8 14 1 39 1 16 1 136 12 39 2 131 7 11 1 40 7 137 12 41 1 135 7 11 1 41 8 42 2 131 8 13 1 42 2 43 2 14 1 135 8 15 5 44 3 15 1 16 5 136 13 47 4 45 2 16 1 48 5 17 2 135 9 20 6 137 13 52 2 21 10 136 14 55 2 131 9 16 1 22 2 138 7 11 1 17 1 136 15 63 1 18 1 135 10 25 1 138 8 14 1 19 1 26 4 137 7 11 1 16 2 21 1 27 5 22 2 28 2 137 8 13 1 138 9 20 2 23 2 14 1 22 1 135 11 33 1 15 2 131 10 20 1 34 3 16 1 138 10 27 1 26 1 17 2 28 2 136 7 11 1 139 7 11 1 29 1 137 9 17 2 30 1 136 8 14 1 19 2 139 8 14 2 15 1 20 3 15 1 131 11 36 1 16 2 21 5 16 1 17 2 22 4 17 1 132 7 11 1 23 2 136 9 19 1 24 3 139 9 17 1 132 8 16 2 20 2 18 2 21 5 137 10 22 1 20 1 132 9 22 5 22 5 24 1 21 1 23 4 25 2 22 1 132 10 29 2 26 3 24 1 136 10 25 3 27 5 132 11 37 1 26 3 28 9 139 10 21 1 27 10 29 4 27 1 133 7 11 1 28 7 30 3 29 1 29 7 31 2 133 8 13 1 140 7 11 1 16 1 136 11 31 1 137 11 32 1 32 4 33 3 140 8 14 1 133 9 19 1 33 6 34 4 16 6 34 13 35 2 17 1 134 7 11 1 35 7 36 6 36 1 37 4 140 9 20 4 79 l n m k l n m k l n m k l n m k 21 2 20 6 30 8 22 8 21 3 31 2 148 9 20 1 23 2 22 2 21 1 146 11 34 2 22 1 140 10 26 1 143 10 23 1 35 3 27 3 24 3 36 6 149 7 11 1 28 2 25 5 37 10 29 5 26 6 38 2 149 8 15 2 30 1 27 2 17 2 28 1 146 12 41 1 140 11 34 1 43 1 149 9 20 1 35 1 143 11 30 1 44 3 21 1 37 2 31 3 45 3 22 3 32 2 23 1 141 7 11 1 33 2 146 13 52 1 24 3 141 8 15 2 143 12 38 1 146 13 53 1 149 10 28 1 16 1 29 3 17 1 144 7 11 1 147 7 11 1 30 2 31 2 141 9 20 1 145 7 11 1 147 8 14 1 21 1 15 2 149 11 37 3 22 1 145 8 15 2 16 4 38 1 16 2 17 1 39 1 142 7 11 1 145 9 20 1 147 9 18 1 149 12 46 1 142 8 15 1 21 4 20 2 16 3 21 6 150 7 11 1 17 1 145 10 27 2 22 4 23 1 150 8 15 1 142 9 21 2 146 7 11 1 16 4 22 3 147 10 25 1 146 8 15 3 27 2 150 9 21 4 142 10 27 2 16 4 28 3 22 2 17 3 29 1 142 11 33 1 150 10 27 2 146 9 20 2 147 11 33 1 143 7 11 1 21 10 34 1 151 7 11 1 22 10 143 8 14 2 23 6 148 7 11 1 151 8 16 1 15 2 24 2 16 3 148 8 14 1 151 9 21 1 146 10 27 7 15 1 143 9 18 2 28 11 16 1 152 7 11 1 19 4 29 10 17 1 80 l n m k l n m k l n m k l n m k 152 8 15 1 22 3 19 1 30 1 16 1 23 3 20 3 31 1 24 1 21 2 152 9 20 1 22 3 163 11 37 1 21 1 156 10 25 1 38 1 22 1 28 1 159 10 24 1 30 3 25 1 163 12 46 1 153 7 11 1 26 1 156 11 37 1 27 1 164 7 11 1 153 8 14 1 28 1 15 2 157 7 11 1 164 8 16 3 17 1 159 11 34 1 157 8 15 3 164 9 21 1 153 9 18 1 16 2 160 7 11 1 22 4 19 1 17 2 20 3 160 8 16 3 164 10 28 1 22 1 157 9 20 2 17 1 29 1 24 1 21 6 22 4 160 9 22 2 165 7 11 1 153 10 23 1 23 2 23 1 24 1 165 8 15 2 25 1 157 10 26 2 161 7 11 1 16 2 28 1 27 2 17 2 30 1 28 4 161 8 15 1 29 2 16 1 165 9 21 3 153 11 37 1 17 1 22 1 157 11 33 1 23 1 154 7 11 1 34 2 161 9 22 1 165 10 28 1 154 8 15 2 157 12 41 1 162 7 11 1 166 7 11 1 155 7 11 1 158 7 11 1 162 8 14 1 166 8 15 2 155 8 16 3 158 8 16 3 163 7 11 1 16 3 17 1 156 7 11 1 158 9 22 1 163 8 15 1 16 3 166 9 20 1 156 8 14 1 159 7 11 1 17 1 21 2 15 1 22 7 16 3 159 8 14 1 163 9 21 2 23 2 17 2 15 3 22 3 24 1 16 1 23 2 156 9 18 1 17 1 24 1 166 10 26 1 20 1 28 1 21 2 159 9 18 1 163 10 29 3 29 4 81 l n m k l n m k l n m k l n m k 30 3 172 8 16 1 30 1 17 1 178 7 12 1 31 1 166 11 37 2 172 9 24 1 178 8 15 1 183 7 12 1 167 7 11 1 16 1 173 7 12 1 17 1 183 8 16 1 167 8 15 1 16 1 173 8 14 1 178 9 21 1 184 7 12 1 17 4 174 7 12 1 179 7 12 1 184 8 15 1 167 9 22 1 17 2 23 4 175 7 12 1 179 8 15 1 24 3 16 1 184 9 21 2 176 7 12 1 17 1 167 10 29 1 185 7 12 1 30 1 176 8 16 1 179 9 19 1 31 4 17 1 23 1 185 8 15 1 18 1 17 2 167 11 38 1 180 7 12 1 18 1 39 1 176 9 22 2 23 1 180 8 15 1 185 9 21 2 168 7 11 1 16 1 22 1 176 10 29 1 17 2 23 1 168 8 16 2 30 1 18 1 24 1 17 1 176 11 37 1 180 9 19 1 185 10 27 1 168 9 22 1 38 1 21 1 29 1 22 1 169 7 11 1 176 12 46 1 23 2 186 7 12 1 170 7 11 1 177 7 12 1 180 10 26 1 186 8 16 1 17 1 170 8 15 1 177 8 16 2 181 7 12 1 16 4 17 2 186 9 21 1 17 1 182 7 12 1 22 1 177 9 20 1 23 1 170 9 21 1 21 2 182 8 17 3 22 3 22 3 18 1 187 7 12 1 171 7 11 1 177 10 25 1 182 9 22 1 187 8 17 1 26 1 23 4 18 1 171 8 16 1 27 1 24 1 28 1 187 9 23 1 172 7 11 1 182 10 28 1 25 1 177 11 32 1 29 1 82 l n m k l n m k l n m k l n m k 187 10 33 1 197 11 37 1 24 1 193 10 27 2 38 1 188 7 12 1 28 1 201 7 12 1 29 1 198 7 12 1 189 7 12 1 201 8 17 3 193 11 34 1 198 8 15 1 18 1 189 8 16 1 16 1 18 1 194 7 12 1 17 1 201 9 23 1 18 2 24 1 189 9 25 1 194 8 14 1 16 1 198 9 19 1 202 7 12 1 190 7 12 1 20 2 194 9 18 1 21 1 202 8 16 1 190 8 16 1 22 3 17 2 17 2 195 7 12 1 23 3 18 2 24 1 202 9 22 2 195 8 16 1 190 9 21 1 17 2 198 10 27 2 203 7 12 1 22 4 28 1 23 8 195 9 22 1 29 5 203 8 17 2 24 2 18 1 196 7 12 1 198 11 35 3 190 10 27 2 203 9 23 1 28 5 196 8 18 1 199 7 12 1 24 1 29 11 30 2 197 7 12 1 199 8 16 2 203 10 31 1 17 4 190 11 34 2 197 8 15 1 18 1 204 7 12 1 35 7 16 1 36 3 17 3 199 9 21 1 204 8 15 1 18 1 22 3 17 1 190 12 42 2 23 4 18 3 197 9 19 1 24 2 191 7 12 1 21 2 204 9 22 2 22 1 199 10 27 1 23 2 192 7 12 1 23 3 29 1 24 2 24 2 30 2 25 2 193 7 12 1 25 1 200 7 12 1 204 10 29 2 193 8 16 3 197 10 27 1 30 1 17 2 29 1 200 8 16 1 31 2 30 2 17 2 32 1 193 9 21 3 31 1 18 1 22 3 32 1 204 11 38 2 23 1 200 9 22 1 83 l n m k l n m k l n m k l n m k 205 7 12 1 215 8 16 1 219 8 17 4 209 8 17 3 17 1 18 1 205 8 16 1 209 9 22 1 215 9 22 1 219 9 22 1 205 9 21 1 23 1 23 1 23 2 24 1 206 7 12 1 209 10 28 1 215 10 29 1 219 10 29 1 206 8 17 1 210 7 12 1 216 7 12 1 220 7 12 1 207 7 12 1 210 8 17 1 216 8 17 2 18 1 220 8 17 3 207 8 16 3 211 7 12 1 18 1 17 2 216 9 23 3 211 8 16 1 24 2 220 9 23 3 207 9 21 3 17 2 22 3 18 1 216 10 29 1 220 10 29 1 23 1 30 1 211 9 22 2 221 7 12 1 207 10 27 3 23 2 216 11 35 1 28 1 221 8 17 2 29 1 211 10 28 2 217 7 12 1 221 9 22 1 207 11 34 1 211 11 34 1 217 8 16 1 23 1 35 1 17 2 212 7 12 1 18 1 221 10 29 1 207 12 42 1 213 7 12 1 217 9 22 2 222 7 12 1 208 7 12 1 23 4 213 8 17 4 24 1 222 8 17 2 208 8 16 1 18 1 25 1 17 3 223 7 12 1 18 2 213 9 23 4 217 10 29 2 24 1 30 2 223 8 18 1 208 9 22 1 31 2 23 5 213 10 30 1 224 7 12 1 24 3 217 11 37 1 25 1 214 7 12 1 38 2 224 8 17 1 18 1 208 10 30 4 214 8 17 1 217 12 46 1 31 3 225 7 12 1 214 9 23 1 218 7 12 1 208 11 38 2 225 8 15 1 215 7 12 1 219 7 12 1 16 2 209 7 12 1 17 1 84 l n m k l n m k l n m k l n m k 18 1 25 1 25 1 235 10 34 1 225 9 19 1 228 10 31 1 243 10 28 1 20 1 236 7 13 1 21 1 229 7 12 1 244 7 13 1 22 1 237 7 13 1 23 1 229 8 17 1 244 8 19 1 25 1 18 1 237 8 17 1 19 2 245 7 13 1 225 10 25 1 229 9 23 1 31 1 237 9 25 1 245 8 16 1 230 7 13 1 18 2 226 7 12 1 238 7 13 1 19 2 231 7 13 1 226 8 17 4 238 8 18 1 245 9 23 1 18 3 231 8 18 1 24 3 238 9 23 1 25 2 226 9 23 6 231 9 23 1 24 5 24 1 239 7 13 1 245 10 30 2 25 2 31 1 231 10 29 1 239 8 18 2 226 10 29 1 246 7 13 1 30 2 231 11 35 1 239 9 24 1 31 4 246 8 18 1 32 2 232 7 13 1 240 7 13 1 247 7 13 1 226 11 36 1 232 8 16 1 241 7 13 1 38 1 18 1 247 8 18 1 39 2 241 8 18 1 232 9 24 1 247 9 24 1 226 12 46 1 241 9 24 1 233 7 13 1 248 7 13 1 227 7 12 1 241 10 31 1 233 8 17 1 248 8 16 1 227 8 18 1 242 7 13 1 17 1 234 7 13 1 18 1 227 9 25 1 243 7 13 1 19 1 234 8 19 1 228 7 12 1 243 8 17 2 248 9 20 1 235 7 13 1 18 3 24 2 228 8 17 2 19 1 25 1 18 2 235 8 18 1 26 1 19 2 243 9 22 1 228 9 23 1 23 2 248 10 31 1 24 1 235 9 26 2 24 1 32 1 85 l n m k l n m k l n m k l n m k 254 8 18 1 248 11 39 1 19 1 260 7 13 1 266 8 18 2 249 7 13 1 254 9 25 1 260 8 17 1 266 9 24 1 18 2 249 8 18 2 255 7 13 1 267 7 13 1 19 1 260 9 23 2 255 8 18 2 267 8 18 1 250 7 13 1 261 7 13 1 255 9 24 1 267 9 24 1 250 8 17 1 261 8 18 1 18 3 256 7 13 1 268 7 13 1 19 2 261 9 24 1 256 8 17 1 269 7 13 1 250 9 23 1 18 2 262 7 13 1 24 6 269 8 18 2 25 2 256 9 23 1 262 8 17 1 19 1 250 10 30 1 257 7 13 1 262 9 22 1 269 9 25 1 31 2 26 1 257 8 18 1 263 7 13 1 250 11 37 1 19 1 269 10 33 1 263 8 18 1 251 7 13 1 257 9 24 2 19 1 270 7 13 1 25 1 252 7 13 1 26 1 264 7 13 1 270 8 18 2 19 2 252 8 17 1 257 10 31 1 264 8 18 1 18 1 32 1 19 3 270 9 24 1 25 2 252 9 23 1 257 11 39 1 264 9 24 2 26 1 25 2 253 7 13 1 258 7 13 1 26 2 270 10 32 1 253 8 17 1 258 8 18 4 264 10 30 1 271 7 13 1 18 1 19 1 32 2 19 1 33 1 272 7 13 1 258 9 24 3 253 9 23 1 25 1 264 11 39 1 272 8 19 1 24 2 258 10 31 1 265 7 13 1 273 7 13 1 253 10 30 1 259 7 13 1 265 8 17 1 273 8 18 1 254 7 13 1 19 1 259 8 18 1 266 7 13 1 86 l n m k l n m k l n m k l n m k 273 9 24 1 283 8 19 2 289 8 19 2 20 1 20 1 295 12 48 1 274 7 13 1 283 9 25 1 289 9 25 1 296 7 14 1 274 8 18 1 26 1 19 1 284 7 14 1 297 7 14 1 290 7 14 1 274 9 26 1 284 8 19 1 297 8 19 1 20 2 290 8 19 1 20 1 275 7 14 1 284 9 25 2 290 9 25 1 297 9 25 2 275 8 20 1 26 1 26 1 291 7 14 1 27 1 276 7 14 1 284 10 31 1 292 7 14 1 297 10 32 1 277 7 14 1 285 7 14 1 33 1 292 8 19 1 277 8 19 2 285 8 18 1 20 1 297 11 40 1 19 1 278 7 14 1 293 7 14 1 298 7 14 1 285 9 24 2 278 8 18 1 293 8 19 1 299 7 14 1 286 7 14 1 20 2 279 7 14 1 299 8 20 1 286 8 19 1 293 9 26 2 280 7 14 1 20 1 300 7 14 1 293 10 33 1 280 8 20 1 286 9 26 1 300 8 19 1 294 7 14 1 20 1 280 9 27 1 287 7 14 1 294 8 19 1 301 7 14 1 281 7 14 1 287 8 18 1 20 1 19 1 302 7 14 1 282 7 14 1 295 7 14 1 287 9 24 1 302 8 20 1 282 8 19 2 295 8 19 1 288 7 14 1 20 2 303 7 14 1 282 9 25 4 288 8 19 1 295 9 24 1 303 8 18 1 282 10 32 2 20 1 26 2 304 7 14 1 282 11 40 1 288 9 25 1 295 10 32 1 33 2 304 8 20 1 283 7 14 1 289 7 14 1 295 11 40 1 304 9 27 1 87 l n m k l n m k l n m k l n m k 305 8 19 1 314 8 20 1 322 9 27 1 332 7 16 1 306 7 15 1 315 7 15 1 323 7 15 1 333 7 16 1 307 7 15 1 316 7 15 1 323 8 20 1 333 8 22 1 307 8 20 1 316 8 20 1 21 1 324 7 15 1 333 9 28 1 317 7 15 1 307 9 26 2 325 7 16 1 334 7 16 1 28 1 317 8 21 1 326 7 16 1 335 7 17 1 308 7 15 1 318 7 15 1 327 7 16 1 336 7 17 1 309 7 15 1 318 8 20 1 21 1 327 8 21 1 336 8 23 1 310 7 15 1 22 1 318 9 26 1 336 9 30 1 311 7 15 1 327 9 27 1 319 7 15 1 337 7 17 1 311 8 20 1 327 10 33 1 21 1 319 8 20 1 338 7 17 1 21 2 328 7 16 1 311 9 28 1 339 7 18 1 319 9 27 1 328 8 22 1 311 10 36 1 339 8 24 1 320 7 15 1 328 9 29 1 311 11 45 1 339 9 30 1 320 8 20 1 328 10 37 1 312 7 15 1 340 7 18 1 320 9 26 1 329 7 16 1 312 8 20 1 341 7 19 1 320 10 33 1 330 7 16 1 313 7 15 1 342 7 21 1 321 7 15 1 331 7 16 1 313 8 20 1 88 Lista 3. KANONI^KI GRAFOVI SA SEDAM SOPSTVENIH VREDNOSTI RAZLI^ITIH OD NULE l n m k l n m k l n m k l n m k 1 17 62 1 59 3 34 64 42 14 63 1 60 3 35 65 43 12 64 2 61 3 36 73 44 8 65 2 62 3 37 81 45 3 70 1 63 1 38 87 46 2 71 1 67 1 39 80 72 1 40 65 1 11 17 3 1 14 35 3 41 46 18 7 1 16 52 2 36 6 42 40 19 24 53 2 37 15 43 37 20 48 54 5 38 23 44 36 21 80 55 5 39 31 45 30 22 111 56 5 40 32 46 19 23 146 57 2 41 32 47 10 24 185 58 1 42 27 48 7 25 218 59 1 43 30 49 4 26 218 60 2 44 35 50 4 27 201 61 3 45 39 51 3 28 179 62 4 46 35 52 3 29 169 63 4 47 27 53 1 30 153 64 2 48 17 31 130 68 1 49 14 1 12 22 3 32 94 69 1 50 11 23 7 33 62 70 1 51 12 24 22 34 40 52 11 25 44 35 31 1 15 43 3 53 10 26 70 36 23 44 4 54 5 27 88 37 17 45 9 55 2 28 103 38 7 46 14 56 1 29 119 39 3 47 15 57 1 30 141 40 1 48 12 58 1 31 156 49 9 59 1 32 155 1 10 13 2 50 8 60 1 33 132 14 8 51 9 61 1 34 112 15 25 52 11 35 92 16 53 53 13 1 13 28 3 36 88 17 88 54 12 29 7 37 80 18 133 55 9 30 19 38 65 19 183 56 3 31 34 39 42 20 220 57 2 32 51 40 26 21 235 58 2 33 60 41 16 22 233 89 l n m k l n m k l n m k l n m k 23 230 22 1 48 8 27 54 24 215 49 7 28 57 25 181 1 7 7 4 50 2 29 57 26 133 8 10 51 1 30 47 27 95 9 24 31 30 28 67 10 33 2 13 32 3 32 12 29 50 11 39 33 6 33 6 30 33 12 34 34 16 34 2 31 19 13 27 35 27 35 1 32 7 14 19 36 32 33 2 15 11 37 26 2 10 15 1 16 5 38 17 16 2 1 9 10 1 17 1 39 12 17 13 11 8 40 15 18 30 12 24 2 17 64 1 41 18 19 55 13 55 65 1 42 19 20 68 14 101 72 1 43 9 21 73 15 143 44 4 22 72 16 177 2 16 55 1 45 1 23 74 17 194 56 4 46 1 24 67 18 207 57 3 25 51 19 199 58 2 2 12 25 1 26 28 20 171 63 1 26 5 27 15 21 128 64 1 27 11 28 5 22 99 28 26 29 1 23 69 2 15 47 2 29 42 24 46 48 4 30 52 2 9 12 1 25 25 49 8 31 49 13 5 26 10 50 7 32 36 14 20 27 2 51 2 33 28 15 35 52 1 34 33 16 51 1 8 8 1 54 1 35 34 17 61 9 10 55 4 36 27 18 72 10 27 56 3 37 14 19 64 11 56 57 2 38 7 20 54 12 83 39 2 21 33 13 110 2 14 39 3 40 1 22 18 14 124 40 5 23 5 15 117 41 13 2 11 20 1 24 1 16 99 42 17 21 7 17 79 43 19 22 18 2 8 10 2 18 58 44 9 23 38 11 9 19 33 45 4 24 57 12 16 20 17 46 3 25 67 13 28 21 5 47 5 26 60 14 37 90 l n m k l n m k l n m k l n m k 15 36 37 8 16 4 24 9 16 26 38 4 17 3 25 17 17 17 39 1 18 2 26 24 18 7 40 2 20 2 27 30 19 1 28 37 3 11 24 1 4 15 43 2 29 36 2 7 10 1 26 6 44 2 30 32 11 3 27 10 47 2 31 29 12 3 28 19 48 2 32 26 13 2 29 42 51 1 33 18 14 1 30 42 34 15 31 15 4 14 35 3 35 12 3 17 72 1 32 5 36 4 36 6 33 3 37 3 37 2 3 16 63 3 36 1 38 3 38 2 64 4 39 8 39 2 3 10 17 1 40 7 40 1 3 15 54 1 20 4 41 2 55 3 21 9 42 3 4 11 18 1 56 6 22 10 43 5 19 5 57 2 23 29 44 2 20 13 24 46 45 1 21 28 3 14 45 1 25 36 46 2 22 43 46 2 26 10 47 2 23 53 47 6 27 5 24 55 48 14 28 2 4 13 28 2 25 55 49 14 29 2 29 4 26 51 50 2 33 1 30 7 27 44 51 3 31 12 28 32 3 9 14 1 32 17 29 20 3 13 38 1 16 4 33 15 30 12 39 5 17 10 34 14 31 11 40 6 18 11 35 17 32 7 41 22 19 28 36 15 33 2 42 19 20 16 37 9 43 11 21 10 38 10 4 10 15 2 44 1 22 4 39 9 16 8 45 2 23 3 40 4 17 21 26 1 41 2 18 36 3 12 31 3 42 3 19 51 32 6 3 8 11 2 43 2 20 61 33 8 12 2 44 1 21 62 34 18 13 3 22 53 35 42 14 7 4 12 22 1 23 40 36 36 15 8 23 3 24 31 91 l n m k l n m k l n m k l n m k 25 23 34 9 31 20 43 5 26 11 35 12 32 15 27 3 36 15 33 7 6 12 32 1 37 13 34 2 33 5 4 9 13 4 38 11 34 11 14 10 39 11 5 10 16 1 35 14 15 23 40 7 17 4 36 11 16 32 41 3 18 12 37 5 17 39 42 5 19 22 38 3 18 39 43 4 20 36 19 34 44 1 21 43 6 11 26 4 20 22 45 1 22 46 27 6 21 9 46 1 23 41 28 16 22 2 47 1 24 38 29 10 25 36 30 17 4 8 13 8 5 12 24 1 26 27 31 5 14 6 25 2 27 13 32 6 15 10 26 7 28 3 33 1 16 4 27 10 34 1 17 3 28 18 5 9 14 3 18 1 29 26 15 8 6 10 20 5 30 30 16 16 21 9 5 15 47 2 31 30 17 21 22 8 48 2 32 29 18 27 23 11 51 1 33 24 19 31 24 15 52 1 34 19 20 30 25 12 55 1 35 17 21 22 26 6 36 12 22 8 27 3 5 14 38 1 37 7 23 2 28 3 39 4 38 6 29 2 40 5 39 4 5 8 14 4 41 3 40 1 15 4 6 9 15 4 42 2 16 6 17 9 43 5 5 11 19 1 17 4 19 11 44 4 20 2 18 1 21 8 45 1 21 6 19 1 23 5 46 3 22 13 25 1 47 3 23 25 6 15 56 2 48 1 24 35 6 8 11 2 50 1 25 43 6 14 48 5 14 2 51 1 26 46 49 5 15 2 27 45 18 1 5 13 31 2 28 39 6 13 40 2 19 1 32 7 29 31 41 9 33 9 30 23 42 5 7 15 56 1 92 l n m k l n m k l n m k l n m k 15 1 41 6 26 4 7 14 48 3 16 2 42 5 27 1 49 3 43 6 28 1 8 15 55 1 44 5 7 13 40 2 56 1 45 2 8 8 17 3 41 4 59 1 46 1 18 2 42 4 60 1 19 3 43 2 67 1 8 11 26 1 20 2 27 5 21 1 7 12 32 1 8 14 47 1 28 12 33 3 48 2 29 18 9 14 35 1 34 8 49 1 30 17 37 2 35 9 50 1 31 14 39 2 36 6 51 3 32 12 41 2 37 3 52 3 33 12 38 2 53 2 34 13 9 13 28 1 54 1 35 11 29 2 7 11 26 2 55 1 36 11 30 2 27 6 58 1 37 10 31 3 28 7 59 1 38 5 32 4 29 10 39 2 33 6 30 6 8 13 39 1 34 2 31 5 40 4 8 10 21 1 35 5 32 2 41 6 22 4 36 1 33 1 42 6 23 10 37 4 43 5 24 13 39 1 7 10 20 3 44 6 25 13 21 7 45 5 26 12 9 12 23 2 22 6 46 3 27 16 24 1 23 6 47 3 28 19 25 7 24 9 48 1 29 18 26 4 25 7 49 1 30 13 27 13 26 4 50 3 31 8 28 8 27 2 51 3 32 3 29 13 28 1 52 2 33 1 30 10 29 1 31 10 8 12 32 1 8 9 17 1 32 5 7 9 14 1 33 4 18 4 33 4 16 4 34 9 19 5 34 2 18 6 35 12 20 6 35 1 20 5 36 11 21 8 22 3 37 11 22 11 9 11 19 4 24 1 38 11 23 13 21 12 39 9 24 12 22 2 7 8 12 2 40 8 25 6 23 26 93 l n m k l n m k l n m k l n m k 24 5 28 8 11 13 30 1 20 11 25 29 29 5 31 1 21 20 26 10 30 8 32 5 22 11 27 19 31 5 33 1 23 21 28 8 32 6 34 6 24 9 29 5 33 3 35 3 25 9 30 4 34 2 36 7 26 6 32 1 35 1 37 2 27 2 36 1 38 5 28 3 9 10 15 2 40 4 17 10 10 11 20 3 42 1 11 9 13 1 19 23 22 8 15 10 21 32 23 1 11 12 25 3 16 3 23 26 24 17 26 2 17 14 25 12 25 3 27 7 18 8 27 2 26 17 28 9 19 11 27 5 29 7 20 5 9 9 13 3 28 13 30 16 21 7 15 7 29 5 31 4 22 2 17 13 30 3 32 15 23 2 19 11 31 2 33 3 21 6 33 1 34 11 11 8 11 1 23 2 35 1 13 5 10 10 16 2 36 4 15 6 10 14 36 1 18 7 38 2 16 1 38 1 20 15 17 2 40 2 22 20 11 11 20 1 18 1 42 1 24 15 21 5 26 9 22 5 11 7 11 1 10 13 29 1 28 1 23 14 30 1 24 9 12 14 38 1 31 1 10 9 14 2 25 21 39 1 32 3 16 6 26 15 40 1 33 3 18 5 27 13 41 2 34 3 20 6 28 17 43 2 35 1 22 3 29 5 45 2 36 3 24 2 30 12 37 1 31 1 12 13 31 1 38 2 11 14 37 1 32 5 32 1 40 1 38 1 34 1 33 5 39 1 34 1 10 12 24 1 40 2 11 10 16 1 35 6 25 1 42 2 17 4 36 3 26 5 44 2 18 6 37 7 27 2 19 13 38 2 94 l n m k l n m k l n m k l n m k 39 5 29 2 31 6 21 2 41 4 32 7 22 1 43 1 12 9 14 1 33 4 23 2 15 1 34 3 24 1 12 12 26 3 16 6 35 5 27 2 17 4 36 2 13 8 15 2 28 7 18 13 37 2 18 1 29 9 19 6 38 1 30 7 20 11 39 1 14 14 40 1 31 16 21 5 41 1 41 1 32 4 22 6 42 1 33 15 23 1 13 11 21 1 43 2 34 3 24 1 22 1 45 1 35 11 23 6 47 1 36 1 12 8 12 1 24 6 37 4 14 3 25 10 14 13 33 1 39 2 15 1 26 8 34 2 16 4 27 8 35 5 12 11 21 1 18 1 28 11 36 2 22 5 29 7 37 5 23 4 13 14 40 1 30 6 38 2 24 14 41 1 31 2 39 4 25 9 43 2 32 3 40 1 26 21 45 1 33 3 41 2 27 17 46 1 35 1 43 1 28 13 47 1 29 17 13 10 18 2 14 12 27 2 30 5 13 13 32 1 19 2 28 6 31 11 33 1 20 9 29 5 32 1 34 2 21 6 30 8 33 5 35 3 22 9 31 8 35 1 36 1 23 10 32 10 37 3 24 6 33 7 12 10 17 1 38 3 25 6 34 6 18 3 39 2 26 7 35 5 19 4 40 1 27 2 36 1 20 13 41 2 28 2 37 3 21 11 43 2 29 1 22 21 44 1 30 1 14 11 22 4 23 12 23 5 24 20 13 12 26 1 13 9 15 1 24 11 25 10 27 2 17 4 25 13 26 8 28 5 18 6 26 16 27 6 29 4 19 1 27 11 28 2 30 6 20 7 28 17 95 l n m k l n m k l n m k l n m k 29 9 33 1 39 2 17 14 43 1 30 8 34 2 40 2 45 1 31 2 32 4 15 11 22 4 16 12 29 4 17 13 35 1 23 7 30 3 36 2 14 10 18 2 24 9 31 11 37 1 19 8 25 10 32 4 38 2 20 12 26 11 33 8 39 1 21 15 27 7 34 1 40 2 22 16 28 2 35 2 23 19 29 1 17 12 28 1 24 12 30 1 16 11 23 5 29 1 25 6 24 8 30 3 26 5 15 10 17 4 25 11 31 3 27 2 18 4 26 13 32 3 19 11 27 11 33 3 14 9 15 2 20 9 28 7 34 2 16 4 21 10 29 5 35 1 17 7 22 3 30 1 36 1 18 12 23 3 31 1 19 7 25 1 17 11 22 1 20 5 16 10 18 4 23 2 21 4 15 9 12 1 19 6 24 2 13 3 20 10 25 4 14 8 12 1 14 4 21 12 26 4 14 1 15 6 22 8 27 7 15 1 16 8 23 7 28 2 16 1 17 2 24 3 29 4 20 1 25 2 30 1 15 14 42 1 26 1 31 2 43 1 15 8 9 1 44 1 10 1 16 9 13 1 17 10 17 1 11 3 14 3 19 3 15 13 34 1 12 1 15 4 21 6 35 3 16 6 23 6 36 4 15 7 7 1 17 5 25 3 37 3 18 4 27 1 38 2 16 14 43 1 19 1 39 2 44 1 20 2 17 9 14 1 45 1 21 1 16 3 15 12 28 4 22 1 18 3 29 3 16 13 35 1 20 3 30 10 36 3 16 8 12 1 22 1 31 4 37 4 13 1 24 1 32 7 38 4 96 l n m k l n m k l n m k l n m k 18 14 43 2 15 2 43 1 20 17 44 1 16 2 21 13 45 2 17 4 19 11 21 2 22 7 46 1 18 1 22 7 23 7 47 1 19 1 23 8 24 5 20 1 24 17 26 2 18 13 35 1 25 19 36 3 19 14 43 1 26 30 19 8 12 2 37 4 44 1 27 23 13 1 38 5 45 3 28 29 14 3 39 6 46 1 29 27 16 2 40 2 47 2 30 17 17 2 41 2 50 1 31 25 20 1 51 1 32 10 18 12 29 4 33 9 20 14 44 1 30 7 19 13 34 1 34 5 45 1 31 7 35 2 35 3 48 1 32 12 36 5 36 3 33 11 37 3 37 1 20 13 35 1 34 5 38 8 36 2 35 2 39 6 19 10 16 2 37 2 36 2 40 4 17 6 39 2 41 3 18 4 40 4 18 11 23 5 42 3 19 20 43 1 24 8 43 4 20 14 44 2 25 8 44 2 21 27 26 12 45 3 22 33 20 12 28 1 27 15 48 1 23 31 29 1 28 8 24 36 30 3 29 7 19 12 27 2 25 22 32 9 30 2 28 5 26 23 33 4 32 1 29 7 27 13 35 1 30 11 28 10 36 8 18 10 17 2 31 17 29 9 40 1 18 3 32 11 30 3 19 5 33 18 31 2 20 11 21 1 20 7 34 11 23 2 21 9 35 10 19 9 12 1 25 2 22 9 36 13 13 1 26 10 23 7 37 8 14 2 29 16 24 2 38 7 15 6 32 2 25 2 39 3 16 8 33 2 26 2 40 2 17 17 37 1 41 2 18 9 18 9 14 2 42 1 19 19 20 10 17 1 97 l n m k l n m k l n m k l n m k 20 3 25 1 33 3 23 10 21 10 18 1 26 9 34 2 26 4 20 4 27 9 36 2 29 1 22 7 28 6 37 2 24 8 29 11 39 1 21 14 44 1 26 4 30 8 42 1 45 1 28 1 31 10 46 1 32 4 23 11 23 2 47 1 21 9 16 1 33 4 25 1 52 1 18 2 34 4 26 5 20 3 35 2 27 2 21 13 36 2 36 1 29 4 37 2 22 14 44 1 30 3 38 3 45 1 22 10 20 5 31 1 39 2 47 1 21 1 33 1 40 2 48 1 22 4 34 1 41 2 51 1 23 17 42 1 24 7 23 10 20 3 43 1 22 13 36 2 25 2 22 1 44 1 37 1 26 8 23 4 45 1 38 1 27 5 26 2 39 4 28 2 27 1 21 12 28 1 40 1 29 3 29 3 41 3 31 2 23 9 17 1 30 2 42 3 31 7 44 2 22 9 17 3 24 14 47 1 32 2 45 1 19 2 50 1 33 7 48 1 20 5 34 3 24 1 24 13 39 2 35 5 22 12 28 1 40 4 36 3 30 3 23 14 45 1 42 2 37 2 31 4 48 1 43 2 38 2 32 3 51 1 45 3 39 2 33 5 34 8 23 13 36 1 24 12 33 4 21 11 22 2 35 3 37 2 35 7 24 5 36 7 39 1 36 4 26 10 37 3 40 1 37 4 27 3 38 4 42 2 38 4 28 7 39 3 45 1 39 1 29 7 41 1 48 1 30 4 42 1 24 11 27 5 31 7 23 12 29 1 29 8 32 1 22 11 23 2 30 2 30 10 33 3 24 1 32 3 31 6 98 l n m k l n m k l n m k l n m k 32 14 31 8 31 1 34 2 32 3 27 10 29 5 32 1 33 3 33 1 24 10 24 7 34 5 27 9 24 2 25 2 35 2 29 11 24 1 26 11 36 5 28 13 32 1 25 1 27 2 38 1 34 1 26 2 35 1 27 1 24 9 21 6 25 10 19 1 37 2 28 1 21 2 38 1 25 14 47 1 23 3 29 10 22 1 49 1 25 4 28 12 26 1 50 1 27 5 27 1 30 13 36 1 52 1 29 5 29 4 38 1 57 1 31 2 30 1 33 1 31 2 30 12 29 1 25 13 39 1 32 2 31 1 41 3 25 9 23 1 33 1 32 2 42 2 27 1 34 1 33 1 43 2 35 1 34 1 44 2 26 14 52 1 45 1 28 11 22 1 30 11 25 1 46 2 26 13 44 2 24 3 26 1 47 1 45 3 25 1 27 1 48 1 26 4 28 2 50 1 26 12 37 3 27 1 29 2 38 2 28 1 25 12 31 1 39 2 29 2 30 10 21 1 32 2 31 1 22 1 33 2 26 11 31 2 23 1 34 5 32 5 28 10 20 1 25 2 35 2 22 2 36 7 26 10 26 2 24 1 31 13 35 2 37 1 26 1 36 3 38 5 27 14 55 1 39 1 39 2 28 9 20 1 40 1 40 3 27 13 47 2 41 2 48 4 29 13 33 1 31 12 28 2 42 2 35 1 29 5 43 1 27 12 40 3 37 1 30 1 44 2 41 4 31 1 42 2 29 12 27 1 32 4 25 11 25 1 28 1 33 3 27 5 27 11 34 4 29 1 36 1 29 7 35 10 30 2 99 l n m k l n m k l n m k l n m k 31 11 23 5 28 2 25 2 39 1 24 1 29 1 41 1 25 4 30 1 34 9 18 1 42 1 26 7 31 2 19 1 27 1 36 12 30 1 28 1 33 10 19 3 35 13 37 2 31 1 29 1 20 2 38 1 33 3 21 1 39 1 35 1 31 10 18 1 22 1 40 1 36 2 20 5 23 3 41 1 38 1 22 1 24 2 42 1 36 11 26 1 31 9 15 1 33 9 16 1 35 12 30 2 27 1 17 1 31 1 28 1 32 13 36 3 32 3 29 1 40 1 34 13 36 2 33 3 30 2 39 2 34 5 33 1 32 12 29 4 40 1 35 2 30 4 42 1 36 2 36 10 26 1 33 2 37 1 34 12 28 1 38 1 37 13 38 2 32 11 23 3 30 2 41 2 24 2 31 3 35 11 23 1 44 1 25 1 32 2 24 1 26 2 33 2 25 1 37 12 30 2 27 2 34 4 26 3 32 2 36 2 27 6 33 3 32 10 18 1 38 1 28 6 35 2 20 1 29 5 36 1 22 1 34 11 23 2 30 4 38 2 24 1 31 4 33 13 37 2 25 2 32 1 37 11 23 1 39 2 26 5 33 1 25 2 42 1 27 7 26 1 28 2 35 10 21 3 27 1 33 12 30 2 29 1 22 1 28 1 31 4 30 2 23 3 29 2 32 2 31 1 24 2 30 2 34 4 32 2 25 3 33 1 36 1 26 1 34 10 20 2 37 10 19 1 33 11 24 4 21 2 35 9 18 2 23 1 25 3 22 1 25 1 26 3 23 3 36 13 36 1 27 5 24 2 38 1 38 13 40 1 100 l n m k l n m k l n m k l n m k 42 2 40 12 28 1 22 4 44 9 19 1 43 1 29 1 23 2 45 3 30 1 24 3 45 12 28 1 48 1 31 1 25 4 29 1 26 1 30 2 38 12 32 2 40 11 24 2 27 1 31 1 34 1 26 3 32 2 35 5 27 1 42 9 20 4 33 1 37 4 28 2 21 1 34 1 38 2 22 2 39 3 40 10 20 1 23 1 45 11 22 1 40 1 22 2 24 1 23 3 42 2 24 3 24 2 43 1 26 1 42 8 18 1 25 3 20 1 26 4 38 11 25 1 40 9 20 1 27 2 28 3 22 1 42 7 16 1 28 5 29 1 29 1 30 3 41 12 27 1 43 12 30 2 30 2 31 3 29 1 31 1 31 1 32 3 31 1 32 1 33 1 33 1 45 10 18 3 34 3 41 11 25 2 19 1 35 1 27 1 43 11 26 2 20 5 37 2 29 1 28 3 21 3 29 1 22 3 38 10 22 1 41 10 21 1 30 1 23 4 24 1 23 1 24 1 26 1 27 1 43 10 26 2 26 2 28 3 28 1 32 1 41 9 21 1 44 12 27 1 30 1 45 9 14 1 38 9 24 1 42 12 29 1 32 1 16 4 30 1 33 1 18 3 39 12 27 1 32 2 21 1 29 1 44 11 23 1 30 1 42 11 24 2 25 1 45 8 12 1 25 2 27 1 39 11 23 1 26 1 28 1 46 12 29 1 25 1 27 4 30 1 30 3 27 2 28 1 32 1 29 3 44 10 21 1 33 2 39 10 23 1 30 1 23 1 25 1 25 1 46 11 24 4 42 10 20 1 25 1 101 l n m k l n m k l n m k l n m k 26 3 29 2 33 1 27 6 49 10 26 1 30 2 29 1 54 11 29 1 30 2 50 12 29 3 51 10 23 1 30 1 24 2 55 12 30 1 46 10 19 1 31 2 26 2 32 1 21 5 33 1 27 1 22 2 34 1 55 11 28 1 23 1 51 9 21 2 24 4 50 11 23 2 56 12 29 1 27 1 24 3 52 12 30 2 30 1 25 4 32 1 32 1 46 9 19 2 26 2 34 1 34 1 21 1 27 6 28 1 52 11 25 1 56 11 23 1 47 12 28 1 29 1 26 1 26 2 31 1 31 1 27 1 27 1 33 1 28 2 29 2 34 1 50 10 19 2 29 1 20 2 30 1 56 10 20 1 47 11 24 1 21 6 23 1 26 2 22 2 52 10 23 1 29 1 23 3 24 1 57 12 30 1 31 1 24 2 25 1 33 1 25 2 27 1 47 10 24 1 27 1 58 12 30 1 52 9 21 1 32 1 48 12 29 1 50 9 16 1 34 1 32 2 17 1 53 12 29 1 33 1 18 3 30 1 58 11 25 1 19 3 31 1 28 1 48 11 23 1 21 2 32 2 26 1 33 1 59 12 33 1 30 1 50 8 14 1 16 2 53 11 25 2 60 12 30 1 48 10 21 1 27 1 31 1 50 7 12 1 28 2 32 1 49 12 31 2 29 2 34 1 33 1 51 12 30 1 35 1 34 1 32 2 53 10 24 1 33 1 25 2 60 11 25 1 49 11 26 1 34 1 27 2 28 1 53 9 21 1 28 1 29 1 51 11 26 1 29 1 31 1 28 3 54 12 32 1 32 1 102 l n m k l n m k l n m k l n m k 68 12 33 1 29 2 82 10 26 1 60 10 27 1 31 2 69 12 32 1 83 12 33 1 61 12 30 2 35 2 77 10 23 1 31 1 25 2 83 11 26 1 34 2 69 11 32 1 27 1 78 12 32 1 61 11 24 2 71 12 34 2 35 1 83 10 21 1 27 4 36 1 31 1 71 11 30 1 83 9 16 1 31 1 78 11 26 1 61 10 21 1 29 3 84 12 33 1 24 1 71 10 27 1 32 2 34 1 33 1 36 1 62 12 33 1 73 12 31 2 34 1 34 1 78 10 23 1 84 11 27 2 36 1 26 2 29 1 62 11 30 2 30 1 73 11 24 1 78 9 20 1 62 10 27 1 26 1 84 10 23 1 28 1 80 12 33 1 63 12 32 1 31 1 35 1 85 12 36 1 33 1 36 2 34 1 73 10 23 1 85 11 32 1 80 11 27 1 63 11 30 1 75 12 33 1 28 1 86 12 34 1 35 1 29 1 35 1 63 10 27 1 31 1 36 1 75 11 29 1 64 12 32 1 32 1 80 10 23 1 86 11 29 1 24 1 30 1 65 12 30 1 75 10 26 1 32 1 81 12 32 1 66 12 32 2 76 12 32 1 36 1 86 10 25 1 36 1 34 1 26 1 81 11 29 1 66 11 27 1 76 11 26 1 87 12 34 2 30 1 82 12 33 1 37 1 76 10 21 1 36 1 66 10 25 1 37 1 87 11 28 1 77 12 32 1 30 3 67 12 30 1 35 2 82 11 29 1 33 1 33 1 30 1 35 1 77 11 25 1 33 1 87 10 24 1 28 1 26 1 103 l n m k l n m k l n m k l n m k 103 11 22 1 18 2 88 12 36 1 101 12 45 1 24 1 19 1 37 1 46 1 25 1 20 2 26 1 21 3 88 11 32 2 101 11 39 3 22 2 40 1 103 10 16 1 23 1 89 12 37 1 18 1 24 1 101 10 33 2 19 1 25 1 90 12 37 1 20 2 101 9 27 1 21 1 104 9 13 1 90 11 33 1 22 6 14 3 102 11 21 1 23 1 15 4 91 12 34 2 22 1 16 5 35 1 25 1 103 9 13 1 17 5 38 1 14 2 18 3 102 10 16 1 15 2 19 2 91 11 27 1 17 2 16 6 20 2 28 1 18 2 17 3 21 2 30 1 19 1 18 5 22 1 31 1 20 1 19 5 21 1 20 1 104 8 10 1 92 12 36 1 11 3 37 1 102 9 12 1 103 8 10 2 12 6 13 3 11 2 13 6 92 11 31 1 14 4 12 5 14 7 33 1 15 4 13 5 15 4 16 3 14 5 16 4 92 10 27 1 17 2 15 5 17 2 18 1 16 6 18 1 93 12 36 1 17 1 102 8 9 1 104 7 8 1 94 12 40 1 10 2 103 7 8 3 9 3 11 5 10 6 10 3 95 12 38 1 12 5 11 2 11 4 13 5 12 4 12 3 96 12 38 1 14 3 13 2 13 2 15 1 14 1 14 1 97 12 36 1 15 1 39 1 102 7 7 1 104 11 21 1 40 1 8 2 22 1 105 11 24 1 9 4 25 1 26 2 97 11 32 2 10 5 26 1 27 1 11 3 29 1 28 1 98 12 37 1 12 1 29 1 40 1 104 10 17 1 104 l n m k l n m k l n m k l n m k 105 10 18 1 19 2 36 1 19 1 20 1 111 11 30 1 37 1 20 2 21 1 21 2 22 1 111 10 24 1 113 9 22 1 22 3 25 1 23 1 23 2 107 8 12 1 24 1 24 3 14 1 111 9 19 1 25 1 25 1 15 1 21 1 28 1 26 1 16 2 29 1 17 1 111 8 14 1 30 1 105 9 14 1 15 1 15 2 108 11 30 1 18 1 113 8 16 1 16 3 17 1 17 4 108 10 24 2 111 7 10 1 18 1 18 3 25 2 12 1 19 1 19 5 16 1 20 1 20 3 108 9 18 1 21 1 21 2 19 2 112 11 32 1 22 1 22 2 20 1 33 2 23 1 21 1 34 1 24 1 105 8 12 1 13 2 108 8 13 1 112 10 26 2 113 7 13 1 14 3 14 3 27 2 14 1 15 3 15 1 28 4 15 1 16 2 16 1 16 1 17 3 18 1 112 9 20 1 17 1 18 1 21 3 18 1 110 11 30 1 22 4 19 1 105 7 14 1 23 4 15 1 110 10 24 1 24 1 115 10 17 1 25 1 18 1 107 11 26 1 112 8 16 1 19 1 28 1 110 9 18 1 17 2 20 2 31 1 19 1 18 3 20 1 19 1 115 9 13 2 107 10 20 1 21 1 15 4 21 1 112 7 14 1 16 2 22 1 110 8 13 1 17 3 24 2 14 1 113 11 37 1 18 1 26 1 15 1 38 1 16 1 45 1 115 8 11 2 107 9 15 1 17 1 13 6 16 1 113 10 29 1 15 2 17 1 110 7 11 1 30 1 18 2 13 1 31 1 115 7 9 1 105 l n m k l n m k l n m k l n m k 125 7 9 3 132 9 21 1 116 10 19 1 120 9 18 1 11 2 20 1 12 1 133 10 23 1 121 10 18 1 13 2 26 1 116 9 17 2 22 1 14 1 18 1 133 9 20 1 121 9 16 1 126 10 20 1 116 8 15 2 22 1 135 10 26 1 122 10 20 1 117 10 17 1 126 9 15 1 135 9 22 2 18 1 122 9 16 1 19 1 20 1 17 2 136 10 27 1 21 1 127 10 21 1 123 10 22 1 23 1 137 10 26 1 117 9 13 2 24 1 28 1 15 3 123 9 20 1 16 1 127 9 18 1 137 9 20 1 17 1 124 10 20 1 19 1 21 1 18 1 21 1 20 1 22 1 23 1 117 8 9 1 124 9 16 3 128 10 22 1 11 2 17 4 23 2 137 8 15 1 13 2 17 2 124 8 13 3 128 9 19 1 19 1 118 10 18 1 20 2 20 1 125 10 19 1 137 7 12 1 21 1 21 1 129 10 20 1 13 1 23 1 23 2 118 9 13 1 139 10 25 1 15 1 125 9 14 1 129 9 17 1 16 1 15 1 18 1 140 10 27 2 18 1 16 1 20 1 17 2 140 9 21 1 119 10 18 1 18 2 130 10 20 1 22 4 19 1 19 2 22 1 20 1 21 1 140 8 16 3 21 2 130 9 17 1 17 2 125 8 11 1 18 1 119 9 14 2 12 1 131 10 21 1 16 1 13 4 140 7 12 1 17 1 14 2 131 9 16 1 13 2 18 2 15 2 19 1 16 2 132 10 24 1 141 10 27 1 17 1 26 1 28 1 120 10 20 1 29 1 106 l n m k l n m k l n m k l n m k 23 2 144 8 19 1 24 1 142 7 11 1 150 8 13 1 25 1 12 1 145 10 29 2 26 2 13 1 32 1 150 7 10 1 14 1 141 8 17 1 15 1 145 9 22 3 156 8 14 1 18 2 16 1 25 2 19 2 17 1 156 7 11 1 20 2 18 1 145 8 16 2 21 1 19 1 157 8 15 1 143 10 29 1 141 7 14 1 145 7 11 1 158 8 17 1 15 2 143 9 23 1 19 1 16 1 24 1 146 10 32 1 158 7 14 1 142 10 27 1 143 8 18 1 147 9 20 1 15 1 29 1 20 1 23 1 33 1 24 1 161 8 19 1 143 7 13 1 142 9 20 1 14 1 147 8 17 2 167 7 10 1 22 1 24 1 144 10 28 1 148 9 27 1 168 7 12 1 25 1 30 1 13 1 27 1 34 1 148 8 21 1 169 7 12 1 142 8 14 1 144 9 23 1 149 8 10 1 16 1 25 1 12 1 170 7 13 1 Literatura [1] D. M. Cvetkovic´, Teorija grafova i njene primene, Naucˇna knjiga, Beograd, 1981. [2] D. M. Cvetkovic´, M. Doob, I. Gutman, A. Torgasˇev, Recent results in the Theory of graph Spectra, Ann. Discrete Math. 36, North-Holland, Amsterdam, 1988. [3] D. M. Cvetkovic´, M. Doob, H. Sachs, Spectra of Graphs – Theory and Appli- cation, VEB Deutscher Verlag der Wissenschaften, Berlin 1980. [4] D. Cvetkovic´, M. Petric´, A table of connected graphs on six vertices, Discrete Math.,50 (1984), 37–49. [5] D. Cvetkovic´, P. Rowlinson, S. Simic´, Eigenspaces of graphs, Cambridge University Press (Cambridge), 1997. [6] R. Grone, R. Merris, V. S. Sunder, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl. 11 (1990), 218–238. [7] G. H. Hardy, E. M. Wright, An introduction to the theory of numbers, 4th edition, Oxford at the Clarendon Press, 1960. [8] M. Lazic´, On the p-reduced Energy of a Graph, Mathematica Moravica, Vol. 9(2005), 17–20. [9] M. Lazic´, Graphs whose reduced Energy does not exceed 3, Publ. Inst. Math., Nouv. Ser. 77(91) (2005), 53–60. [10] M. Lazic´, Some results on symmetric double starlike trees, Journal of Applied Mathematics and Computing Vol. 21 (2006), No. 1–2, 215–222. [11] M. Lazic´, Maximal canonical graphs with 7 nonzero eigenvalues, Publ. Inst. Math., Nouv. Ser. (rad prihvac´en za sˇtampu u oktobru 2008.) [12] M. Lepovic´, Maximal canonical graphs with 6 nonzero eigenvalues, Glasnik Mat. (Zagreb), 25 (1) (1990), 683–686. [13] M. Lepovic´, Some results on the reduced energy of graphs, III Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 2 (1991), 82–88. [14] M. Lepovic´, Solving some hereditary problems in spectral graph theory, dok- torska disertacija, Univerzitet u Beogradu, Beograd, 1991. 107 108 [15] M. Lepovic´, Some kinds of energies of graphs, Discrete Mathematics, 128( 1994), 277–282. [16] M. Lepovic´, On Spectral complementary Graphs, Novi Sad J. Math. Vol. 30. No. 3 (2000), 83–91. [17] M. Lepovic´, Some results on starlike trees and sunlike graphs, J. Appl. Math. and Computing Vol. 11 (2003), No. 1–2, 109–123. [18] M. Lepovic´, On Integral Graphs which belong to the class αKa ∪ βKb, J. Appl. Math. and Computing, Vol 14 (2004), No. 1–2, 39–49. [19] M. Lepovic´, I. Gutman, No starlike trees are cospectral, Discrete Mathematics 242 (2002), 291–295. [20] M. Petrovic´, Z. Radosavljevic´, Spectrally constrained graphs, Faculty of Science, Kragujevac, 2001. [21] A. Torgasˇev, On infinite graphs with three and four nonzero eigenvalues, Bull. Acad. Serbe Sci. Arts. (Sci. Mat.) (76) 11 (1981), 39–48. [22] A. Torgasˇev, On infinite graphs with five nonzero eigenvalues, Bull. Acad. Serbe Sci. Arts. (Sci. Mat.) (79) 12 (1982), 31–38. [23] A. Torgasˇev, Graphs whose energy does not exceed 3, Czechoslovak Mathemat- ical Journal, 36 (1986), 167–171. [24] A. Torgasˇev, A property of canonical graphs, Publ. Inst. Math., Nouv. Ser. 50(64) (1991), 33–38 (Beograd). Dodatak Summary This doctoral dissertation belongs to the Spectral theory of finite and infinite graphs, which joins elements of Graph theory, Linear algebra and General theory of operators. Graph theory, as special mathematical discipline, is around seven decades old. The developments of the computational techniques asked the construction of suitable math- ematical apparatus due to which, directly and indirectly, Graph theory has begun its development intensively, being applied in different scientific fields, and very large popu- larity. The application of Graph theory and its methods take an important role in the theory of electrical circuits, in the theory of systems of automatic control, in the theory of finite automats, operational research, in Informatics, in Chemistry, in Economics, Sociology, Biology etc. Hereby, we describe in short the content of this dissertation. The dissertation, consists of four chapters divided in sections, Appendix and Refer- ences. In Chapter 1, some results on the reduced energy of graphs are given. This chapter consists of three sections. In section 1.1, some basic notions which will be used in this and the next chapter are given. Section 1.2 consists of results from [9]. In this section all connected graphs whose reduced energy does not exceed 3 are described. In the paper [13] by M. Lepovic´, all connected graphs whose reduced energy does not exceed 2, 5 are completely described. In the section 1.3 we introduced definitions of some other kinds of the p–reduced energies and we proved some of their properties. This last part of the Section 1 is related on the results from [8]. In Chapter 2 all finite and infinite graphs with seven nonzero eigenvalues are deter- mined. This chapter consists of three sections. The problem of characterization of all connected graphs with exactly p = 3, 4, 5 nonzero eigenvalues was considered by A. Torgasˇev in [21], [22], and for p = 6 by M. Lepovic´ in [12], [14]. In section 2.1, some basic properties and definitions from the Spectral theory of canon- ical graphs are given. In section 2.2, we characterized all connected infinite graphs with exactly seven nonzero eigenvalues. Since it is almost impossible to expose this whole list, we have succeeded to make a condensation of this result by making a computer program for separating maximal 109 110 graphs from this set. This result is given in section 2.3. Some results on integral graphs are given in Chapter 3. This chapter consists of three sections. In section 3.1 we considered some problems related to integral graphs. We say that a graph G is integral if its spectrum σ(G) consists of integral values. In 1973 F. Harrary and A. Swank posed the following problem: Which graphs are integral? This problem is very hard and it is not solved in general case. Namely, it is demonstrated in several papers that this problem (in mostly cases) is reduced to the problem of finding the most general integral solution of some Diophantine equations (see [18]). In this chapter we described some classes of integral graphs. In this work this problem is reduced to the problem of finding the most general integral solution of some Diophantine equations of second order. In section 3.2 we defined necessary and sufficient conditions under which G ⋃ G is integral (G is a regular integral graph). In section 3.3, we considered family of integral complete tripartite graphs Kk,m,n, for k ≥ m ≥ n. We completely described this family in the cases k > m = n and k = m > n. Chapter 4 contains some results on symmetric double starlike trees. This chapter consists of three sections. In section 4.1, the definitions of starlike tree and double starlike tree are given. Some auxiliary results are given in section 4.2. Finally, in the section 4.3, we proved that there exist no two cospectral non-isomorphic symmetric double starlike trees. 111 Biografija Mirjana Lazi} je ro|ena 28.oktobra 1959.godine u Kragujevcu. Osnovnu {kolu "Sve- tozar Markovi}" u Kragujevcu zavr{ila je kao nosilac diplome "Vuk Karaxi}", a Prvu Kragujeva~ku gimnaziju sa odli~nim uspehom. Prirodno-matemati~ki fakultet u Kragujevcu, studijska grupa matematika, upisala je 1978.godine, a zavr{ila 1982. godine. Poslediplomske magistarske studije zavr{ila je na Matemati~kom fakultetu Uni- verziteta u Beogradu 9.05.1996.godine, odbranom magistarske teze iz oblasti matemati~ke lingvistike pod nazivom "Analiza i sinteza tipi~nih re~enica u malim oglasima". Od januara 1985.godine radi u zvawu asistenta pripravnika u Institutu za matematiku i informatiku Prirodno-matemati~kog fakulteta u Kragujevcu. U zvawe asistenta izabrana je u januaru 1997.godine za u`u nau~nu oblast Programirawe. U dosada{wem radu u Institutu za matematiku i informatiku Prirodno- matemati~kog fakulteta u Kragujevcu, od 1985. do danas, dr`ala je ve`be iz predmeta: Matemati~ka logika i skupovi, Analiti~ka geometrija, Linearna algebra i analiti~ka geometrija, Ra~unarstvo 2, Softverski praktikum i Softverski praktikum 1, Teori- jske osnove informatike 3, Statistika 2, Matematika, Matematika 1 i Matematika 2 (za studente Hemije), Matematika 1 i Matematika 2 (za studente Ma{inskog akulteta) i Matematika 1 (za studente Fizike). Mirjana Lazi} se bavi nau~noistra`iva~kim radom iz oblasti spektralne teorije grafova. Rezultate istra`ivawa objavila je u okviru slede}ih nau~nih radova: 1. M. Lazi}, Formal grammar for a fragment of the Serbian language, Kragujevac Journal of Mathematics, 24(2002), 147–178. 2. M. Lazi}, A Prolog program for analysis and synthesis of typical sentences taken from advertisements, Kragujevac Journal of Mathematics, 24(2002), 179–192. 3. M. Lazi}, A note on λ2 and λn of a Graph, Mathematica Moravica, Vol. 8(2004), 11–14. 4. M. Lazi}, Graphs whose reduced Energy does notexceed 3, Publ. Inst. Math., Nouv. Ser. 77(91) (2005), 53–60. 5. M.Lazi}, Interlacing Theorem for the Laplacian Spectrum of a Graph, Mathematica Moravica, Vol. 9(2005), 13–16. 6. M. Lazi}, On the p-reduced Energy of a Graph, Mathematica Moravica, Vol. 9(2005), 17–20. 7. M. Lazi}, On the Laplacian energy of a graph, Czechoslovak Mathematical Journal, 56 (131) (2006), 1207–1213. 8. M. Lazi}, Some results on symmetric double starlike trees, Journal of Applied Mathematics and Computing Vol. 21 (2006), No. 1–2, 215–222. 9. M. Lazi}, Maximal canonical graphs with 7 nonzero eigenvalues, Publ. Inst. Math., Nouv. Ser. (rad prihva}en za {tampu u oktobru 2008.) 112 10. Q. Pavlovi}, M. Lazi}, T. Aleksi} More on ”Connected (n,m)–graphs with min- imum and maximum zeroth–order general Randic´ index”, Discrete Applied Mathe- matics, (rad prihva}en za {tampu u januaru 2009.) 11. M. Torga{evPetrovi}, M. Lazi}, Zbirka re{enih zadataka iz matematike 1, Ma{inski fakultet u Kragujevcu, ISBN 86-80581-54-2, Kragujevac, 2003.