Naslov (srp)

Критични графови дијаметра 2 : докторска дисертација

Autor

Radosavljević, Jovan M., 1992-

Doprinosi

Koledin, Tamara, 1976-
Marić, Filip, 1978-
Živković, Miodrag, 1956-
Stanić, Zoran, 1975-

Opis (srp)

Граф G = (V, E) је уређени пар скупа чворова V и грана E. Редграфа G је број чворова |V |, а његова величина је број грана |E|. Чворовиu, v ∈ V су суседни ако између њих постоји грана uv ∈ E. Растојање dist(u, v)чворова u и v G је дужина најкраћег пута од u до v. Дијаметар графа G јенајвеће растојање dist(u, v) нека два чвора u, v. У дисертацији се разматрајуграфови дијаметра 2. Интуитивно се намеће представа да су графови дија-метра 2 једноставне структуре; међутим познато је да су асимптотски скоросви графови дијаметра 2. Због тога је интересантна ужа класа — класа D2Cкритичних графова дијаметра 2, тј. графова код којих уклањање било којегране води повећавању дијаметра. Поред тога, разматра се и ужа класа при-митивних D2C (PD2C) графова, тј. D2C графова који немају два чвора саистим скупом суседа.У уводном поглављу 2 изложени су основни појмови, алгоритми и твр-ђења која се користе у дисертацији. У наредним поглављима приказују сеоригинални резултати у вези са графовима дијаметра 2.У поглављу 3 описује поступак добијања листе D2C графова реда до 13.Са уграђеном паралелизацијом формирање списка D2C графова реда до 13трајало је месец дана. Овим је учињен искорак, јер је претходно постојао спи-сак свих графова дијаметра 2 реда до 10. Добијени резултати су искоришћениза проверу неколико познатих хипотеза о графовима дијаметра 2.У поглављу 4 показује се да за свако m ⩾ 3 D2C граф који садржи кли-ку величине m мора да има бар 2m чворова. При томе, са тачношћу до наизоморфизам, постоји тачно један граф величине 2m који садржи клику ве-личине m.У поглављу 5 разматрају се PD2C графови са најмањим бројем грана. Изсписка свих PD2C графови реда n ⩽ 13 су издвојени PD2C графови величиненајвише 2n − 4. Само три од издвојених графова су величине 2n − 5, што јеу складу са тврђењем Ердеш-Рењијеве теореме о доњој граници за величинуграфова дијаметра 2 који не садрже чвор суседан са свим осталим чворовима(та граница је 2n − 5). PD2C графови величине 2n − 4 реда до 13 разврстанису у три групе:• Прва група припада фамилијисвако n ⩾ 6 садржи тачно један PD2C граф реда n величине 2n − 4.• Другу групу чини седам Хамилтонових PD2C графова реда највише 9величине 2n − 4. У дисертацији је доказано да не постоји овакав Хамил-тонов граф реда већег од 11, тј. да су пронађених седам графова јединиХамилтонови PD2C графови величине 2n − 4.• Трећу групу чини јединствени граф који не припада ни једној од прведве групе.На основу ових резултата формулисана је хипотеза да сви PD2C графови ре-да n ⩾ 10 и величине 2n − 4 припадају фамилији Z.

Opis (srp)

Рачунарство и информатика -Теорија графова / Computer science - Graph theory Datum odbrane: 30.09.2023.

Opis (eng)

A graph G = (V, E) is an ordered pair of the set of vertices (V ) andthe set of edges (E). The order of the graph G is the number of vertices |V |, andits size is the number of edges |E|. The vertices u, v ∈ V are adjacent if there isan edge uv ∈ E between them. The distance dist(u, v) between vertices u and v isthe length of the shortest path from u to v. Diameter of a graph G is the largestdistance dist(u, v) between some two vertices u, v. In the dissertation, graphs ofdiameter 2 are considered. Intuitively, the idea arises that graphs of diameter 2have simple structures; however, it is known that asymptotically almost all graphsare of diameter 2. That is the reason why the narrower class — the class of criticalgraphs of diameter 2 (D2C) is interesting, i.e. graphs such that the removal ofany edge increases the graph diameter. Furthermore, a narrower class of primitiveD2C (PD2C) graphs is considered, i.e. D2C graphs which have no two verticeswith the same set of neighbors.In the introductory chapter 2, the basic terms, algorithms and assertions arepresented which are used in the dissertation. The following chapters present theoriginal results regarding 2 diameter graphs.Chapter 3 describes the procedure to obtain the lists of D2C of order up to13. Using simple parallelization obtaining the list of D2C graphs of order up to13 took a month. This was a step forward, because before there was a list of allgraphs of diameter 2 of order up to 10. The obtained results were used to testseveral known hypotheses on graphs of diameter 2.In chapter 4 it is shown that for each m ⩾ 3 a D2C graph containing a cliqueof size m must have at least 2m nodes. Furthermore, up to an isomorphism, thereexists a unique graph of size 2m that contains a clique of size m.In chapter 5 PD2C graphs with the smallest number of edges are considered.From the list of all PD2C graphs of order n ⩽ 13 firstly PD2C graphs of size atmost 2n − 4 are selected. Only three of the extracted graphs are of size 2n − 5,which is consistent with the statement of the Erdöş-Renyi theorem on the lowerbound (2n−5) on the size of graphs of diameter 2 not containing a vertex adjacentto all other vertices. PD2C graphs of size 2n − 4 of order up to 13 are classifiedinto three groups:• The first group is a subset of the family Z, defined in the dissertation, whichfor each n ⩾ 6 contains exactly one PD2C graph of order n and size 2n − 4.• The second group consists of seven Hamiltonian PD2C graphs of order atmost 9 and the size 2n − 4. It is proved that there is no such Hamilto-nian graph of order greater than 11, i.e. these seven graphs are the onlyHamiltonian PD2C graphs of size 2n − 4.• The third group consists of a unique graph which does not belong to eitherof the first two groups.Based on these results, a conjecture is formulated that all PD2C graphs of ordern ⩾ 10 and size 2n − 4 belong to the family Z.

Jezik

srpski

Datum

2023

Licenca

Ovo delo je licencirano pod uslovima licence
Creative Commons CC BY-NC 3.0 AT - Creative Commons Autorstvo - Nekomercijalno 3.0 Austria License.

http://creativecommons.org/licenses/by-nc/3.0/at/legalcode

Predmet

OSNO - Opšta sistematizacija naučnih oblasti, Kombinatorna analiza. Teorija grafova

графови, критични графови дијаметра 2, примитивни графо- ви

OSNO - Opšta sistematizacija naučnih oblasti, Kombinatorna analiza. Teorija grafova

graphs, diameter 2 critical graphs, primitive graphs