Vertex splitting and the recognition of trapezoid graphs

Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between permutation graphs (where the trapezoids are lines) and cocomparability graphs (the complement has a transitive orientation). The operation of “vertex splitting”, introduced in (Cheah and Corneil, 1996) [3], first augments a given graph G and then transforms the augmented graph by replacing each of the original graph’s vertices by a pair of new vertices. This “splitted graph” is a permutation graph with special properties if and only if G is a trapezoid graph. Recently vertex splitting has been used to show that the recognition problems for both tolerance and bounded tolerance graphs is NP-complete (Mertzios et al., 2010) [11]. Unfortunately, the vertex splitting trapezoid graph recognition algorithm presented in (Cheah and Corneil, 1996) [3] is not correct. In this paper, we present a new way of augmenting the given graph and using vertex splitting such that the resulting algorithm is simpler and faster than the one reported in (Cheah and Corneil, 1996) [3].     

On total domination vertex critical graphs of high connectivity

A graph is called γ-critical if the removal of any vertex from the graph decreases the domination number, while a graph with no isolated vertex is γ_t-critical if the removal of any vertex that is not adjacent to a vertex of degree 1 decreases the total domination number. A γ_t-critical graph that has total domination number k, is called k-γ_t-critical. In this paper, we introduce a class of k-γ_t-critical graphs of high connectivity for each integer k≥3. In particular, we provide a partial answer to the question “Which graphs are γ-critical and γ_t-critical or one but not the other?” posed in a recent work [W. Goddard, T.W. Haynes, M.A. Henning, L.C. van der Merwe, The diameter of total domination vertex critical graphs, Discrete Math. 286 (2004) 255-261].     

Models and heuristic algorithms for a weighted vertex coloring problem

We consider a weighted version of the well-known Vertex Coloring Problem (VCP) in which each vertex i of a graph G has associated a positive weight w _i . Like in VCP, one is required to assign a color to each vertex in such a way that colors on adjacent vertices are different, and the objective is to minimize the sum of the costs of the colors used. While in VCP the cost of each color is equal to one, in the Weighted Vertex Coloring Problem (WVCP) the cost of each color depends on the weights of the vertices assigned to that color, and it equals the maximum of these weights. WVCP is known to be NP-hard and arises in practical scheduling applications, where it is also known as Scheduling on a Batch Machine with Job Compatibilities. We propose three alternative Integer Linear Programming (ILP) formulations for WVCP: one is used to derive, dropping integrality requirement for the variables, a tight lower bound on the solution value, while a second one is used to derive a 2-phase heuristic algorithm, also embedding fast refinement procedures aimed at improving the quality of the solutions found. Computational results on a large set of instances from the literature are reported.     

Vertex Poisson Algebras Associated with Courant Algebroids

We study relationships between vertex Poisson algebras and Courant algebroids. For any ?-graded vertex Poisson algebra A = ? _n∈? A _(n), we show that A ₍₁₎ is a Courant A ₍₀₎-algebroid. On the other hand, for any Courant 𝒜-algebroid ?, we construct an ?-graded vertex Poisson algebra A = ? _n∈? A _(n) such that A ₍₀₎ is 𝒜 and the Courant 𝒜-algebroid A ₍₁₎ is isomorphic to ? as a Courant 𝒜-algebroid.     

Axiomatic Aspects of N = 2 Vertex Superalgebras with Odd Formal Variables

We formulate the notion of “N = 2 vertex superalgebra with two odd formal variables” using a Jacobi identity with odd formal variables in which an N = 2 superconformal shift is incorporated into the usual Jacobi identity for a vertex superalgebra. It is shown that as a consequence of these axioms, the N = 2 vertex superalgebra is naturally a representation of the Lie superalgebra isomorphic to the three-dimensional algebra of superderivations with basis consisting of the usual conformal operator and the two N = 2 superconformal operators. In addition, this superconformal shift in the Jacobi identity dictates the form of the odd formal variable components of the vertex operators, and allows one to easily derive the useful formulas in the theory. The notion of N = 2 Neveu–Schwarz vertex operator superalgebra with two odd formal variables is introduced, and consequences of this notion are derived. In particular, we develop the duality properties which are necessary for a rigorous treatment of the correspondence with the underlying supergeometry. Various other formulations of the notion of N = 2 (Neveu–Schwarz) vertex (operator) superalgebra appearing in the mathematics and physics literature are discussed, and several mistakes in the literature are noted and corrected.     

Study of a lacunary solid phase II—Morphological and kinetic characteristics of its formation

The morphological changes which take place during the formation of the lacunary phase αH₂C₂O₄·BaC₂O₄ by isothermal dehydration of the oxalate H₂C₂O₄·BaC₂O₄·2H₂O, are characteristic for dihydrations of hydrates which, with water vapor, form a divariant system.They show that the transformation affects the entire bulk of the solid from the very first moments of the reaction. The dihydrate crystal undergo a very regular fragmentation and the pseudomorph appears as a stacking of microcrystals whose shape and dimensions are unique and independent of the size and habit of the initial crystals.The kinetic characteristics of the reaction show that the microcrystal dimensions do not depend on dehydration rate, they enable the precise role of crystalline faces in gas evacuation to be evaluated.The origin of fragmentation, the microcrystal habit produced, the anisotropy of transformation of the crystalline faces and the process of water elimination are explained by means of structural considerations.     

AB initio SCF LCAO MO study of the HOH…Cl− hydrogen bond

Ab initio SCF LCAO MO calculations for the [H₂O…Cl]^? complex have been performed. The energy of the linear hydrogen bond has been found to be lower than the energy of the bifurcated one. The difference of the energies is about 3 kcal/mole. The calculated equilibrium distance between the oxygen and chlorine atoms equals 5.75 au. The interaction energy of the chlorine anion and the rigid water molecule amounts to ?19 kcal/mole. The optimization of the OH bond length in the complex (linear hydrogen bond) leads to an interaction energy of ?19.5 kcal/mole (the experimental value equals ?13.1 kcal/mole). As a result of the hydrogen bond formation the OH bond length increases by 0.08 au.     

Coloring graphs by iterated local search traversing feasible and infeasible solutions

Graph coloring is one of the hardest combinatorial optimization problems for which a wide variety of algorithms has been proposed over the last 30 years. The problem is as follows: given a graph one has to assign a label to each vertex such that no monochromatic edge appears and the number of different labels used is minimized. In this paper we present a new heuristic for this problem which works with two different functionalities. One is defined by two greedy subroutines, the former being a greedy constructive one and the other a greedy modification one. The other functionality is a perturbation subroutine, which can produce also infeasible colorings, and the ability is then to retrieve feasible solutions. In our experimentation the proper tuning of this optimization scheme produced good results on known graph coloring benchmarks.     

Inequalities for vertex distances of two simplices

We establish in this paper some inequalities for vertex distances of two simplices, and give some applications thereof.