On a graph packing conjecture by Bollobás,Eldridge and Catlin

Two graphs G ₁ and G ₂ of order n pack if there exist injective mappings of their vertex sets into [n], such that the images of the edge sets are disjoint. In 1978, Bollobás and Eldridge, and independently Catlin, conjectured that if (Δ(G ₁) + 1)(Δ(G ₂) + 1) ≤ n + 1, then G ₁ and G ₂ pack. Towards this conjecture, we show that for Δ(G ₁),Δ(G ₂) ≥ 300, if (Δ(G ₁) + 1)(Δ(G ₂) + 1) ≤ 0.6n + 1, then G ₁ and G ₂ pack. This is also an improvement, for large maximum degrees, over the classical result by Sauer and Spencer that G ₁ and G ₂ pack if Δ(G ₁)Δ(G ₂) < 0.5n. This work was supported in part by NSF grant DMS-0400498. The work of the second author was also partly supported by NSF grant DMS-0650784 and grant 05-01-00816 of the Russian Foundation for Basic Research. The work of the third author was supported in part by NSF grant DMS-0652306.     

On k‐detour subgraphs of hypercubes

A spanning subgraph G of a graph H is a k‐detour subgraph of H if for each pair of vertices , the distance, , between x and y in G exceeds that in H by at most k. Such subgraphs sometimes also are called additive spanners. In this article, we study k‐detour subgraphs of the n‐dimensional cube, , with few edges or with moderate maximum degree. Let denote the minimum possible maximum degree of a k‐detour subgraph of . The main result is that for every and On the other hand, for each fixed even and large n, there exists a k‐detour subgraph of with average degree at most . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 55–64, 2008     

2,6-Diacylnaphthalene-1,8:4,5-bis(dicarboximides): synthesis, reduction potentials, and core extension

2,6-Diacyl derivatives of naphthalene-1,8:4,5-bis(dicarboximide)s have been synthesized via Stille coupling reactions of the corresponding 2,6-distannyl derivative with acyl halides. Reaction of these diketones with hydrazine gave phthalazino[6,7,8,1-lmna]pyridazino[5,4,3-gh][3,8]phenanthroline-5,11(4H,10H)-dione fused-ring derivatives. The products were characterized by UV-vis absorption spectroscopy and electrochemistry, modeled using density functional theory calculations, and, in some cases, studied and compared using single-crystal X-ray diffraction.     

On the approximability of the Simplified Partial Digest Problem

In this paper, we analyse the computational complexity of an optimization version of the Simplified Partial Digest Problem (SPDP), which is a mathematical model for DNA mapping based on the results of a simplified partial digest experiment. We prove that recognizing 46.16% of the elements of the DNA map in the error-free simplified partial digest experiment is NP-hard in the strong sense. This implies that the problem of maximizing the number of correct elements of the DNA map in the error-free simplified partial digest experiment is pseudopolynomially non-approximable with the approximation ratio .     

On topological diversity of rectilinear representations of countably infinite graphs

We prove that, for each simple graph G whose set of vertices is countably infinite, there is a family ${\varvec{\mathcal{R}}(\varvec{G})}$ of the cardinality of the continuum of graphs such that (1) each graph ${\varvec{H} \in \varvec{\mathcal{R}}(\varvec{G})}$ is isomorphic to G, all vertices of H are points of the Euclidean space E ³, all edges of H are straight line segments (the ends of each edge are the vertices joined by it), the intersection of any two edges of H is either their common vertex or empty, and any isolated vertex of H does not belong to any edge of H; (2) all sets ${\varvec{\mathcal{B}}(\varvec{H})}$ ( ${\varvec{H} \in \varvec{\mathcal{R}}(\varvec{G})}$ ), where ${\varvec{\mathcal{B}}(\varvec{H})\subset \mathbf{E}^3}$ is the union of all vertices and all edges of H, are pairwise not homeomorphic; moreover, for any graphs ${\varvec{H}_1 \in \varvec{\mathcal{R}}(\varvec{G})}$ and ${\varvec{H}_2 \in \varvec{\mathcal{R}}(\varvec{G})}$ , ${\varvec{H}_1 \ne \varvec{H}_2}$ , and for any finite subsets ${\varvec{S}_i \subset \varvec{\mathcal{B}}(\varvec{H}_i)}$ (i = 1, 2), the sets ${\varvec{\mathcal{B}}(\varvec{H}_1){\setminus} \varvec{S}_1}$ and ${\varvec{\mathcal{B}}(\varvec{H}_2){\setminus} \varvec{S}_2}$ are not homeomorphic.     

