The Degree Preserving Spanning Tree Problem: Valid Inequalities and Branch-and-cut method

Given a connected undirected graph G, the Degree Preserving Spanning Tree Problem (DPSTP) consists in finding a spanning tree T of G that maximizes the number of vertices that have the same degree in T and in G. In this paper, we introduce Integer Programming formulations, valid inequalities and a Branch-and-cut algorithm for the DPSTP. Reinforced with new valid inequalities, the upper bounds provided by the formulation behind our Branch-and-cut method dominate previous DPSTP bounds in the literature.     

SINGLE AND DOUBLE EDGE INTERFACE CRACK SOLUTIONS FOR ARBITRARY FORMS OF MATERIAL COMBINATION

In this paper interfacial edge crack problems are considered by the application of the finite element method. The stress intensity factors are accurately determined from the ratio of crack-tip-stress value between the target given unknown and reference problems. The reference problem is chosen to produce the singular stress fields proportional to those of the given unknown problem. Here the original proportional method is improved through utilizing very refined meshes and post-processing technique of linear extrapolation. The results for a double-edge interface crack in a bonded strip are newly obtained and compared with those of a single-edge interface crack for different forms of combination of material. It is found that the stress intensity factors should be compared in the three different zones of relative crack lengths. Different from the case of a cracked homogeneous strip, the results for the double edge interface cracks are found to possibly be bigger than those for a single edge interface crack under the same relative crack length.     

A hybrid level set method for modelling detonation and combustion problems in complex geometries

We present an accurate and fast wave tracking method that uses parametric representations of tracked fronts, combined with modifications of level set methods that use narrow bands. Our strategy generates accurate computations of the front curvature and other geometric properties of the front. We introduce data structures that can store discrete representations of the location of the moving fronts and boundaries, as well as the corresponding level set fields, that are designed to reduce computational overhead and memory storage. We present an algorithm we call stack sweeping to efficiently sort and store data that is used to represent orientable fronts. Our implementation features two reciprocal procedures, a forward ‘front parameterization’ that constructs a parameterization of a front given a level set field and a backward ‘field construction’ that constructs an approximation of the signed normal distance to the front, given a parameterized representation of the front. These reciprocal procedures are used to achieve and maintain high spatial accuracy. Close to the front, precise computation of the normal distance is carried out by requiring that displacement vectors from grid points to the front be along a normal direction. For front curves in two dimensions, a cubic interpolation scheme is used, and G ¹ surface parameterization based on triangular patches is used for the three-dimensional implementation to compute the distances from grid points near the front. To demonstrate this new, high accuracy method we present validations and show examples of combustion-like applications that include detonation shock dynamics, material interface motions in a compressible multi-material simulation and the Stephan problem associated with dendrite solidification.     

半定矩阵秩极小的非凸精确松弛

本文主要研究半定矩阵秩极小问题(P)的非凸精确松弛及其性质.首先,为求解问题(P),我们引入其Schatten p-范数(0＜p＜1)松弛,记为(Sp).其次,通过定义半定限制等距常数和半定限制正交常数,我们给出了问题(P)有唯—解的充分条件.最后,利用半定限制等距性质,我们给出了问题(P)和(Sp)有相同唯一解的充分条件.特别地,对任意0＜p＜1,我们还得到—个一致的精确恢复条件.     

Synthesis of Piperidine Nucleosides as Conformationally Restricted Immucillin Mimics

The de novo synthesis of piperidine nucleosides from our homologating agent 5,6-dihydro-1,4-dithiin is herein reported. The structure and conformation of nucleosides were conceived to faithfully resemble the well-known nucleoside drugs Immucillins H and A in their bioactive conformation. NMR analysis of the synthesized compounds confirmed that they adopt an iminosugar conformation bearing the nucleobases and the hydroxyl groups in the appropriate orientation.     

List star edge coloring of k-degenerate graphs

A star edge coloring of a graph is a proper edge coloring such that every connected 2-colored subgraph is a path with at most 3 edges. Deng et al. and Bezegová et al. independently show that the star chromatic index of a tree with maximum degree $\Delta$ is at most $?\frac{3\Delta }{2}?$, which is tight. In this paper, we study the list star edge coloring of $k$-degenerate graphs. Let $c{h}_{st}^{\prime }\left(G\right)$ be the list star chromatic index of $G$: the minimum $s$ such that for every $s$-list assignment $L$ for the edges, $G$ has a star edge coloring from $L$. By introducing a stronger coloring, we show with a very concise proof that the upper bound on the star chromatic index of trees also holds for list star chromatic index of trees, i.e. $c{h}_{st}^{\prime }\left(T\right)\le ?\frac{3\Delta }{2}?$ for any tree $T$ with maximum degree $\Delta$. And then by applying some orientation technique we present two upper bounds for list star chromatic index of $k$-degenerate graphs.     

A Simple Synthesis of Stable Phosphorus Ylides from Indole and Some of Its Derivatives

Stable crystalline phosphorus ylides were obtained in excellent yields from the 1:1:1 addition reaction between triphenylphosphine and dialkyl acetylenedicarboxylates in the presence of strong NH acids, such as indole and 2-methyl indole, 3-methyl indole, and 5-boromo indole. These stable ylides exist in a solution as a mixture of two geometrical isomers as a result of the restricted rotation around the carbon–carbon partial double bond resulting from the conjugation of the ylide moiety with the adjacent carbonyl group.     

Erratum: The average degree of an edge-chromatic critical graph II

In the article “The average degree of an edge-chromatic critical graph II” by Douglas R. Woodall (J. Graph Theory 56 (2007), 194-218), it was claimed that the average degree of an edge-chromatic critical graph with maximum degree $\mathrm{\Delta }$ is at least $\text{◂⋅▸}\frac{2}{3}\left(\mathrm{\Delta }+1\right)$ if $\mathrm{\Delta }⩾2$, at least $\text{◂+▸}\frac{2}{3}\mathrm{\Delta }+1$ if $\mathrm{\Delta }⩾8$, and at least $\text{◂⋅▸}\frac{2}{3}\left(\mathrm{\Delta }+2\right)$ if $\mathrm{\Delta }⩾15$. Unfortunately there were mistakes in the proof of the last two of these results, which are now proved only if $\mathrm{\Delta }⩾18$ and $\mathrm{\Delta }⩾30$, respectively.     

Uniform random colored complexes

We present here random distributions on (D + 1)‐edge‐colored, bipartite graphs with a fixed number of vertices 2p. These graphs encode D‐dimensional orientable colored complexes. We investigate the behavior of those graphs as p→∞. The techniques involved in this study also yield a Central Limit Theorem for the genus of a uniform map of order p, as p→∞.     

Powers of edge ideals with linear resolutions

We show that if G is a gap-free and diamond-free graph, then I(G)^s has a linear minimal free resolution for every s≥2.