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.     

Sizes of Critical Graphs with Small Maximum Degrees

In this paper, we give new lower bounds for the size of Δ-critical graphs with Δ=8,9 which improve the partial results of Luo [6] and Y. Zhao [12].     

Measurements of edge-uncolorability

Cubic bridgeless graphs with chromatic index four are called uncolorable. We introduce parameters measuring the uncolorability of those graphs and relate them to each other. For k=2,3, let c_k be the maximum size of a k-colorable subgraph of a cubic graph G=(V,E). We consider r₃=|E|−c₃ and . We show that on one side r₃ and r₂ bound each other, but on the other side that the difference between them can be arbitrarily large. We also compare them to the oddness ω of G, the smallest possible number of odd circuits in a 2-factor of G. We construct cyclically 5-edge connected cubic graphs where r₃ and ω are arbitrarily far apart, and show that for each 1c<2 there is a cubic graph such that ωcr₃. For k=2,3, let ζ_k denote the largest fraction of edges that can be k-colored. We give best possible bounds for these parameters, and relate them to each other.     

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     

Growth of Lévy trees

We construct random locally compact real trees called Lévy trees that are the genealogical trees associated with continuous-state branching processes. More precisely, we define a growing family of discrete Galton–Watson trees with i.i.d. exponential branch lengths that is consistent under Bernoulli percolation on leaves; we define the Lévy tree as the limit of this growing family with respect to the Gromov–Hausdorff topology on metric spaces. This elementary approach notably includes supercritical trees and does not make use of the height process introduced by Le Gall and Le Jan to code the genealogy of (sub)critical continuous-state branching processes. We construct the mass measure of Lévy trees and we give a decomposition along the ancestral subtree of a Poisson sampling directed by the mass measure. T. Duquesne is supported by NSF Grants DMS-0203066 and DMS-0405779. M. Winkel is supported by Aon and the Institute of Actuaries, EPSRC Grant GR/T26368/01, le département de mathématique de l’Université d’Orsay and NSF Grant DMS-0405779.     

The analysis of thermal stresses in thermopiezoelastic semi-infinite body with an edge crack

Summary  Thermopiezoelastic materials have recently attracted considerable attention because of their potential use in intelligent or smart structural systems. The governing equations of a thermopiezoelastic medium are more complex due to the intrinsic coupling effects that take place among mechanical, electrical and thermal fields. In this analysis, we deal with the problem of a crack in a semi-infinite, transversely isotropic, thermopiezoelastic material by means of potential functions and Fourier transforms under steady heat-flux loading conditions. The problem is reduced to a singular integral equation that is solved. The thermal stress intensity factor for a crack situated in a cadmium selenide material is calculated. Received 20 March 2001; accepted for publication 18 October 2001     

Special simplices and Gorenstein toric rings

Athanasiadis [Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley, J. Reine Angew. Math., to appear.] studies an effective technique to show that Gorenstein sequences coming from compressed polytopes are unimodal. In the present paper we will use such the technique to find a rich class of Gorenstein toric rings with unimodal h-vectors arising from finite graphs.