The upper traceable number of a graph

For a nontrivial connected graph G of order n and a linear ordering s: v ₁, v ₂, …, v _n of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t ⁺(G) of G is t ⁺(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t ⁺(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand under the grant number MRG 5080075.     

Admissibility of the natural estimator of the mean of a Gaussian process

Let {X(t): t [a, b]} be a Gaussian process with mean μ L₂[a, b] and continuous covariance K(s, t). When estimating μ under the loss ∫_a^b ( (t)−μ(t))² dt the natural estimator X is admissible if K is unknown. If K is known, X is minimax with risk ∫_a^b K(t, t) dt and admissible if and only if the three by three matrix whose entries are K(t_i, t_j) has a determinant which vanishes identically in t_i [a, b], i = 1, 2, 3.     

Partitions of a graph into paths with prescribed endvertices and lengths

For a graph G, let σ₂(G) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| = n = Σ^k_{i = 1} a_i and σ₂(G) ≥ n + k − 1, then for any k vertices v₁, v₂,…, v_k in G, there exist vertex‐disjoint paths P₁, P₂,…, P_k such that |V(P_i)| = a_i and v_i is an endvertex of P_i for 1 ≤ i ≤ k. In this paper, we verify the conjecture for the cases where almost all a_i ≤ 5, and the cases where k ≤ 3. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 163–169, 2000     

A note on graphs and sphere orders

A partially ordered set P is called a k-sphere order if one can assign to each element a ∈ P a ball B_a in R^k so that a < b iff B_a ? B_b. To a graph G = (V,E) associate a poset P(G) whose elements are the vertices and edges of G. We have v < e in P(G) exactly when v ∈ V, e ∈ E, and v is an end point of e. We show that P(G) is a 3-sphere order for any graph G. It follows from E. R. Scheinerman [“A Note on Planar Graphs and Circle Orders,” SIAM Journal of Discrete Mathematics, Vol. 4 (1991), pp. 448–451] that the least k for which G embeds in R^k equals the least k for which P(G) is a k-sphere order. For a simplicial complex K one can define P(K) by analogy to P(G) (namely, the face containment order). We prove that for each 2-dimensional simplicial complex K, there exists a k so that P(K) is a k-sphere order. © 1993 John Wiley & Sons, Inc.     

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

A note on traversing specified vertices in graphs embedded with large representativity

A graph G is said to have property P(2,k) if given any k+2 distinct vertices a,b,v₁,…,v_k, there is a path P in G joining a and b and passing through all of v₁,…,v_k. A graph G is said to have property C(k) if given any k distinct vertices v₁,…,v_k, there is a cycle C in G containing all of v₁,…,v_k. It is shown that if a 4-connected graph G is embedded in an orientable surface Σ (other than the sphere) of Euler genus eg(G,Σ), with sufficiently large representativity (as a function of both eg(G,Σ) and k), then G possesses both properties P(2,k) and C(k).     

Distance in stratified graphs

A graph G is stratified if its vertex set is partitioned into classes, called strata. If there are k strata, then G is k-stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color X in a stratified graph G, the X-eccentricity e _X(v) of a vertex v of G is the distance between v and an X-colored vertex furthest from v. The minimum X-eccentricity among the vertices of G is the X-radius rad_X G of G and the maximum X-eccentricity is the X-diameter diam_X G. It is shown that for every three positive integers a, b and k with ab, there exist a k-stratified graph G with rad_X G = a and diam_X G = b. The number s _X denotes the minimum X-eccetricity among the X-colored vertices of G. It is shown that for every integer t with rad_X G t diam_X G, there exist at least one vertex v with e _X(v) = t; while if rad_X G t s _X, then there are at least two such vertices. The X-center C _X(G) is the subgraph induced by those vertices v with e _X(v) = rad_X G and the X-periphery P _X (G) is the subgraph induced by those vertices v with e _X(G) = diam_X G. It is shown that for k-stratified graphs H ₁, H ₂,..., H _k with colors X ₁, X ₂,..., X _k and a positive integer n, there exists a k-stratified graph G such that C X _i(G) H _i (1 ; i ; k1) and for i j. Those k-stratified graphs that are peripheries of k-stratified graphs are characterized. Other distance-related topics in stratified graphs are also discussed.     

A wavelike functional equation of Pexider type

Summary. Let (G, +) and (H, +) be abelian groups such that the equation 2u = v 2u = v is solvable in both G and H. It is shown that if f₁, f₂, f₃, f₄, : G ×G ? H f_1, f_2, f_3, f_4, : G \times G \longrightarrow H satisfy the functional equation f₁(x + t, y + s) + f₂(x - t, y - s) = f₃(x + s, y - t) + f₄(x - s, y + t) for all x, y, s, t ? G x, y, s, t \in G , then f₁, f₂, f₃, and f₄ are given by f₁ = w + h, f₂ = w - h, f₃ = w + k, f₄ = w - k where w : G ×G ? H w : G \times G \longrightarrow H is an arbitrary solution of f (x + t, y + s) + f (x - t, y - s) = f (x + s, y - t) + f (x - s, y + t) for all x, y, s, t ? G x, y, s, t \in G , and h, k : G ×G ? H h, k : G \times G \longrightarrow H are arbitrary solutions of D_y,t³g(x,y) = 0 \Delta_{y,t}^{3}g(x,y) = 0 and D_x,t³g(x,y) = 0 \Delta_{x,t}^{3}g(x,y) = 0 for all x, y, s, t ? G x, y, s, t \in G .     

Long cycles passing through a specified path in a graph

For a graph G and an integer k ≥ 1, let ς_k(G) = d_G(v_i): {v₁, …, v_k} is an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, ς₂(G) − s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a (k + s − 1)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, − s} passing through any path of length s. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998     

Cycles in Partially Square Graphs

. In this work we consider finite undirected simple graphs. If G=(V,E) is a graph we denote by α(G) the stability number of G. For any vertex x let N[x] be the union of x and the neighborhood N(x). For each pair of vertices ab of G we associate the set J(a,b) as follows. J(a,b)={u∈N[a]∩N[b]∣N(u)⊆N[a]∪N[b]}. Given a graph G, its partially squareG ^* is the graph obtained by adding an edge uv for each pair u,v of vertices of G at distance 2 whenever J(u,v) is not empty. In the case G is a claw-free graph, G ^* is equal to G ². If G is k-connected, we cover the vertices of G by at most ⌈α(G ^*)/k⌉ cycles, where α(G ^*) is the stability number of the partially square graph of G. On the other hand we consider in G ^* conditions on the sum of the degrees. Let G be any 2-connected graph and t be any integer (t≥2). If ∑ _{x ∈ S} deg _G (x)≥|G|, for every t-stable set S⊆V(G) of G ^* then the vertex set of G can be covered with t−1 cycles. Different corollaries on covering by paths are given. Received: January 22, 1997 Final version received: February 15, 2000     

Rates for approximation of unbounded functions by positive linear operators

Let g_a(t) and g_b(t) be two positive, strictly convex and continuously differentiable functions on an interval (a, b) (−∞ a < b ∞), and let {L_n} be a sequence of linear positive operators, each with domain containing 1, t, g_a(t), and g_b(t). If L_n(ƒ; x) converges to ƒ(x) uniformly on a compact subset of (a, b) for the test functions ƒ(t) = 1, t, g_a(t), g_b(t), then so does every ƒ ε C(a, b) satisfying ƒ(t) = O(g_a(t)) (t → a⁺) and ƒ(t) = O(g_b(t)) (t → b⁻). We estimate the convergence rate of L_nƒ in terms of the rates for the test functions and the moduli of continuity of ƒ and ƒ′.     

A degree condition for a graph to have [a,b]-factors

Let G be a graph of order n, and let a and b be integers such that 1 ≤ a < b. We show that G has an [a, b]-factor if δ(G) ≥ a, n ≥ 2a + b + and max {d_G(u), d_G(v) ≥ for any two nonadjacent vertices u and v in G. This result is best possible, and it is an extension of T. Iida and T. Nishimura's results (T. Iida and T. Nishimura, An Ore-type condition for the existence of k-factors in graphs, Graphs and Combinat. 7 (1991), 353–361; T. Nishimura, A degree condition for the existence of k-factors, J. Graph Theory 16 (1992), 141–151). about the existence of a k-factor. As an immediate consequence, it shows that a conjecture of M. Kano (M. Kano, Some current results and problems on factors of graphs, Proc. 3rd China–USA International Conference on Graph Theory and Its Application, Beijing (1993). about connected [a, b]-factors is incorrect. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 1–6, 1998     

Sets in Abelian groups with distinct sums of pairs

A subset S={s₁,…,sk} of an Abelian group G is called an St-set of size k if all sums of t different elements in S are distinct. Let s(G) denote the cardinality of the largest S₂-set in G. Let v(k) denote the order of the smallest Abelian group for which s(G)?k. In this article, bounds for s(G) are developed and v(k) is determined for k?15 by computing s(G) for Abelian groups of order up to 183 using exhaustive backtrack search with isomorph rejection.     

On the Oscillation of Second Order Neutral Differential Equations of Emden-Fowler Type

Some oscillation criteria are established by the averaging technique for the second order neutral delay differential equation of Emden-Fowler type (a(t)x￠(t))￠+q₁(t)| y(t-s₁)|^a sgn y(t-s₁) +q₂(t)| y(t-s₂)|^b sgn y(t-s₂)=0,    t 3 t₀,(a(t)x'(t))'+q_1(t)| y(t-\sigma_1)|^{\alpha}\,{\rm sgn}\,y(t-\sigma_1) +q_2(t)| y(t-\sigma_2)|^{\beta}\,{\rm sgn}\,y(t-\sigma_2)=0,\quad t \ge t_0, where x(t) = y(t) + p(t)y(t − τ), τ, σ₁ and σ₂ are nonnegative constants, α > 0, β > 0, and a, p, q ₁, q₂ ? C([t₀, ￥), \Bbb R)q_2\in C([t_0, \infty), {\Bbb R}) . The results of this paper extend and improve some known results. In particular, two interesting examples that point out the importance of our theorems are also included.     

Integrability of certain solutions of differential equations

Let L=P_o(d/d_t)ⁿ+P₁(d/d_t)^n–1+...+P_n denote a formally self-adjoint differential expression on an open intervalI=(a, b) (–a. Here the P_k are complex valued with (n — k) continuous derivatives onI, and P₀(t) 0 onI. We discuss integrability of functions which are adjoint to certain fundamental solutions ofLy=y, and a related consequence.     

On a nonconvolution Volterra resolvent

Under fairly weak assumptions, the solutions of the system of Volterra equations x(t) = ∝₀^ta(t, s) x(s) ds + f(t), t > 0, can be written in the form x(t) = f(t) + ∝₀^tr(t, s) f(s) ds, t > 0, where r is the resolvent of a, i.e., the solution of the equation r(t, s) = a(t, s) + ∝₀^ta(t, v) r(v, s)dv, 0 < s < t. Conditions on a are given which imply that the resolvent operator f ∝₀^tr(t, s) f(s) ds maps a weighted L¹ space continuously into another weighted L¹ space, and a weighted L^∞ space into another weighted L^∞ space. Our main theorem is used to study the asymptotic behavior of two differential delay equations.     

Some Bistar Bipartite Ramsey Numbers

For bipartite graphs G ₁, G ₂, . . . ,G _k , the bipartite Ramsey number b(G ₁, G ₂, . . . , G _k ) is the least positive integer b so that any colouring of the edges of K _b,b with k colours will result in a copy of G _i in the ith colour for some i. A tree of diameter three is called a bistar, and will be denoted by B(s, t), where s ≥ 2 and t ≥ 2 are the degrees of the two support vertices. In this paper we will obtain some exact values for b(B(s, t), B(s, t)) and b(B(s, s), B(s, s)). Furtermore, we will show that if k colours are used, with k ≥ 2 and s ≥ 2, then \({b_{k}(B(s, s)) \leq \lceil k(s - 1) + \sqrt{(s - 1)^{2}(k^{2} - k) - k(2s - 4)} \rceil}\) . Finally, we show that for s ≥ 3 and k ≥ 2, the Ramsey number \({r_{k}(B(s, s)) \leq \lceil 2k(s - 1)+ \frac{1}{2} + \frac{1}{2} \sqrt{(4k(s - 1) + 1)^{2} - 8k(2s^{2} - s - 2)} \rceil}\) .     

A New Approach to the Creation and Propagation of Exponential Moments in the Boltzmann Equation

We study the creation and propagation of exponential moments of solutions to the spatially homogeneous d-dimensional Boltzmann equation. In particular, when the collision kernel is of the form |v ? v _*|^β b(cos (θ)) for β ∈ (0, 2] with cos (θ) = |v ? v _*|^?1(v ? v _*)·σ and σ ∈ 𝕊 ^d?1, and assuming the classical cut-off condition b(cos (θ)) integrable in 𝕊 ^d?1, we prove that there exists a > 0 such that moments with weight exp (amin {t, 1}|v|^β) are finite for t > 0, where a only depends on the collision kernel and the initial mass and energy. We propose a novel method of proof based on a single differential inequality for the exponential moment with time-dependent coefficients.     

Asymptotic distributions of regression and autoregression coefficients with martingale difference disturbances

In this paper a form of the Lindeberg condition appropriate for martingale differences is used to obtain asymptotic normality of statistics for regression and autoregression. The regression model is y_t = Bz_t + v_t. The unobserved error sequence {v_t} is a sequence of martingale differences with conditional covariance matrices {Σ_t} and satisfying sup_{t=1,…, n} {v′_tv_tI(v′_tv_t>a) |z_t, v_t−1, z_t−1, …} 0 as a → ∞. The sample covariance of the independent variables z₁, …, z_n, is assumed to have a probability limit M, constant and nonsingular; max_t=1,…,nz′_tz_t/n 0. If (1/n)Σ_t=1ⁿΣ_t Σ, constant, then √nvec( _n−B) N(0,M⁻¹Σ) and _n Σ. The autoregression model is x_t = Bx_{t − 1} + v_t with the maximum absolute value of the characteristic roots of B less than one, the above conditions on {v_t}, and (1/n)Σ_t=max(r,s)+1(Σ_tv_t−1−rv′_t−1−s) δ_rs(ΣΣ), where δ_rs is the Kronecker delta. Then √nvec( _n−B) N(0,Γ⁻¹Σ), where Γ = Σ_{s = 0}^∞B^sΣ(B′)^s.