Speaker: Lorenzo Ciardo
Title: Where is 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 seminar 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 of a unique cycle) or quasi-simple (i.e., inducing a connected subgraph of G). In the last part of the seminar these properties are connected to the notion of discrete concavity of functions on graphs.