Title
Neke klase spektralno ograničenih grafova
Creator
Koledin, Tamara D.
Copyright date
2013
Object Links
Select license
Autorstvo-Nekomercijalno-Bez prerade 3.0 Srbija (CC BY-NC-ND 3.0)
License description
Dozvoljavate samo preuzimanje i distribuciju dela, ako/dok se pravilno naznačava ime autora, bez ikakvih promena dela i bez prava komercijalnog korišćenja dela. Ova licenca je najstroža CC licenca. Osnovni opis Licence: http://creativecommons.org/licenses/by-nc-nd/3.0/rs/deed.sr_LATN. Sadržaj ugovora u celini: http://creativecommons.org/licenses/by-nc-nd/3.0/rs/legalcode.sr-Latn
Language
Serbian
Cobiss-ID
Theses Type
Doktorska disertacija
description
Datum odbrane: 08.07.2013.
Other responsibilities
mentor
Stanić, Zoran. 1975-
član komisije
Cvetković, Dragoš M
član komisije
Radosavljević, Zoran, 1949-
član komisije
Dugošija, Đorđe, 1948-
Academic Expertise
Prirodno-matematičke nauke
University
Univerzitet u Beogradu
Faculty
Matematički fakultet
Alternative title
Some classes of spectrally constrained graphs
Publisher
[T. Koledin]
Format
PDF/A (157 listova)
description
Matematika-Algebarska teorija grafova / Mathematics-Algebraic graph theory
Abstract (sr)
Spektralna teorija grafova je grana matematike koja je nastala pedesetih godina
pro²log veka i od tada se neprestano razvija. Njen zna£aj ogleda se u brojnim
primenama, naro£ito u hemiji, zici, ra£unarstvu i drugim naukama. Grane matematike,
kao ²to su linearna algebra i, posebno, teorija matrica imaju vaºnu ulogu
u spektralnoj teoriji grafova. Postoje razli£ite matri£ne reprezentacije grafa. Najvi
²e su izu£avane matrica susedstva grafa i Laplasova (P.S. Laplace) matrica, a
zatim i Zajdelova (J.J. Seidel) i takozvana nenegativna Laplasova matrica. Spektralna
teorija grafova u su²tini uspostavlja vezu izmeu strukturalnih osobina grafa i
algebarskih osobina njegove matrice, odnosno razmatra o kojim se strukturalnim
osobinama (kao ²to su povezanost, bipartitnost, regularnost i druge) mogu dobiti
informacije na osnovu nekih svojstava sopstvenih vrednosti njegove matrice. Veliki
broj dosada²njih rezultata iz ovog ²irokog polja istraºivanja moºe se na¢i u slede¢im
monograjama: [20], [21], [23] i [58].
Disertacija sadrºi originalne rezultate dobijene u nekoliko podoblasti spektralne
teorije grafova. Ti rezultati izloºeni su u tri celine glave, od kojih je svaka podeljena
na poglavlja, a neka od njih na potpoglavlja. Na po£etku svake glave, u posebnom
poglavlju, formulisan je problem koji se u toj glavi razmatra, kao i postoje¢i rezultati
koji se odnose na zadati problem, a neophodni su za dalja razmatranja. U ostalim
poglavljima predstavljeni su originalni rezultati, koji se nalaze i u radovima [3], [4],
[47], [48], [49], [50], [51] i [52].
U prvoj glavi razmatra se druga sopstvena vrednost regularnih grafova. Postoji
dosta rezultata o grafovima £ija je druga po veli£ini sopstvena vrednost ograni£ena
odozgo nekom (relativno malom) konstantom. Posebno, druga sopstvena vrednost
ima zna£ajnu ulogu u odreivanju strukture regularnih grafova. Poznata je karakterizacija
regularnih grafova koji imaju samo jednu pozitivnu sopstvenu vrednost
(videti [20]), a razmatrani su i regularni grafovi sa osobinom 2 ≤ 1 (videti [64]). U
okviru ove disertacije pro²iruju se rezultati koji se nalaze u radu [64], a predstavljaju
se i neki op²ti rezultati koji se odnose na vezu odreenih spektralnih i strukturalnih
osobina regularnih nebipartitnih grafova bez trouglova...
Abstract (en)
Spectral graph theory is a branch of mathematics that emerged more than sixty years
ago, and since then has been continuously developing. Its importance is reected
in many interesting and remarkable applications, esspecially in chemistry, physics,
computer sciences and other. Other areas of mathematics, like linear algebra and
matrix theory have an important role in spectral graph theory. There are many
dierent matrix representations of a given graph. The ones that have been studied
the most are the adjacency matrix and the Laplace matrix, but also the Seidel
matrix and the so-called signless Laplace matrix. Basically, the spectral graph
theory establishes the connection between some structrural properties of a graph
and the algebraic properties of its matrix, and considers structural properties that
can be described using the properties of the eigenvalues of its matrix. Systematized
former results from this vast eld of algebraic graph theory can be found in the
following monographs: [20], [21], [23] i [58].
This thesis contains original results obtained in several subelds of the spectral
graph theory. Those results are presented within three chapters. Each chapter is
divided into sections, and some sections into subsections. At the beginning of each
chapter (in an appropriate sections), we formulate the problem considered within
it, and present the existing results related to this problem, that are necessary for
further considerations. All other sections contain only original results. Those results
can also be found in the following papers: [3], [4], [47], [48], [49], [50], [51] and [52].
In the rst chapter we consider the second largest eigenvalue of a regular graph.
There are many results concerning graphs whose second largest eigenvalue is upper
bounded by some (relatively small) constant. The second largest eigenvalue plays
an important role in determining the structure of regular graphs. There is a known
characterization of regular graphs with only one positive eigenvalue (see [20]), and
regular graphs with the property 2 ≤ 1 have also been considered (see [64]). Within
this thesis we extend the results given in [64], and we also present some general
results concerning the relations between some structural and spectral properties of
regular triangle-free graphs...
Authors Key words
matrica susedstva grafa, nenegativna Laplasova matrica grafa, spektar
grafa, nenegativni Laplasov spektar grafa, druga sopstvena vrednost, regularan
graf, bipartitni graf, ugneºeni graf, uravnoteºena nekompletna blok-²ema, delimi
£no uravnoteºena nekompletna blok-²ema
Authors Key words
adjacency matrix, signless Laplace matrix, graph spectrum, signless La-
place spectrum, second largest eigenvalue, regular graph, bipartite graph, nested
graph, balanced incomplete block design, partially balanced incomplete block de-
sign
Classification
519.1
Subject
Teorija grafova
Type
Tekst
Abstract (sr)
Spektralna teorija grafova je grana matematike koja je nastala pedesetih godina
pro²log veka i od tada se neprestano razvija. Njen zna£aj ogleda se u brojnim
primenama, naro£ito u hemiji, zici, ra£unarstvu i drugim naukama. Grane matematike,
kao ²to su linearna algebra i, posebno, teorija matrica imaju vaºnu ulogu
u spektralnoj teoriji grafova. Postoje razli£ite matri£ne reprezentacije grafa. Najvi
²e su izu£avane matrica susedstva grafa i Laplasova (P.S. Laplace) matrica, a
zatim i Zajdelova (J.J. Seidel) i takozvana nenegativna Laplasova matrica. Spektralna
teorija grafova u su²tini uspostavlja vezu izmeu strukturalnih osobina grafa i
algebarskih osobina njegove matrice, odnosno razmatra o kojim se strukturalnim
osobinama (kao ²to su povezanost, bipartitnost, regularnost i druge) mogu dobiti
informacije na osnovu nekih svojstava sopstvenih vrednosti njegove matrice. Veliki
broj dosada²njih rezultata iz ovog ²irokog polja istraºivanja moºe se na¢i u slede¢im
monograjama: [20], [21], [23] i [58].
Disertacija sadrºi originalne rezultate dobijene u nekoliko podoblasti spektralne
teorije grafova. Ti rezultati izloºeni su u tri celine glave, od kojih je svaka podeljena
na poglavlja, a neka od njih na potpoglavlja. Na po£etku svake glave, u posebnom
poglavlju, formulisan je problem koji se u toj glavi razmatra, kao i postoje¢i rezultati
koji se odnose na zadati problem, a neophodni su za dalja razmatranja. U ostalim
poglavljima predstavljeni su originalni rezultati, koji se nalaze i u radovima [3], [4],
[47], [48], [49], [50], [51] i [52].
U prvoj glavi razmatra se druga sopstvena vrednost regularnih grafova. Postoji
dosta rezultata o grafovima £ija je druga po veli£ini sopstvena vrednost ograni£ena
odozgo nekom (relativno malom) konstantom. Posebno, druga sopstvena vrednost
ima zna£ajnu ulogu u odreivanju strukture regularnih grafova. Poznata je karakterizacija
regularnih grafova koji imaju samo jednu pozitivnu sopstvenu vrednost
(videti [20]), a razmatrani su i regularni grafovi sa osobinom 2 ≤ 1 (videti [64]). U
okviru ove disertacije pro²iruju se rezultati koji se nalaze u radu [64], a predstavljaju
se i neki op²ti rezultati koji se odnose na vezu odreenih spektralnih i strukturalnih
osobina regularnih nebipartitnih grafova bez trouglova...
“Data exchange” service offers individual users metadata transfer in several different formats. Citation formats are offered for transfers in texts as for the transfer into internet pages. Citation formats include permanent links that guarantee access to cited sources. For use are commonly structured metadata schemes : Dublin Core xml and ETUB-MS xml, local adaptation of international ETD-MS scheme intended for use in academic documents.