4 papers · 1 filter
Eigenvalues and homology of flag complexes and vector representations of graphs
R. Aharoni, E. Berger, R. Meshulam
Let X(G) denote the flag complex of a graph G=(V,E) on n vertices. We study relations between the first eigenvalues of successive higher Laplacians of X(G). One consequence is the…
A tree version of Konig's theorem
Ron Aharoni, Eli Berger, Ran Ziv
Konig's theorem states that the covering number and the matching number of a bipartite graph are equal. We prove a generalisation of this result, in which each point in one side of…
The number of edges in critical strongly connected graphs
Ron Aharoni, Eli Berger
We prove that the maximal number of directed edges in a vertex-critical strongly connected simple digraph on n vertices is n(n-1)/2 - n +4.
Dynamic monopolies of constant size
Eli Berger
The paper deals with a polling game on a graph. Initially, each vertex is colored white or black. At each round, each vertex is colored by the color shared by the majority of verti…