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.     

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 Ω.     

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.     

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     

Highly edge‐connected detachments of graphs and digraphs

Let G = (V,E) be a graph or digraph and r : V → Z₊. An r‐detachment of G is a graph H obtained by ‘splitting’ each vertex ν ∈ V into r(ν) vertices. The vertices ν₁,…,ν_r(ν) obtained by splitting ν are called the pieces of ν in H. Every edge uν ∈ E corresponds to an edge of H connecting some piece of u to some piece of ν. Crispin Nash‐Williams 9 gave necessary and sufficient conditions for a graph to have a k‐edge‐connected r‐detachment. He also solved the version where the degrees of all the pieces are specified. In this paper, we solve the same problems for directed graphs. We also give a simple and self‐contained new proof for the undirected result. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 67–77, 2003     

The Ends of Manifolds with Bounded Geometry, Linear Growth and Finite Filling Area

We prove that simply connected open manifolds of bounded geometry, linear growth and sublinear filling growth (e.g. finite filling area) are simply connected at infinity.     

From dilute to dense self-avoiding walks on hypercubic lattices

A field-theoretic representation is presented to count the number of configurations of a single self-avoiding walk on a hypercubic lattice ind dimensions with periodic boundary conditions. We evaluate the connectivity constant as a function of the fractionf of sites occupied by the polymer chain. The meanfield approximation is exact in the limit of infinite dimensions, and corrections to it in powers ofd ^–1 can be systematically evaluated. The connectivity constant and the site entropy calculated throughout second order compare well with known results in two and three dimensions. We also find that the entropy per site develops a maximum atf1–(2d)^–1. Ford=2 (d=3), this maximum occurs atf~0.80 (f~0.86) and its value is about 50% (30%) higher than the entropy per site of a Hamiltonian walk (f=1).     

取代苯酚的定量结构－活性／性质相关性研究

在分子拓扑理论基础上,提出了一个新的价连接性指数~nG=∑(E_i·E_j· E_k...),其中~0G=∑(E_i),~1G=∑(E_i·E_j),并用~0G,~1G研究了取代苯酚（ 含Cl,Br,INH_2,NO_2,COOH,烷基、环烷基、苯基等）的溶解度,辛醇／水分 配系数及对黑曲霉、浮萍、细胞色素P－450、酵母菌等的生物活性,给出了相关方 程。结果表明,新方法计算简单,使用方便,预测值与相应的实验值较好吻合。     

Topological investigations of molar excess volumes of quinoline with alkanols

Excess volumes V ^E of binary liquid mixtures of quinoline with alkanols have been determined from densities at 30°C as a function of composition. The excess volumes are negative over the whole mole fraction range for all the mixtures and decrease with increasing length of alkanol (C₁–C₁₀). The V^E data have been analyzed in terms of an approach which uses graph theoretical connectivity parameters of the third degrees for two components. The analysis gives information regarding associated species in the pure state and in the mixture. It is suggested that, in the mixture state, no change occurs in the association of alkanols.