Lorenzo Ciardo: How to find the center of a graph?

Speaker: Lorenzo Ciardo (UiO)

Title: How to find the center of a graph?

Abstract: Many complex phenomena in fields such as social science, biology, telecommunication or physics are described in terms of interactions among a large number of discrete, atomic individuals, and can hence be modeled in a natural way by using graphs. A basic step to gain insight into the structure of these large graphs is to identify a small set of nodes which are best suited to control all the others: a center. Fiedler theory provides a meaningful - but computationally expensive - notion of center for acyclic graphs, obtained by comparing spectral radii of particular matrices. In this talk the Fiedler center is used as a model to build a new, computationally efficient center concept for a general graph G, defined as the set of cycles in a directed graph associated with G. It is then investigated when this center is simple (i.e., consisting in a unique cycle) or quasi-simple (i.e., inducing a connected subgraph of G). In the last part of the talk these properties are related to the notion of discrete concavity of functions on graphs.

Published Mar. 6, 2019 2:17 PM - Last modified Apr. 4, 2019 1:10 PM