Hamilton cycles,avoiding prescribed arcs,in close-to-regular tournaments

The local irregularity of a digraph D is defined as i_l(D) = max {|d⁺ (x) − d⁻ (x)| : x ϵ V(D)}. Let T be a tournament, let Γ = {V₁, V₂, …, V_c} be a partition of V(T) such that |V₁| ≥ |V₂| ≥ … ≥ |V_c|, and let D be the multipartite tournament obtained by deleting all the arcs with both end points in the same set in Γ. We prove that, if |V(T)| ≥ max{2i_l(T) + 2|V₁| + 2|V₂| − 2, i_l(T) + 3|V₁| − 1}, then D is Hamiltonian. Furthermore, if T is regular (i.e., i_l(T) = 0), then we state slightly better lower bounds for |V(T)| such that we still can guarantee that D is Hamiltonian. Finally, we show that our results are best possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 123–136, 1999     

How Close to Regular Must a Semicomplete Multipartite Digraph Be to Secure Hamiltonicity?

 Let D be a semicomplete multipartite digraph, with partite sets V ₁, V ₂,…, V _c, such that |V ₁|≤|V ₂|≤…≤|V _c|. Define f(D)=|V(D)|−3|V _c|+1 and . We define the irregularity i(D) of D to be max|d ⁺(x)−d ⁻(y)| over all vertices x and y of D (possibly x=y). We define the local irregularity i _l(D) of D to be max|d ⁺(x)−d ⁻(x)| over all vertices x of D and we define the global irregularity of D to be i _g(D)=max{d ⁺(x),d ⁻(x) : x∈V(D)}−min{d ⁺(y),d ⁻(y) : y∈V(D)}. In this paper we show that if i _g(D)≤g(D) or if i _l(D)≤min{f(D), g(D)} then D is Hamiltonian. We furthermore show how this implies a theorem which generalizes two results by Volkmann and solves a stated problem and a conjecture from [6]. Our result also gives support to the conjecture from [6] that all diregular c-partite tournaments (c≥4) are pancyclic, and it is used in [9], which proves this conjecture for all c≥5. Finally we show that our result in some sense is best possible, by giving an infinite class of non-Hamiltonian semicomplete multipartite digraphs, D, with i _g(D)=i(D)=i _l(D)=g(D)+?≤f(D)+1. Revised: September 17, 1998     

RELATIONS AMONG SOME PARAMETERS OF HYPERGRAPHS

The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows：Dv（H）≤min{α≤（H）, p（H）, p（H）, T（H）}; De（H）≤min{v（H）, T（H）, p（H）}; DT（H） ≤αT（H）; S（H）≤ Dv （H） ＋ α（H）≤n; 2≤ Dv （H） ＋ T（H） ≤n; 2 〈 Dv （H） ＋ v（H）≤n/2 ＋ [n/r]; Dv （H） ＋ p（H） 〈_n;2≤De（H） ＋ Dv（H）≤n/2 ＋ [n/r];α（H） ＋ De（H）≤n;2 ≤ De（H） ＋ v（H）≤2[n/r]; 2 De（H） ＋ p（H）≤n-r ＋ 2.     

Graph diameter in long‐range percolation

We study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in ${\mathbb Z}^dWe study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in ${\mathbb Z}^d$. We focus on the cases when an edge between x and y is added with probability decaying with the Euclidean distance as |x ? y|^?s+o(1) when |x ? y| → ∞. For s ∈ (d, 2d) we show that the graph diameter for the graph reduced to a box of side L scales like (log L)^Δ+o(1) where Δ^?1 := log₂(2d/s). In particular, the diameter grows about as fast as the typical graph distance between two vertices at distance L. We also show that a ball of radius r in the intrinsic metric on the (infinite) graph will roughly coincide with a ball of radius exp{r^1/Δ+o(1)} in the Euclidean metric. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 210‐227, 2011     

Connected subgraphs with small degree sums in 3‐connected planar graphs

