NEKE KLASE GRAFOVA SA DATIM OGRANIČENJEM DRUGE SOPSTVENE VREDNOSTI

eBiblioteka

 
 

NEKE KLASE GRAFOVA SA DATIM OGRANIČENJEM DRUGE SOPSTVENE VREDNOSTI

Show simple item record

dc.contributor.advisor Radosavljević, Zoran
dc.contributor.author Mihajlović, Bojana
dc.date.accessioned 2017-03-21T16:29:09Z
dc.date.available 2017-03-21T16:29:09Z
dc.date.issued 2016
dc.identifier.uri http://hdl.handle.net/123456789/4445
dc.description.abstract 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 1 R and 3 R , and we give some partial results about the class 2 R , using previously induced mappings (until now only the graphs from the remaining class 4 R 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 3 R - 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. en_US
dc.description.provenance Submitted by Slavisha Milisavljevic (slavisha) on 2017-03-21T16:29:09Z No. of bitstreams: 1 Mihailovic_Bojana.pdf: 6960465 bytes, checksum: b4ecddba155d33bd6c52562bbdc35200 (MD5) en
dc.description.provenance Made available in DSpace on 2017-03-21T16:29:09Z (GMT). No. of bitstreams: 1 Mihailovic_Bojana.pdf: 6960465 bytes, checksum: b4ecddba155d33bd6c52562bbdc35200 (MD5) Previous issue date: 2016 en
dc.language.iso sr en_US
dc.publisher Beograd en_US
dc.title NEKE KLASE GRAFOVA SA DATIM OGRANIČENJEM DRUGE SOPSTVENE VREDNOSTI en_US
mf.author.birth-date 1960
mf.author.birth-place Beograd en_US
mf.author.birth-country Srbija en_US
mf.author.residence-state Srbija en_US
mf.author.citizenship Srpsko en_US
mf.author.nationality Srpkinja en_US
mf.subject.area Mathematics en_US
mf.subject.keywords spectral graph theory, second largest eigenvalue, hereditary graph property, maximal graphs, minimal forbidden graphs, treelike graphs (cacti), reflexive graphs en_US
mf.subject.subarea Spectral graph theory en_US
mf.contributor.committee Dražić, Milan
mf.contributor.committee Stanić, Zoran
mf.contributor.committee Rašajski, Marija
mf.university.faculty Mathematical Faculty en_US
mf.document.references 58 en_US
mf.document.pages 210 en_US
mf.document.location Beograd en_US
mf.document.genealogy-project No en_US
mf.university Belgrade University en_US

Files in this item

Files Size Format View
Mihailovic_Bojana.pdf 6.960Mb PDF View/Open

This item appears in the following Collection(s)

Show simple item record