The Caesarea Rothschild Institute at the University of Haifa invites you to attend its

CRI-Haifa Special Summer Graph Theory Event

Double Seminar

           Date:     Wednesday July 29th

           Place:     665 Education Building, University of Haifa


       11:00 Coffee and welcome

       11:15 Alain Hertz (Ecole Polytechnique, Montreal, Canada)

                 "Dominating induced matchings in graphs containing no long claw"

       12:15 Farewell Toast to Felix

                 "How to consume pizza, vegetables, wine and cake"

      13:00 Felix Goldberg

                 "Signed spectral moments of graphs"



               Dominating induced matchings in graphs containing no long claw

Alain Hertz

An induced matching M in a graph G is dominating if every edge not in M shares exactly one vertex with an edge in M. The dominating induced matching problem (also known as efficient edge domination) asks whether a graph G contains a dominating induced matching. This problem is generally NP-complete, but polynomial-time solvable for graphs with some special properties. In particular, it is solvable in polynomial time for claw-free graphs.

We study this problem for graphs containing no long claw, i.e. no induced subgraph obtained from the claw by subdividing each of its edges exactly once. To solve the problem in this class, we reduce it to the following

question: given a graph G and a subset of its vertices, does G contain a matching saturating all vertices of the subset? We show that this question can be answered in polynomial time, thus providing a polynomial-time algorithm to solve the dominating induced matching problem for graphs containing no long claw.

 Joint work with V. Lozin, B. Ries, V. Zamaraev, D. de Werra


 Signed spectral moments of graphs

Felix Goldberg

A well known upper bound for the spectral radius of a graph, due to Hong,

is that   {\mu_1}^2   ≤2m−n+1.

It is conjectured that for connected graphs n−1≤s+≤2m−n+1, where s+ denotes the sum of the squares of the positive eigenvalues. The conjecture is proved for various classes of graphs, including bipartite, complete q-partite,hyper-energetic, strongly regular and barbell graphs. Various searches have found no counter-examples. The paper


concludes with a brief discussion of the apparent difficulties of proving the conjecture in general.

Joint work with Clive Elphick, Miriam Farber, and Pawel Wocjan