Diameter 2 critical graphs

[Ј. М. Радосављевић ]

стр. 58-59

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

Граф 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.

A graph G = (V, E) is an ordered pair of the set of vertices (V ) and the set of edges (E). The order of the graph G is the number of vertices |V |, and its size is the number of edges |E|. The vertices u, v ∈ V are adjacent if there is an edge uv ∈ E between them. The distance dist(u, v) between vertices u and v is the length of the shortest path from u to v. Diameter of a graph G is the largest distance dist(u, v) between some two vertices u, v. In the dissertation, graphs of diameter 2 are considered. Intuitively, the idea arises that graphs of diameter 2 have simple structures; however, it is known that asymptotically almost all graphs are of diameter 2. That is the reason why the narrower class — the class of critical graphs of diameter 2 (D2C) is interesting, i.e. graphs such that the removal of any edge increases the graph diameter. Furthermore, a narrower class of primitive D2C (PD2C) graphs is considered, i.e. D2C graphs which have no two vertices with the same set of neighbors. In the introductory chapter 2, the basic terms, algorithms and assertions are presented which are used in the dissertation. The following chapters present the original results regarding 2 diameter graphs. Chapter 3 describes the procedure to obtain the lists of D2C of order up to 13. Using simple parallelization obtaining the list of D2C graphs of order up to 13 took a month. This was a step forward, because before there was a list of all graphs of diameter 2 of order up to 10. The obtained results were used to test several known hypotheses on graphs of diameter 2. In chapter 4 it is shown that for each m ⩾ 3 a D2C graph containing a clique of size m must have at least 2m nodes. Furthermore, up to an isomorphism, there exists 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 at most 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 lower bound (2n−5) on the size of graphs of diameter 2 not containing a vertex adjacent to all other vertices. PD2C graphs of size 2n − 4 of order up to 13 are classified into three groups: • The first group is a subset of the family Z, defined in the dissertation, which for 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 at most 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 only Hamiltonian PD2C graphs of size 2n − 4. • The third group consists of a unique graph which does not belong to either of the first two groups. Based on these results, a conjecture is formulated that all PD2C graphs of order n ⩾ 10 and size 2n − 4 belong to the family Z.

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

graphs, diameter 2 critical graphs, primitive graphs

519.17(043.3)

Tekst