ChemInform Abstract: Single-Crystal and Powder Neutron Diffraction Study of the FexMn1-xS Solid Solutions.

Single crystals of the α-MnS-based Fe_xMn_1-xS (x = 0-0.3) solid solutions are prepared and shown to be new Mott materials with the rock salt structure.     

Phosphorylation of 2‐(3‐methyl‐1,3‐diazabuten‐1‐yl)‐3‐ethoxycarbonylthiophenes with phosphorus(III) halides

2‐(3‐Methyl‐1,3‐diazabuten‐1‐yl)‐3‐ethoxycarbonylthiophenes are phosphorylated with phosphorus(III) halides in basic media at position 5 of the thiophene ring. Up to three heteroaromatic substituents can be introduced one by one at the same phosphorus atom. On this basis, mono‐, bis‐, and trishetaryl substituted P(III) and P(V) derivatives have been obtained. Phosphorylated 2‐(N,N‐dimethylformamidino)‐3‐ethoxycarbonylthiophenes provide a synthetic access to phosphorylated thienopyrimidines. © 2001 John Wiley & Sons, Inc. Heteroatom Chem 12:641–651, 2001     

Heterocondensed 1,2,3‐diazaphosphorines

The reaction of phosphorus tribromide with phenylhydrazones of heterocyclic aldehydes leads to formation of a new phosphorus‐containing heterocyclic system—heterocondensed 1,2,3‐diazaphosphorines. Properties of the phosphorus‐containing heterocyclic compounds that have been synthesized are described. © 2001 John Wiley & Sons, Inc. Heteroatom Chem 12:658–664, 2001     

A DFT quantum‐chemical study on the structures and active sites of polymethylaluminoxane

The electronic structure and geometry of polymethylaluminoxane (MAO) [—Al(CH₃)O—]_n with different size (n = 4–12) have been studied using quantum‐chemical DFT (density functional theory) calculations. It has been found: 1) Starting from n = 6, the three‐dimensional oxo‐bridged (cage) structure of MAO is more stable than the cyclic structure. 2) Both for cage structure and for cyclic structure the Lewis acidity of Al atoms characterized by their net positive charge amplifies with increasing size of MAO (n). 3) Trimethylaluminium (AlMe₃) reacts with the cage structure of MAO with cleavage of an Al‐O dative bond and formation of acidic tri‐coordinated Al^v and basic di‐coordinated O^v atoms in the MAO molecule. Two molecules AlMe₃ are associated with acidic Al^v and basic O^v centers. As the MAO increases in size, the acidity of Al^v centers amplifies and the distance Al^v‐(AlMe₃) shortens; on the contrary, interaction of AlMe₃ with O^v centers weakens and the distance O^v‐(AlMe₃) increases with increasing n value. The total heat of Al₂Me₆ interaction with MAO (sum interaction of Al^v‐(AlMe₃) and O^v‐(AlMe₃)) noticeably decreases as the size of MAO increases (from 50.9 kcal/mol for n = 4 to 20.2 kcal/mol for n = 12). It is proposed that acidic Al^v and basic O^v centers formed in the cage structure of MAO interact with zirconocene yielding ‘cation‐like’ zirconium active centers.