Lower bounds on signed edge total domination numbers in graphs

The open neighborhood N _G (e) of an edge e in a graph G is the set consisting of all edges having a common end-vertex with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each e ∈ E(G), then f is called a signed edge total dominating function of G. The minimum of the values , taken over all signed edge total dominating function f of G, is called the signed edge total domination number of G and is denoted by γ _st ′(G). Obviously, γ _st ′(G) is defined only for graphs G which have no connected components isomorphic to K ₂. In this paper we present some lower bounds for γ _st ′(G). In particular, we prove that γ _st ′(T) ⩾ 2 − m/3 for every tree T of size m ⩾ 2. We also classify all trees T with γ _st ′(T). Research supported by a Faculty Research Grant, University of West Georgia.     

TWO-DISTANCE PRESERVING FUNCTIONS FROM EUCLIDEAN SPACE

Let 0 < c < s be fixed real numbers such that , and let f : E² → E ^d for d ≥ 2 be a function such that for every p, q ∈ E ² if |p − q| = c, then |f(p) − f(q)| ≤ c, and if |p − q| = s, then |f(p) − f(q)| ≥ s. Then f is a congruence. This result depends on and expands a result of Rádo et. al. [9], where a similar result holds, but for replacing . We also present a further extensions where E² is replaced by E ⁿ for n > 2 and where the range of c/s is enlarged. This revised version was published online in August 2006 with corrections to the Cover Date.     

On the Upper Bounds of the Numbers of Perfect Matchings in Graphs with Given Parameters

Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!].     

On the product of the distances of a point from the vertices of a polytope

Letx ₁,...,x _m be points in the solid unit sphere ofE _n and letx belong to the convex hull ofx ₁,...,x _m. Then . This implies that all such products are bounded by (2/m) ^m (m −1) ^m−1. Bounds are also given for other normed linear spaces. As an application a bound is obtained for |p(z ₀)| where andp′(z ₀)=0.     

A note on the signed edge domination number in graphs

Let G=(V(G),E(G)) be a graph. A function f:E(G)→{+1,−1} is called the signed edge domination function (SEDF) of G if ∑_e^′N[e]f(e^′)≥1 for every eE(G). The signed edge domination number of G is defined as is a SEDF of G}. Xu [Baogen Xu, Two classes of edge domination in graphs, Discrete Applied Mathematics 154 (2006) 1541–1546] researched on the edge domination in graphs and proved that for any graph G of order n(n≥4). In the article, he conjectured that: For any 2-connected graph G of order n(n≥2), . In this note, we present some counterexamples to the above conjecture and prove that there exists a family of k-connected graphs G_m,k with .     

Quadratic programming and combinatorial minimum weight product problems

We present a fully polynomial time approximation scheme (FPTAS) for minimizing an objective (a ^T x + γ)(b ^T x + δ) under linear constraints A x ≤ d. Examples of such problems are combinatorial minimum weight product problems such as the following: given a graph G = (V,E) and two edge weights find an s − t path P that minimizes a(P)b(P), the product of its edge weights relative to a and b.      

New negative Latin square type partial difference sets in nonelementary abelian 2-groups and 3-groups

A partial difference set having parameters (n ², r(n − 1), n + r ² − 3r, r ² − r) is called a Latin square type partial difference set, while a partial difference set having parameters (n ², r(n + 1), − n + r ² + 3r, r ² + r) is called a negative Latin square type partial difference set. Nearly all known constructions of negative Latin square partial difference sets are in elementary abelian groups. In this paper, we develop three product theorems that construct negative Latin square type partial difference sets and Latin square type partial difference sets in direct products of abelian groups G and G′ when these groups have certain Latin square or negative Latin square type partial difference sets. Using these product theorems, we can construct negative Latin square type partial difference sets in groups of the form where the s _i are nonnegative integers and s ₀ + s ₁ ≥ 1. Another significant corollary to these theorems are constructions of two infinite families of negative Latin square type partial difference sets in 3-groups of the form for nonnegative integers s _i . Several constructions of Latin square type PDSs are also given in p-groups for all primes p. We will then briefly indicate how some of these results relate to amorphic association schemes. In particular, we construct amorphic association schemes with 4 classes using negative Latin square type graphs in many nonelementary abelian 2-groups; we also use negative Latin square type graphs whose underlying sets can be elementary abelian 3-groups or nonelementary abelian 3-groups to form 3-class amorphic association schemes.      

Structural formulas and value regions of functionals in certain classes of regular functions