It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σ_x∈V(H) deg_G(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999     

Embedding graphs with bounded degree in sparse pseudorandom graphs

In this paper, we show the equivalence of somequasi-random properties for sparse graphs, that is, graphsG with edge densityp=|E(G)|/( ₂ ⁿ )=o(1), whereo(1)→0 asn=|V(G)|→∞. Our main result (Theorem 16) is the following embedding result. For a graphJ, writeN _J(x) for the neighborhood of the vertexx inJ, and letδ(J) andΔ(J) be the minimum and the maximum degree inJ. LetH be atriangle-free graph and setd _H=max{δ(J):J⊆H}. Moreover, putD _H=min{2d _H,Δ(H)}. LetC>1 be a fixed constant and supposep=p(n)≫n ⁻¹ D _H. We show that ifG is such that

Partial Parity (g,f )-Factors and Subgraphs Covering Given Vertex Subsets

 Let G be a graph and W a subset of V(G). Let g,f:V(G)→Z be two integer-valued functions such that g(x)≤f(x) for all x∈V(G) and g(y)≡f(y) (mod 2) for all y∈W. Then a spanning subgraph F of G is called a partial parity (g,f)-factor with respect to W if g(x)≤deg _F (x)≤f(x) for all x∈V(G) and deg _F (y)≡f(y) (mod 2) for all y∈W. We obtain a criterion for a graph G to have a partial parity (g,f)-factor with respect to W. Furthermore, by making use of this criterion, we give some necessary and sufficient conditions for a graph G to have a subgraph which covers W and has a certain given property. Received: June 14, 1999?Final version received: August 21, 2000     

Identifying codes and locating-dominating sets on paths and cycles

Let G=(V,E) be a graph and let r≥1 be an integer. For a set D⊆V, define N_r[x]={y∈V:d(x,y)≤r} and D_r(x)=N_r[x]∩D, where d(x,y) denotes the number of edges in any shortest path between x and y. D is known as an r-identifying code (r-locating-dominating set, respectively), if for all vertices x∈V (x∈V?D, respectively), D_r(x) are all nonempty and different. Roberts and Roberts [D.L. Roberts, F.S. Roberts, Locating sensors in paths and cycles: the case of 2-identifying codes, European Journal of Combinatorics 29 (2008) 72-82] provided complete results for the paths and cycles when r=2. In this paper, we provide results for a remaining open case in cycles and complete results in paths for r-identifying codes; we also give complete results for 2-locating-dominating sets in cycles, which completes the results of Bertrand et al. [N. Bertrand, I. Charon, O. Hudry, A. Lobstein, Identifying and locating-dominating codes on chains and cycles, European Journal of Combinatorics 25 (2004) 969-987].     

Generalized Hopf Formulas for the Nonautonomous Hamilton–Jacobi Equation

Generalized Hopf formulas are provided for minimax (viscosity) solutions of Hamilton–Jacobi equations of the form V _t + H(t, D _x V) = 0 and V _t + H(t, V, D _x V) = 0 with the boundary condition V(T, x) = (x), where is a convex function. The bounds within which these formulas apply are elucidated.     

Inequalities for Means in Two Variables

We present various new inequalities involving the logarithmic mean L(x,y)=(x-y)/(logx-logy) L(x,y)=(x-y)/(\log{x}-\log{y}) , the identric mean I(x,y)=(1/e)(x^x/y^y)^1/(x-y) I(x,y)=(1/e)(x^x/y^y)^{1/(x-y)} , and the classical arithmetic and geometric means, A(x,y)=(x+y)/2 A(x,y)=(x+y)/2 and G(x,y)=?{xy} G(x,y)=\sqrt{xy} . In particular, we prove the following conjecture, which was published in 1986 in this journal. If M_r(x,y) = (x^r/2+y^r/2)^1/r(r 1 0) M_r(x,y)= (x^r/2+y^r/2)^{1/r}(r\neq{0}) denotes the power mean of order r, then $ M_c(x,y)<\frac{1}{2}(L(x,y)+I(x,y)) {(x,y>0,\, x\neq{y})} $ M_c(x,y)<\frac{1}{2}(L(x,y)+I(x,y)) {(x,y>0,\, x\neq{y})} with the best possible parameter c=(log2)/(1+log2) c=(\log{2})/(1+\log{2}) .     

Asymptotic Behaviour of C0–Semigroups with Bounded Local Resolvents

Let {T(t)}_t≥0 be a C₀–semigroup on a Banach space X with generator A, and let H^∞_T be the space of all x ∈ X such that the local resolvent λ ↦ R(λ, A)x has a bounded holomorphic extension to the right half–plane. For the class of integrable functions ϕ on [0, ∞) whose Fourier transforms are integrable, we construct a functional calculus ϕ ↦ T_ϕ, as operators on H^∞_T. Weshow that each orbit T(·)T_ϕx is bounded and uniformly continuous, and T(t)T_ϕx → 0 weakly as t → ∞, and we give a new proof that ∥T(t)R(μ, A)x∥ = O(t). We also show that ∥T(t)T_ϕx∥ → 0 when T is sun –reflexive, and that ∥T(t)R(μ, A)x∥ = O(ln t) when T is a positive semigroup on a normal ordered space X and x is a positive vector in H^∞_T.     

On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998     

Hyperquasipolynomials for the Theta-Function

Let g be a linear combination with quasipolynomial coefficients of shifts of the Jacobi theta function and its derivatives in the argument. All entire functions f: ? → ? satisfying f(x+y)g(x?y) = α₁(x)β₁(y)+· · ·+α_r(x)β_r(y) for some r ∈ ? and α_j, β_j: ? → ? are described.     

Analytic Extension of Non Quasi - Analytic Whitney Jets of Beurling Type

Let (M_r)_r∈_?0 be a logarithmically convex sequence of positive numbers which verifies M₀ = 1 as well as M_r ≥ 1 for every r ∈ ? and defines a non quasi - analytic class. Let moreover F be a closed proper subset of ?ⁿ. Then for every function f on ?ⁿ belonging to the non quasi - analytic (M_r)-class of Beurling type, there is an element g of the same class which is analytic on ?,ⁿ F and such that D^αf(x) = D^αg(x) for every α ∈ ?ⁿ₀ and x ∈ F.     

Some generalizations of the first Fredholm theorem to multivalued A-proper mappings with applications to nonlinear elliptic equations

Let X and Y be real normed spaces with an admissible scheme Γ = {E_n, V_n; F_n, W_n} and T: X → 2^YA-proper with respect to Γ such that dist(y, A(x)) < kc(∥ x ∥) for all y in T(x) with ∥ x ∥ ? R for some R > 0 and k > 0, where c: R⁺ → R⁺ is a given function and A: X → 2^Y a suitable possibly not A-proper mapping. Under the assumption that either T or A is odd or that (u, Kx) ? 0 for all u in T(x) with $\text{∥ x ∥ ? r > 0}\text{and some}\text{K: X → Y}{}^1$, we obtain (in a constructive way) various generalizations of the first Fredholm theorem. The unique approximation-solvability results for the equation T(x) = f with T such that T(x) ? T(y) ?A(x ? y) for x, y in X or T is Fréchet differentiable are also established. The abstract results for A-proper mappings are then applied to the (constructive) solvability of some boundary value problems for quasilinear elliptic equations. Some of our results include the results of Lasota, Lasota-Opial, Hess, Ne?as, Petryshyn, and Babu?ka.     

On a stopped functional for a bidimensional process

Consider a bidimensional process Q_t = (x_t, y_t) consisting of an Ornstein–Uhlenbeck process and a geometric Brownian motion, respectively. Let T be the first time the process x_t hits a constant positive level b > 0. Under certain conditions, we give an explicit form for a stopped functional.u(x,y)=E^x,y[y^m(T)h(x(T))e^-αT],where m, α > 0 are fixed constants and h : R₊ → R is a bounded continuous function.The present result is derived using the method of similarity solutions and the result has many applications in mathematical finance.     

Equations fonctionnelles et estimations de normes de matrices

We solve independently the equations 1/θ(x)θ(y)=ψ(x)−ψ(y)+φ(x−y)/θ(x−y) and 1/θ(x)θ(y)=σ(x)−σ(y)/θ(x−y)+τ(x)τ(y), τ(0)=0. In both cases we find θ²=aθ⁴+bθ²+c. We deduce estimates for the spectral radius of a matrix of type(1/θ(x _r −x _s )) (the accent meaning that the coefficients of the main diagonal are zero) and we study the case where thex _r are equidistant.

Dédié to à Monsieur le Professeur Otto Haupt à l'occasion de son cententiare avec les meilleurs voeux     

Nonlocal initial-boundary-value problems for a degenerate hyperbolic equation

We consider the equation y ^m u _xx − u _yy − b ² y ^m u = 0 in the rectangular area {(x, y) | 0 < x < 1, 0 < y < T}, where m < 0, b ≥ 0, T > 0 are given real numbers. For this equation we study problems with initial conditions u(x, 0) = τ(x), u _y (x, 0) = ν(x), 0 ≤ x ≤ 1, and nonlocal boundary conditions u(0, y) = u(1, y), u _x (0, y) = 0 or u _x (0, y) = u _x (1, y), u(1, y) = 0 with 0≤y≤T. Using the method of spectral analysis, we prove the uniqueness and existence theorems for solutions to these problems     

Markov-type Inequalities for Surface Gradients of Multivariate Polynomials

Let K ^d be a compact set with a smooth boundary and consider a polynomial p of total degree n such that p_C(K)1. Then we show that D_Tp(x)=o(n²) for any x Bd K and T a tangential direction at x. Moreover, the o(n²) term is given in terms of the modulus of smoothness of Bd K.     

Monogenic functions in the biharmonic boundary value problem

We consider a commutative algebra over the field of complex numbers with a basis {e₁,e₂} satisfying the conditions , . Let D be a bounded domain in the Cartesian plane xOy and D_ζ={xe₁+ye₂:(x,y)∈D}. Components of every monogenic function Φ(xe₁+ye₂) = U₁(x,y)e₁+U₂(x,y)ie₁+U₃(x,y)e₂+U₄(x,y)ie₂ having the classic derivative in D_ζ are biharmonic functions in D, that is, Δ²U_j(x,y) = 0 for j = 1,2,3,4. We consider a Schwarz‐type boundary value problem for monogenic functions in a simply connected domain D_ζ. This problem is associated with the following biharmonic problem: to find a biharmonic function V(x,y) in the domain D when boundary values of its partial derivatives ?V/?x, ?V/?y are given on the boundary ?D. Using a hypercomplex analog of the Cauchy‐type integral, we reduce the mentioned Schwarz‐type boundary value problem to a system of integral equations on the real axes and establish sufficient conditions under which this system has the Fredholm property. Copyright © 2015 John Wiley & Sons, Ltd.