05C50 Online Seminar: Sirshendu Pan

Let A ∈ M_n be nonnegative, irreducible and E_ii = e_ie_i^T, where e_i is the ith standard basis vector. For a fixed t_0 > 0, an index p ∈ [n] := {1, 2, \ldots, n} is called a winner for the value t_0 if the spectral radius satisfies

\rho( A + t_0 E_pp ) = \max_{ i ∈ [n] } \rho( A + t_0 E_ii ).

If p remains a winner for each t>0, then it is called a universal winner. The concepts were introduced in 1996 and studied only in a few articles till now. When G is a simple connected graph (or a strongly connected digraph), the nonnegative weighted adjacency matrix A(G) being irreducible, one can talk of a universal winner vertex with respect to A(G). The universal winners seem to capture the graph structures well. It is known that the only strongly connected digraph G in which all vertices are universal winners with respect to all nonnegative weighted A(G), is the directed cycle, thereby characterizing it. Let S\subset [n] be nonempty. We characterize the class of strongly connected digraphs G with vertex set [n] for which only the vertices in S are the universal winners with respect to all nonnegative weighted A(G). Interestingly, in the case of undirected graphs, it turns out that the stars are the only such graphs. Looking at this result, one is naturally be curious about whether the structures will be different if we consider only the 0-1 adjacency matrices of connected undirected graphs? As expected, even for a tree, it is not in general true that there is always a universal winner. In fact, every tree is a subtree of a tree that has a unique universal winner, and also of one without a universal winner.  Trees with exactly k > 1 universal winners are not easy to find. A construction of a class of trees with exactly k universal winners is provided. Interestingly, it turns out that for any undirected connected graph G, the set of winners of G and the corona G \circ K_1 are the same, where the later is obtained by adding a new pendent vertex to each vertex of G. This talk is based on joint work with Steve Kirkland and Sukanta Pati.