We study the structural properties of the class M_k,λ,b(k≥2, 0≤λ≤1, b∈ℂ\{0}) of functions f(z)=z+ ... which are regular in |z|<1 and satisfy the conditions f(z)f′(z)z⁻¹≠0 and , where J(z)=λ(1+b⁻¹zf″(z)/f′(z)+(1−λ)(b⁻¹zf′(z)/f(z)+1−b⁻¹). The value regions of some functionals on this class are found. The case λ=1 was considered in our previous paper. Bibliography: 4 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 204, 1993, pp. 55–60. Translated by O. A. Ivanov.     

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

Fourier and Hermite series estimates of regression functions

Summary In the paper we estimate a regressionm(x)=E {Y|X=x} from a sequence of independent observations (X ₁,Y ₁),…, (X _n, Y_n) of a pair (X, Y) of random variables. We examine an estimate of a type , whereN depends onn andϕ _N is Dirichlet kernel and the kernel associated with the hermite series. Assuming, that E|Y|<∞ and |Y|≦γ≦∞, we give condition for to converge tom(x) at almost allx, provided thatX has a density. if the regression hass derivatives, then converges tom(x) as rapidly asO(nC^{−(2s−1)/4s}) in probability andO(n ^{−(2s−1)/4s} logn) almost completely.     

On the characterization of trees with signed edge domination numbers 1, 2, 3, or 4

Let G=(V,E) be a simple graph. For an edge e of G, the closed edge-neighbourhood of e is the set N[e]={e^′∈E|e^′ is adjacent to e}∪{e}. A function f:E→{1,−1} is called a signed edge domination function (SEDF) of G if ∑_e^′∈N[e]f(e^′)≥1 for every edge e of G. The signed edge domination number of G is defined as . In this paper, we characterize all trees T with signed edge domination numbers 1, 2, 3, or 4.     

Remainder estimates for the approximation numbers of weighted Hardy operators acting onL 2

We consider the weighted Hardy integral operatorT:L ²(a, b) →L ²(a, b), −∞≤a<b≤∞, defined by . In [EEH1] and [EEH2], under certain conditions onu andv, upper and lower estimates and asymptotic results were obtained for the approximation numbersa _n(T) ofT. In this paper, we show that under suitable conditions onu andv, where ∥w∥_p=(∫ _a ^b |w(t)|^p dt)^1/p. Research supported by NSERC, grant A4021. Research supported by grant No. 201/98/P017 of the Grant Agency of the Czech Republic.     

Analysis of the impact of the number of edges in connected graphs on the computational complexity of the independent set problem

Under study is the complexity status of the independent set problem in a class of connected graphs that are defined by functional constraints on the number of edges depending on the number of vertices. For every natural number C, this problem is shown to be polynomially solvable in the class of graphs

The Balian-Low theorem and regularity of Gabor systems

For any positive real numbers A, B, and d satisfying the conditions , d>2, we construct a Gabor orthonormal basis for L²(ℝ), such that the generating function g∈L²(ℝ) satisfies the condition:∫_ℝ|g(x)|²(1+|x| ^A )/log ^d (2+|x|)dx < ∞ and .     

A lower bound on the total signed domination numbers of graphs

Let G be a finite connected simple graph with a vertex set V(G)and an edge set E(G). A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1}.The weight of f is W(f)=∑_(x∈V)(G)∪E(G))f(X).For an element x∈V(G)∪E(G),we define f[x]=∑_(y∈NT[x])f(y).A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1} such that f[x]≥1 for all x∈V(G)∪E(G).The total signed domination numberγ_s~*(G)of G is the minimum weight of a total signed domination function on G. In this paper,we obtain some lower bounds for the total signed domination number of a graph G and compute the exact values ofγ_s~*(G)when G is C_n and P_n.     

Very weak solutions to elliptic equations with nonlinear Neumann boundary conditions

Consider the equation −Δu = 0 in a bounded smooth domain , complemented by the nonlinear Neumann boundary condition ∂_ν u = f(x, u) − u on ∂Ω. We show that any very weak solution of this problem belongs to L ^∞(Ω) provided f satisfies the growth condition |f(x, s)| ≤ C(1 + |s| ^p ) for some p ∈ (1, p*), where . If, in addition, f(x, s) ≥ −C + λs for some λ > 1, then all positive very weak solutions are uniformly a priori bounded. We also show by means of examples that p* is a sharp critical exponent. In particular, using variational methods we prove the following multiplicity result: if N ∈ {3, 4} and f(x, s) =  s ^p then there exists a domain Ω and such that our problem possesses at least two positive, unbounded, very weak solutions blowing up at a prescribed point of ∂Ω provided . Our regularity results and a priori bounds for positive very weak solutions remain true if the right-hand side in the differential equation is of the form h(x, u) with h satisfying suitable growth conditions.     

On the riemann zeta-function and the divisor problem II

Let Δ(x) denote the error term in the Dirichlet divisor problem, and E(T) the error term in the asymptotic formula for the mean square of . If E ^*(t)=E(t)-2πΔ^*(t/2π) with , then we obtain

A general result on precise asymptotics for linear processes of positively associated sequences

Let {εt; t ∈ Z^＋} be a strictly stationary sequence of associated random variables with mean zeros, let 0〈Eε1^2〈∞ and σ^2=Eε1^2＋1∑j=2^∞ Eε1εj with 0〈σ^2〈∞.{aj;j∈Z^＋} is a sequence of real numbers satisfying ∑j=0^∞｜aj｜〈∞.Define a linear process Xt=∑j=0^∞ ajεt-j,t≥1,and Sn=∑t=1^n Xt,n≥1.Assume that E｜ε1｜^2＋δ′〈 for some δ′〉0 and μ（n）=O（n^-ρ） for some ρ〉0.This paper achieves a general law of precise asymptotics for {Sn}.     

On <Emphasis Type="Bold">(c,p)</Emphasis>-pseudostable Random Variables

In (Oleszkiewicz, Lecture Notes in Math. 1807), K. Oleszkiewicz defined a p-pseudostable random variable X as a symmetric random variable for which the following equation holds:

Estimating a general function of a quadratic function

Let be an observation from a spherically symmetric distribution with unknown location parameter . For a general non-negative function c, we consider the problem of estimating c(||x − θ||²) under the usual quadratic loss. For p ≥ 5, we give sufficient conditions for improving on the unbiased estimator γ₀ of c(||x − θ||²) by competing estimators γ _s = γ₀ + s correcting γ₀ with a suitable function s. The main condition relies on a partial differential inequality of the form k Δs + s ² ≤ 0 for a certain constant k ≠ 0. Our approach unifies, in particular, the two problems of quadratic loss estimation and confidence statement estimation and allows to derive new results for these two specific cases. Note that we formally establish our domination results (that is, with no recourse to simulation).