Growth in graphs

Iz MaFiRaWiki

Growth in graphs

Primož Lukšič

Univerza v Ljubljani, IMFM

We will present the results from our Ph.D. thesis, which explores the concept of growth in graphs and some similar concepts, such as the distance of a vertex or a graph, distance-balanced graphs, distance-residual subgraphs and the distance distribution of a graph.

Growth is a natural generalization of two basic notions in graph theory, distance and adjacency, although it formally originates from group theory. We will therefore start with the notion of growth in groups, followed by the definition of different forms of growth in graphs and their rate of growth. Then, we will present an algorithm for calculating the growth in infinite graphs, which will be used to calculate the growth of semiregular tessellations of the Euclidean plane.

In the second part, we will focus on growth in finite graphs, especially on distance degree regular (DDR) graphs, analyzing their properties, symmetries and their product graphs. We will do the same for distance-balanced (DB) graphs, where we will also prove the NP-completeness of the distance-balanced addition problem and the existence of some infinite families of DB-graphs that are not DDR-graphs.

Glej tudi/See also

Seminar za diskretno matematiko

Osebna orodja