Efficient edge domination in regular graphs

An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs with efficient edge dominating sets are efficient edge dominating sets. A necessary condition for the existence of efficient edge dominating sets in terms of spectra of graphs is established. We also prove that, for arbitrary fixed p ≥ 3, deciding on the existence of efficient edge dominating sets on p-regular graphs is NP-complete. © 2008 Elsevier B.V. All rights reserved.

Maxwell perturbations on asymptotically Anti-de-Sitter spacetimes: generic boundary conditions and a new branch of quasinormal modes

Perturbations of asymptotically Anti-de-Sitter (AdS) spacetimes are often considered by imposing field vanishing boundary conditions (BCs) at the AdS boundary. Such BCs, of Dirichlet-type, imply a vanishing energy flux at the boundary, but the converse is, generically, not true. Regarding AdS as a gravitational box, we consider vanishing energy flux (VEF) BCs as a more fundamental physical requirement and we show that these BCs can lead to a new branch of modes. As a concrete example, we consider Maxwell perturbations on Kerr-AdS black holes in the Teukolsky formalism, but our formulation applies also for other spin fields. Imposing VEF BCs, we find a set of two Robin BCs, even for Schwarzschild-AdS black holes. The Robin BCs on the Teukolsky variables can be used to study quasinormal modes, superradiant instabilities and vector clouds. As a first application, we consider here the quasinormal modes of Schwarzschild-AdS black holes. We find that one of the Robin BCs yields the quasinormal spectrum reported in the literature, while the other one unveils a new branch for the quasinormal spectrum.