On λ-harmonic graphs

A λ harmonic graph G, a λ-Hgraph G for short, means that there exists a constant A such that the equality λd（ui） = ∑（vi,vj）∈E（G） d（vj） holds for all i = 1, 2,…, ｜V（G）｜, where d（vi） denotes the degree of vertex vi. In this paper, some harmonic properties of the complement and line graph are given, and some algebraic properties for the λ-Hgraphs are obtained.     

Comparison of exact constants in Kolmogorov-type inequalities for periodic and nonperiodic functions of many variables

We investigate the correlation between the constants K(ℝⁿ) and , where

The roots of <Emphasis Type="Italic">σ</Emphasis>-polynomials

Let G be a connected graph. We denote by σ(G,x) and δ(G) respectively the σ-polynomial and the edge-density of G, where . If σ(G,x) has at least an unreal root, then G is said to be a σ-unreal graph. Let δ(n) be the minimum edgedensity over all n vertices graphs with σ-unreal roots. In this paper, by using the theory of adjoint polynomials, a negative answer to a problem posed by Brenti et al. is given and the following results are obtained: For any positive integer a and rational number 0≤c≤1, there exists at least a graph sequence {G _i}_1≤i≤a such that G _i is σ-unreal and δ(G _i)→c as n→∞ for all 1 ≤i≤a, and moreover, δ(n)→0 as n→∞. Supported by the National Natural Science Foundation of China (10061003) and the Science Foundation of the State Education Ministry of China.     

Score sets in oriented 3-partite graphs

Let D(U, V, W) be an oriented 3-partite graph with |U|=p, |V|=q and |W|= r. For any vertex x in D(U, V, W), let d x and d-x be the outdegree and indegree of x respectively. Define aui (or simply ai) = q r d ui - d-ui, bvj(or simply bj) = p r d vj - d-vj and Cwk (or simply ck) = p q d wk - d-wk as the scores of ui in U, vj in V and wk in Wrespectively. The set A of distinct scores of the vertices of D(U, V, W) is called its score set. In this paper, we prove that if a1 is a non-negative integer, ai(2≤i≤n - 1) are even positive integers and an is any positive integer, then for n≥3, there exists an oriented 3-partite graph with the score set A = {a1,2∑i=1 ai,…,n∑i=1 ai}, except when A = {0,2,3}. Some more results for score sets in oriented 3-partite graphs are obtained.     

Non-wandering points and the depth for graph maps

Let G be a graph and f:G→G be continuous.Denote by R(f) andΩ(f) the set of recurrent points and the set of non-wandering points of f respectively.LetΩ_0(f) = G andΩ_n(f)=Ω(f|_(Ω_(n-1)(f))) for all n∈N.The minimal m∈NU {∞} such thatΩ_m(f)=Ω_(m 1)(f) is called the depth of f.In this paper,we show thatΩ_2 (f)=(?) and the depth of f is at most 2.Furthermore,we obtain some properties of non-wandering points of f.     

On the multiplicity of the eigenvalues of a graph

Given a graph G with characteristic polynomial ϕ(t), we consider the ML-decomposition ϕ(t) = q ₁(t)q ₂(t)² ... q _m (t)^m, where each q _i (t) is an integral polynomial and the roots of ϕ(t) with multiplicity j are exactly the roots of q _j (t). We give an algorithm to construct the polynomials q _i (t) and describe some relations of their coefficients with other combinatorial invariants of G. In particular, we get new bounds for the energy E(G) = |λ_i| of G, where λ₁, λ₂, ..., λ_n are the eigenvalues of G (with multiplicity). Most of the results are proved for the more general situation of a Hermitian matrix whose characteristic polynomial has integral coefficients. This work was done during a visit of the second named author to UNAM.     

A general oscillation theorem for self-adjoint differential systems with applications to Sturm-Liouville eigenvalue problems and quadratic functionals

For given 2n×2n matricesS ₁₃,S ₂₄ with rank(S ₁₃,S ₂₄)=2n we consider the eigenvalue problem:u′=A(x)u+B(x)v,v′=C ₁(x;λ)u-A ^T(x)v with

Pan-connectedness of graphs with large neighborhood unions

