KRITIČNI GRAFOVI DIJAMETRA 2

eLibrary

 
 

KRITIČNI GRAFOVI DIJAMETRA 2

Show simple item record

dc.contributor.advisor Živković, Miodrag
dc.contributor.author Radosavljević, Jovan
dc.date.accessioned 2023-09-15T12:18:51Z
dc.date.available 2023-09-15T12:18:51Z
dc.date.issued 2023-08-10
dc.identifier.uri http://hdl.handle.net/123456789/5594
dc.description.abstract Graph G = (V,E) is an ordered pair of set of nodes V and branches E. Order graph G is the number of nodes |V |, and its size is the number of branches |E|. Knots u, v ∈ V are adjacent if there is a branch uv ∈ E between them. Distance dist(u, v) nodes u and v G is the length of the shortest path from u to v. The diameter of the graph G is the largest distance dist(u, v) let two nodes in, v. They are discussed in the dissertation graphs of diameter 2. Intuitively, the notion that graphs are dia- meters 2 simple structures; however, they are known to be asymptotically close all graphs of diameter 2. That is why a narrower class is interesting — class D2C of critical graphs of diameter 2, i.e. graphs where the removal of any branches leads to an increase in diameter. In addition, a narrower class of pri- mitive D2C (PD2C) graphs, i.e. D2C graphs that do not have two nodes with the same set of neighbors. In the introductory chapter 2, the basic concepts, algorithms and dings used in the dissertation. They are presented in the following chapters original results regarding diameter graphs 2. Chapter 3 describes the procedure for obtaining a list of D2C graphs of order up to 13. With built-in parallelization, the creation of a list of D2C graphs of order up to 13 it lasted a month. This was a step forward, because previously there was a spi- around all graphs of diameter 2 lines up to 10. The obtained results were used for testing several known hypotheses about graphs of diameter 2. In chapter 4 it is shown that for every m ⩾ 3 a D2C graph containing cli- a ku of size m must have at least 2m nodes. At the same time, with accuracy up to isomorphism, there is exactly one graph of size 2m that contains a clique of characters m. Chapter 5 discusses PD2C graphs with the smallest number of branches. From list of all PD2C graphs of order n ⩽ 13 are selected PD2C graphs of size at most 2n − 4. Only three of the isolated graphs are of size 2n − 5, which is in accordance with the statement of the Erdes-Renji theorem about the lower bound for the size graphs of diameter 2 that do not contain a node adjacent to all other nodes (that limit is 2n − 5). PD2C graphs of size 2n − 4 rows up to 13 sorted are in three groups: • The first group belongs to the Z family, defined in the dissertation, which for each n ⩾ 6 contains exactly one PD2C graph of order n of size 2n − 4. • The second group consists of seven Hamiltonian PD2C graphs of order at most 9 of size 2n−4. In the dissertation it was proved that there is no such Hamil- tone graph of order greater than 11, i.e. that the seven graphs found are the only ones Hamiltonian PD2C graphs of size 2n − 4. • The third group consists of a unique graph that does not belong to any of the first two groups. Based on these results, the hypothesis was formulated that all PD2C graphs re- that n ⩾ 10 and sizes 2n − 4 belong to the family Z. Keywords: graphs, critical graphs of diameter 2, primitive graph- You Scientific field: Computing and informatics Narrower scientific field: Graph theory UDC number: 004.415.5(519.1 en_US
dc.description.provenance Submitted by Slavisha Milisavljevic (slavisha) on 2023-09-15T12:18:51Z No. of bitstreams: 1 disertacijaJovanRadosavljevic.pdf: 746060 bytes, checksum: 773cfbbd4d9be16224fed41529aca356 (MD5) en
dc.description.provenance Made available in DSpace on 2023-09-15T12:18:51Z (GMT). No. of bitstreams: 1 disertacijaJovanRadosavljevic.pdf: 746060 bytes, checksum: 773cfbbd4d9be16224fed41529aca356 (MD5) Previous issue date: 2023-08-10 en
dc.language.iso sr en_US
dc.publisher Beograd en_US
dc.title KRITIČNI GRAFOVI DIJAMETRA 2 en_US
mf.author.birth-date 1992-01-19
mf.author.birth-place Jagodina 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 Srbin en_US
mf.subject.area Computer science en_US
mf.subject.keywords graphs, diameter 2 critical graphs, primitive graphs en_US
mf.subject.subarea Graphtheory en_US
mf.contributor.committee Marić, Filip
mf.contributor.committee Stanić, Zoran
mf.contributor.committee Koledin, Tamara
mf.university.faculty Mathematical Faculty en_US
mf.document.references 16 en_US
mf.document.pages 61 en_US
mf.document.location Belgrade en_US
mf.document.genealogy-project Yes en_US
mf.university Belgrade en_US

Files in this item

Files Size Format View
disertacijaJovanRadosavljevic.pdf 746.0Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record