Radiation from a D-dimensional collision of shock waves: two-dimensional reduction and Carter–Penrose diagram

We analyze the causal structure of the two-dimensional (2D) reduced background used in the perturbative treatment of a head-on collision of two D-dimensional Aichelburg–Sexl gravitational shock waves. After defining all causal boundaries, namely the future light-cone of the collision and the past light-cone of a future observer, we obtain characteristic coordinates using two independent methods. The first is a geometrical construction of the null rays which define the various light cones, using a parametric representation. The second is a transformation of the 2D reduced wave operator for the problem into a hyperbolic form. The characteristic coordinates are then compactified allowing us to represent all causal light rays in a conformal Carter–Penrose diagram. Our construction holds to all orders in perturbation theory. In particular, we can easily identify the singularities of the source functions and of the Green’s functions appearing in the perturbative expansion, at each order, which is crucial for a successful numerical evaluation of any higher order corrections using this method.

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.

A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph

A family of quadratic programming problems whose optimal values are upper bounds on the independence number of a graph is introduced. Among this family, the quadratic programming problem which gives the best upper bound is identified. Also the proof that the upper bound introduced by Hoffman and Lovász for regular graphs is a particular case of this family is given. In addition, some new results characterizing the class of graphs for which the independence number attains the optimal value of the above best upper bound are given. Finally a polynomial-time algorithm for approximating the size of the maximum independent set of an arbitrary graph is described and the computational experiments carried out on 36 DIMACS clique benchmark instances are reported.

A recursive construction of the regular exceptional graphs with least eigenvalue -2

In spectral graph theory a graph with least eigenvalue 2 is exceptional if it is connected, has least eigenvalue greater than or equal to 2, and it is not a generalized line graph. A ðk; tÞ-regular set S of a graph is a vertex subset, inducing a k-regular subgraph such that every vertex not in S has t neighbors in S. We present a recursive construction of all regular exceptional graphs as successive extensions by regular sets.