|
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 |