Sufficient Conditions for a Digraph to be Supereulerian

A (di)graph is supereulerian if it contains a spanning eulerian sub(di)graph. This property is a relaxation of hamiltonicity. Inspired by this analogy with hamiltonian cycles and by similar results in supereulerian graph theory, we analyze a number of sufficient Ore type conditions for a digraph to be supereulerian. Furthermore, we study the following conjecture due to Thomassé and the first author: if the arc‐connectivity of a digraph is not smaller than its independence number, then the digraph is supereulerian. As a support for this conjecture we prove it for digraphs that are semicomplete multipartite or quasitransitive and verify the analogous statement for undirected graphs.     

模糊线性回归模型的约束最小二乘估计

自Tanaka等1982年提出模糊回归概念以来,该问题已得到广泛的研究。作为主要估计方法之一的模糊最小二乘估计以其与统计最小二乘估计的密切联系更受到人们的重视。本文依据适当定义的两个模糊数之间的距离,提出了模糊线性回归模型的一个约束最小二乘估计方法,该方法不仅能使估计的模糊参数的宽度具有非负性而且估计的模糊参数的中心线与传统的最小二乘估计相一致。最后,通过数值例子说明了所提方法的具体应用。     

Sparse graph certificates for mixed connectivity

We give a short proof for the Mixed Connectivity Certificate Theorem of Even, Itkis and Rajsbaum and provide an upper bound on the edge number of a certificate of local T-mixed connectivity up to k.     

On the degree of convergence of lemniscates in finite connected domains

For an arbitrary bounded closed set E in the complex plane with complement Ω of finite connectivity, we study the degree of convergence of the lemniscates in Ω.     

Molecular dynamics and information on possible sites of interaction of intramyocellular metabolites in vivo from resolved dipolar couplings in localized H NMR spectra

Proton NMR resonances of the endogenous metabolites creatine and phosphocreatine ((P)Cr), taurine (Tau), and carnosine (Cs, β-alanyl-l-histidine) were studied with regard to residual dipolar couplings and molecular mobility. We present an analysis of the direct ¹H–¹H interaction that provides information on motional reorientation of subgroups in these molecules in vivo. For this purpose, localized ¹H NMR experiments were performed on m. gastrocnemius of healthy volunteers using a 1.5-T clinical whole-body MR scanner. We evaluated the observable dipolar coupling strength SD₀ (S = order parameter) of the (P)Cr-methyl triplet and the Tau-methylene doublet by means of the apparent line splitting. These were compared to the dipolar coupling strength of the (P)Cr-methylene doublet. In contrast to the aliphatic protons of (P)Cr and Tau, the aromatic H2 (δ = 8 ppm) and H4 (δ = 7 ppm) protons of the imidazole ring of Cs exhibit second-order spectra at 1.5 T. This effect is the consequence of incomplete transition from Zeeman to Paschen-Back regime and allows a determination of SD₀ from H2 and H4 of Cs as an alternative to evaluating the multiplet splitting which can be measured directly in high-resolution ¹H NMR spectra. Experimental data showed striking differences in the mobility of the metabolites when the dipolar coupling constant D₀ (calculated with the internuclear distance known from molecular geometry in the case of complete absence of molecular dynamics and motion) is used for comparison. The aliphatic signals involve very small order parameters S ≈ (1.4 − 3) × 10⁻⁴ indicating rapid reorientation of the corresponding subgroups in these metabolites. In contrast, analysis of the Cs resonances yielded S ≈ (113 − 137) × 10⁻⁴. Thus, the immobilization of the Cs imidazole ring owing to an anisotropic cellular substructure in human m. gastrocnemius is much more effective than for (P)Cr and Tau subgroups. Furthermore, ¹H NMR experiments on aqueous model solutions of histidine and N-acetyl-l-aspartate (NAA) enabled the assignment of an additional signal component at δ = 8 ppm of Cs in vivo to the amide group at the peptide bond. The visibility of this proton could result from hydrogen bonding which would agree with the anticipated stronger motional restriction of Cs. Referring to the observation that all dipolar-coupled multiplets resolved in localized in vivo ¹H NMR spectra of human m. gastrocnemius collapse simultaneously when the fibre structure is tilted towards the magic angle (θ ≈ 55°), a common model for molecular confinement in muscle tissue is proposed on the basis of an interaction of the studied metabolites with myocellular membrane phospholipids.     

Gray code for derangements

We give a Gray code and constant average time generating algorithm for derangements, i.e., permutations with no fixed points. In our Gray code, each derangement is transformed into its successor either via one or two transpositions or a rotation of three elements. We generalize these results to permutations with number of fixed points bounded between two constants.     

The node-edge weighted 2-edge connected subgraph problem: Linear relaxation, facets and separation

Let G=(V,E) be a undirected k-edge connected graph with weights c_e on edges and w_v on nodes. The minimum 2-edge connected subgraph problem, 2ECSP for short, is to find a 2-edge connected subgraph of G, of minimum total weight. The 2ECSP generalizes the well-known Steiner 2-edge connected subgraph problem. In this paper we study the convex hull of the incidence vectors corresponding to feasible solutions of 2ECSP. First, a natural integer programming formulation is given and it is shown that its linear relaxation is not sufficient to describe the polytope associated with 2ECSP even when G is series-parallel. Then, we introduce two families of new valid inequalities and we give sufficient conditions for them to be facet-defining. Later, we concentrate on the separation problem. We find polynomial time algorithms to solve the separation of important subclasses of the introduced inequalities, concluding that the separation of the new inequalities, when G is series-parallel, is polynomially solvable.     

关于限制李超代数的分解

代数$A$ 称为不可分解的,如果 $A$ 不能分解成理想的直和.文中将证明满足$C(L_{\bar{0}})=C(L)=\{0\}$的限制李超代数能够分解成不可分解限制理想的直和,这种分解在不计理想次序的前提下是唯一的.而且还证明了限制李超代数的一些结果.     

The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻_n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s₁,…,s_k,t₁,…,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Identifying phylogenetic trees

A central problem that arises in evolutionary biology is that of displaying partitions of subsets of a finite set X on a tree whose vertices are partially labelled with the elements of X. Such a tree is called an X-tree and, for a collection of partitions of subsets of X, characterisations for the existence and uniqueness of an X-tree that displays have been previously given in terms of chordal graphs. In this paper, we obtain two closely related characterisations also in terms of chordal graphs. The first describes when identifies an X-tree, and the second describes when a compatible subset of is of maximum size.