Let G be a simple graph with n vertices. For any , let , and , and and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC ₂(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC ₂(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC ₂(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.      

Evaluation of infinite series involving special products and their algebraic characterization

The aim of the paper is the investigation of special infinite series of the form

A divergent Khintchine theorem in the real,complex, and <Emphasis Type="Italic">p</Emphasis>-adic fields

In this paper, we show that if the sum ∑_r=1^∞ Ψ(r) diverges, then the set of points (x, z, w) ∈ ℝ × ℂ × ℚ_p satisfying the inequalities , and for infinitely many integer polynomials P has full measure. With a special choice of parameters v _i and λ _i , i = 1, 2, 3, we can obtain all the theorems in the metric theory of transcendental numbers which were known in the real, complex, or p-adic fields separately.     

The Existence of BIB Designs

Abstract Given any positive integers k≥ 3 and λ, let c(k, λ) denote the smallest integer such that v∈B(k, λ) for every integer v≥c(k, λ) that satisfies the congruences λv(v− 1) ≡ 0(mod k(k− 1)) and λ(v− 1) ≡ 0(mod k− 1). In this article we make an improvement on the bound of c(k, λ) provided by Chang in [4] and prove that . In particular, . Supported by NSFC Grant No. 19701002 and Huo Yingdong Foundation     

Remarks on Spectral Radius and Laplacian Eigenvalues of a Graph

Let G be a graph with n vertices, m edges and a vertex degree sequence (d ₁, d ₂,..., d _n ), where d ₁ ≥ d ₂ ≥ ... ≥ d _n . The spectral radius and the largest Laplacian eigenvalue are denoted by ϱ(G) and μ(G), respectively. We determine the graphs with

Gauss-Bonnet Formula, Finiteness Condition, and Characterizations of Graphs Embedded in Surfaces

Let G be an infinite graph embedded in a closed 2-manifold, such that each open face of the embedding is homeomorphic to an open disk and is bounded by finite number of edges. For each vertex x of G, define the combinatorial curvature

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

Almost sure convergence of sample range

Let X ₁, X ₂, ... be i.i.d. random variables. The sample range is R _n = max {X _i , 1 ≤ i ≤ n} − min {X _i , 1 ≤ i ≤ n}. If for a non-degenerate distribution G and some sequences (α _k ), (β _k ) then we have

Positive Solution of Multi-Point Boundary Value Problems for the One-Dimensional p-Laplacian with Singularities

In this paper, we obtain positive solution to the following multi-point singular boundary value problem with p-Laplacian operator,{（ φp（u＇））＇＋q（t）f（t,u,u＇）=0,0〈t〈1,u（0）=∑i=1^nαiu（ξi）,u＇（1）=∑i=1^nβiu＇（ξi）,whereφp（s）=｜s｜^p-2s,p≥2;ξi∈（0,1）（i=1,2,…,n）,0≤αi,βi〈1（i=1,2,…n）,0≤∑i=1^nαi,∑i=1^nβi〈1,and q（t） may be singular at t=0,1,f（t,u,u＇）may be singular at u＇=0     

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.     

The value regions of initial coefficients in a certain class of meromorphic functions

Let M_k,λ(0≤λ≤1, k≥2) be the class of functions f(z)=1/z+a_o+a₁z+... that are regular and locally univalent for 0<⩛z⩛<1 and satisfy the condition where J_λ(z)=λ(1+zf″(z)/f'(z))+(1-λ)zf'(z)/f(z). In the class M_k,λ we consider sorne coefficient problems and problems concerning distortion theorems. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 212, 1994, pp. 91–96. Translated by N. Yu. Netsvetaev.     

On the Cubicity of Interval Graphs

A k-cube (or “a unit cube in k dimensions”) is defined as the Cartesian product where R _i (for 1 ≤ i ≤ k) is an interval of the form [a _i , a _i  + 1] on the real line. The k-cube representation of a graph G is a mapping of the vertices of G to k-cubes such that the k-cubes corresponding to two vertices in G have a non-empty intersection if and only if the vertices are adjacent. The cubicity of a graph G, denoted as cub(G), is defined as the minimum dimension k such that G has a k-cube representation. An interval graph is a graph that can be represented as the intersection of intervals on the real line - i.e., the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. We show that for any interval graph G with maximum degree Δ, . This upper bound is shown to be tight up to an additive constant of 4 by demonstrating interval graphs for which cubicity is equal to .