Neke klase grafova sa datim ograničenjima druge sopstvene vrednosti

Abstract

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 <r (za r > 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<5+1/2. Takođe je razmatrano ograničenje 3 (kao i u [28]) i opisani su sva stabla sa dijametrom 3 i dijametrom većim od 8, sa osobinom λ2 <3 , kao i svi GRS-neodlučivi multiciklički kaktusi sa istom osobinom. Na kraju su uvedene i primenjene tzv. σ-modifikacije Smitovih stabala. Opisano je sedam σ-modifikacija i odgovarajućih ekstenzija i uočeno je njihovo pojavljivanje u (već poznatim) rezultatima u klasi multicikličkih refleksivnih kaktusa sa 4 konture. Primenom nekih ekstenzija na određene familije tricikličkih kaktusa na drugi način se došlo do rezultata u klasi multicikličkih refleksivnih kaktusa sa 4 konture [48]. Na kraju disertacije, u zaključku, ukazano je na moguće pravce daljih istraživanja.

The subject of this dissertation belongs to scientific field of spectral graph theory, a young branch of mathematical combinatorics, i.e. graph theory, which finds important applications in many areas, such as chemistry, physics, computer science, telecommunications, sociology, etc., and various fields of mathematics. Spectral graph theory connects basic properties and the structure of a graph with characteristics of the spectra of its matrices (adjacency matrix, Laplacian matrix, etc.). In this dissertation we only work with the adjacency matrix. The second largest eigenvalue of the adjacency matrix of a graph (or, simply, second largest eigenvalue of a graph), as well as its distance from the largest eigenvalue, are very important especially in applications of spectral graph theory in computer science. The property of a graph that one of its eigenvalues does not exceed some given value is a hereditary one; therefore, many of the investigations of this kind have been directed at finding the maximal allowed graphs, or minimal forbidden graphs for that property. In this dissertation we determine some classes of graphs whose second largest eigenvalue does not exceed some given value, and, for that purpose, we develop some very useful tools. In methodological sense, investigations in this dissertation represent a combined approach consisting of application of the algebraic apparatus and methods of spectral graph theory and combinatorial reasoning, whilst at some stages the expert system newGRAPH has been used. The dissertation consists of eight chapters, each of which is divided into subchapters. In the beginning, some important previous work is shown, and afterwards we present some original elements of the algebraic and combinatorial apparatus that speed up and simplify the further work. We define some mappings between certain families of graphs, some of which preserve the sign of the expression λ2 - 2 , and, using them, we describe and systematize some (already known) results in a new way. Further on we completely determine all maximal reflexive tricyclic cacti which are not RS-decidable and whose cycles do not form a bundle, from the classes R1 and R3 , and we give some partial results about the class R2 , using previously induced mappings (until now only the graphs from the remaining class R4 have been completely determined [40], [46]). Next, we completely describe all minimal forbidden graphs in the class of bicyclic graphs with a bridge, and all minimal forbidden graphs in the class R3 - the approach that so far has never been used with reflexive graphs. Then we determine the maximal number of the cycles for RS-undecidable reflexive cacti whose cycles do form a bundle, and, therefore, generally for RS-undecidable reflexive cacti and we describe three classes of maximal reflexive RS-undecidable reflexive cacti that contain a bundle. Further on, some of the previous results are generalized: the generalized RS-theorem is stated and proved (so-called GRS-theorem) for any r , r > 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 <5+1/2. Furthermore, we investigate the limit 3 (as in [28]) and we describe all trees with the diameter 3 and the diameter larger than 8, with the property λ2 < 3 , as well as all GRSundecidable multicyclic cacti with the same property. Finally, we introduce and apply so-called σ-modifications of Smith trees. We describe seven σ-modifications and corresponding extensions, and we notice the appearance in (already known) results in the class of multicyclic reflexive cacti with 4 cycles. Applying some extensions to certain families of tricyclic cacti, we obtained the results in the class of multicyclic reflexive cacti with 4 cycles, using a different approach [48]. Finally, in the conclusion, we suggest some possible directions of further investigations.