Some classes of graphs with given bound for second largest eigenvalue

Autor: Mihailović, Bojana Lj.
Přispěvatelé: Radosavljević, Zoran, Dražić, Milan, Stanić, Zoran, Rašajski, Marija
Jazyk: srbština
Rok vydání: 2016
Předmět:
Zdroj: Универзитет у Београду
Popis: Predmet ove disertacije pripada oblasti spektralne teorije grafova, mladoj grani matematičke kombinatorike, odnosno teorije grafova, koja u današnje vreme nalazi važne primene u mnogim poljima, kao što su hemija, fizika, računarstvo, telekomunikacije, sociologija, itd. kao i razne oblasti matematike. Spektralna teorija grafova dovodi u vezu osnovne osobine i strukturu grafa sa osobinama spektra njegovih matrica (matrice susedstva, Laplasove matrice itd.). U ovoj disertaciji reč je isključivo o spektru matrice susedstva grafa. Druga po veličini sopstvena vrednost matrice susedstva grafa (kraće, druga sopstvena vrednost grafa), kao i njeno rastojanje od najveće sopstvene vrednosti, od značaja su naročito za primenu spektralne teorije u računarstvu. Osobina grafa da mu posmatrana sopstvena vrednost ne prevazilazi dato ograničenje jeste nasledna osobina, pa su mnoga istraživanja o ovakvim ograničenjima išla u pravcu nalaženja maksimalnih dozvoljenih grafova ili nalaženja minimalnih zabranjenih grafova za tu osobinu. Ova disertacija bavi se određivanjem nekih klasa grafova koje imaju dato ograničenje druge sopstvene vrednosti matrice susedstva grafa i u tom cilju razvija neke vrlo korisne instrumente. U metodološkom smislu istraživanja u ovoj disertaciji predstavljaju spregu primene algebarskog aparata i metoda spektralne teorije grafova i kombinatorog rezonovanja, dok je u pojedinim fazama korišćen i ekspertni sistem newGRAPH. Disertacija sadrži osam glava, koje su podeljene na delove. Na početku se navode prethodni rezultati, a zatim se uvode i razvijaju novi i originalni elementi algebarsko-kombinatornog aparata koji ubrzava i olakšava dalji rad. Definišu se preslikavanja između određenih familija grafova, od kojih neka čuvaju znak izraza λ2 - 2 i pomoću njih se opisuju i sistematizuju neki već poznati rezultati na nov način. Zatim se u potpunosti određuju svi maksimalni refleksivni triciklički kaktusi koji nisu RS-odlučivi i čije konture ne čine snop iz klasa R1 i R3 i daju parcijalni rezultati koji se tiču klase R2 , uz primenu prethodno uvedenih preslikavanja (dosad su u potpunosti bili određeni samo oni iz preostale klase R4 [40], [46]). Dalje se kompletno opisuju svi minimalni zabranjeni grafovi u klasi bicikličkih grafova sa mostom i svi minimalni zabranjeni grafovi u klasi R3 - pristup koji kod refleksivnih grafova još nije bio korišćen. Zatim se određuje maksimalan broj kontura za RS-neodlučive refleksivne kaktuse za slučaj kad konture sadrže snop, a time i uopšte za RS-neodlučive refleksivne kaktuse, i opisuju tri klase maksimalnih refleksivnih RS-neodlučivih kaktusa koji sadrže snop kontura. Posle toga su uopšteni neki prethodni rezultati: iskazano je i dokazano uopštenje RS-teoreme (tzv. GRS-teorema) za bilo koje r, r > 0 ; uopštena su prethodno uvedena preslikavanja, dokazane su osobine uopštenja i dati različiti primeri klasa grafova sa osobinom λ2 0 ). Na osnovu prethodnog, opisani su svi GRSneodlučivi maksimalni grafovi za osobinu λ2 < 2 u klasi unicikličkih i multicikličkih kaktusa i svi GRS-neodlučivi maksimalni θ-grafovi za isto svojstvo, kao i sva GRSneodlučiva maksimalna stabla sa osobinom λ2 0 ; previously induced mappings are generalized, their properties are proved and various examples of classes of graphs with the property λ2 - < r (for r > 0 ) are given. Based on this, we describe all GRS-undecidable maximal graphs for the property λ2 < 2 in the class of unicyclic and multicyclic graphs, and also all RS-undecidable maximal θ-graphs for this property as well as all GRS-undecidable maximal trees with the property λ2
Databáze: OpenAIRE
Externí odkaz: