Reconfiguration for Dominating Sets Given a problem and a set of feasible solutions to that problem, the associated  reconfiguration problem involves determining whether one feasible solution to the original problem can be transformed to a different feasible solution through a sequence of allowable moves, with the condition that the intermediate stages are also feasible solutions.  Any reconfiguration problem can be modelled with a  reconfiguration graph, where the vertices represent feasible solutions and two vertices are adjacent if and only if…

In this talk, I will show regions that contain no complex zeros the edge-cover polynomials of hypergraphs. The edge cover polynomial of a graph $G$ is the generating function of edges that covers $V(G)$. It is known that the zeros of this polynomial have length at most $\frac{(2+\sqrt{3})^2}{1+\sqrt{3}}$, that we strengthen by showing that it is at most $4$.  We use the general subgraph counting polynomial of Wagner to establish this result along with its generalization for the edge cover…

About a year ago Jason Brown spoke in our seminar (of the university of Amsterdam) about the two-terminal reliability polynomial and left us with some questions about the closure of the complex zeros of all such polynomials (the zero-locus). In this talk I will define a way to capture, for a certain parameter, whether the set of all two-terminal reliability polynomials behaves chaotically around this parameter or not, i.e. whether this parameter is active or passive. I call the set…

We study the algebraic connectivity for several classes of random semi-regular graphs. For large random semi-regular bipartite graphs, we explicitly compute both their algebraic connectivity and as well as the full spectrum distribution. For an integer d in , we find families of random semi-regular graphs that have higher algebraic connectivity than a random d-regular graphs with the same number of vertices and edges. On the other hand, we show that regular graphs beat semi-regular graphs when d >8. More…

Extremal questions for vertex colorings of graphs For graphs $G$ and $H$, an $H$-coloring of $G$ is a map from the vertices of $G$ to the vertices of $H$ so that an edge in $G$ is mapped to an edge in $H$.  The graph $H$ can be thought of as the allowable coloring scheme: its vertices are the colors used and its edges indicating colors that can appear on the endpoints of an edge in $G$. When the graph $H$…

Graph polynomials In this talk, I will discuss various aspects of several graph polynomials such as the location of their roots, their combinatorial properties and extremal questions. Join Zoom Meeting: link

An Unsupervised Framework for Comparing Graph Embeddings The goal of many machine learning applications is to make predictions or discover new patterns using graph-structured data as feature information. In order to extract useful structural information from graphs, one might want to try to embed it in a geometric space by assigning coordinates to each node such that nearby nodes are more likely to share an edge than those far from each other. There are many embedding algorithms (based on techniques…