Growth in graphs

2013-10-28
10:00-11:00
FAMNIT-SEMIN
Primož Lukšič (UP IAM and Abelium).
Growth in graphs

The concepts of adjacency and distance are two of the most basic terms in graph theory. A natural generalization leads to the notion of distance degree which tells us the number of vertices at some distance from the chosen vertex, thereby defining the term of growth in a graph.When studying growth we often limit ourselves to the so called distance degree regular graphs, where all the distance degrees for all the vertices are the same, and self-median graphs, where the sum of distances from a chosen vertex to all the other vertices is independent of the selected vertex. It was shown that the former graphs correspond to strongly distance-balanced graphs while the latter correspond to distance-balanced graphs.The talk will focus on the properties and known families of the mentioned types of graphs, the complexity of obtaining them and their use in practical applications. It will present an overview of the known results and pose some still unanswered questions.