Mutually Independent Hamiltonian Connectivity of (n, k)-Star Graphs

A graph G is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths and of G from u to v are independent if u = u ₁ = v ₁, v = u _v(G) = v _v(G) , and u _i ≠ v _i for every 1 < i < v(G). A set of hamiltonian paths, {P ₁, P ₂, . . . , P _k }, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A graph is k mutually independent hamiltonian connected if for any two distinct nodes u and v, there are k mutually independent hamiltonian paths from u to v. The mutually independent hamiltonian connectivity of a graph G, IHP(G), is the maximum integer k such that G is k mutually independent hamiltonian connected. Let n and k be any two distinct positive integers with n–k ≥ 2. We use S _n,k to denote the (n, k)-star graph. In this paper, we prove that IHP(S _n,k ) = n–2 except for S _4,2 such that IHP(S _4,2) = 1.      

Hamiltonian paths and cycles in hypertournaments

Given two integers n and k, n ≥ k > 1, a k-hypertournament T on n vertices is a pair (V, A), where V is a set of vertices, |V| = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S of V, A$ contains exactly one of the k! k-tuples whose entries belong to S. A 2-hypertournament is merely an (ordinary) tournament. A path is a sequence v₁a₁v₂v₃···v_t−1v_t of distinct vertices v₁, v₂,⋖, v_t and distinct arcs a₁, ⋖, a_t−1 such that v_i precedes v_t−1 in a, 1 ≤ i ≤ t − 1. A cycle can be defined analogously. A path or cycle containing all vertices of T (as v_i's) is Hamiltonian. T is strong if T has a path from x to y for every choice of distinct x, y ≡ V. We prove that every k-hypertournament on n (k) vertices has a Hamiltonian path (an extension of Redeis theorem on tournaments) and every strong k-hypertournament with n (k + 1) vertices has a Hamiltonian cycle (an extension of Camions theorem on tournaments). Despite the last result, it is shown that the Hamiltonian cycle problem remains polynomial time solvable only for k ≤ 3 and becomes NP-complete for every fixed integer k ≥ 4. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 277–286, 1997     

Alcune osservazioni sui sottogruppi abeliani del gruppoSp(n)·Sp(1)

Sunto Si studiano i sottogruppi abeliani diSp(n)·Sp(1). Viene data una caratterizzazione dei sottogruppi abeliani G diSp(n)·Sp(1) che sono immagini di sottogruppi abeliani del rivestimento universaleSp(n)·Sp(1). In relazione all'azione diSp(n)·Sp(1) su R⁴ⁿ ≡ Qⁿ si determinano i sottogruppi abeliani G per i quali Qⁿ si decompone nella somma diretta di di n sottospazi quaternionali1-dimensionali invarianti per G. Si caratterizzano i sottogruppi abeliani massimali tra quelli del tipo Z_p × … × Z_p (p numero primo). Entrata in Redazione il 21 Luglio 1976.     

3·2 r+1 -Cycle Systems of K n −C n

 In this paper we investigate the necessary and sufficient conditions for the existence of 3 · 2 ^{r +1}-cycle system of K _n – C _n , where C _n is any Hamilton cycle of K _n and r ≥ 0. Received: December 17, 1999 Final version received: July 25, 2000 Present address: 15 Guang Ming 10 St. Sec. 1, Chu-Bei, Hsin-Chu, 302, Taiwan, ROC     

An El-Zahár type condition ensuring path-factors

Let G be a connected graph of order n and suppose that n = n₁ + ··· + n_k where n_i ≥ 2 are integers. The following will be proved: If G has minimum degree at least ⌊ ½n₁⌋ + ··· + ⌊ ½n_k⌋ then G has a spanning subgraph which consists of paths of orders n₁, …, n_k. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 39–42, 1998     

Some Limit Theorems in Geometric Processes

Geometric process (GP) was introduced by Lam[4,5], it is defined as a stochastic process {Xn, n = 1, 2,…} for which there exists a real number a > 0, such that {an-1 Xn, n = 1,2, …} forms a renewal process (RP). In this paper, we study some limit theorems in GP. We first derive the Wald equation for GP and then obtain the limit theorems of the age, residual life and the total life at t for a GP. A general limit theorem for Sn with a > 1 is also studied. Furthermore, we make a comparison between GP and RP, including the comparison of their limit distributions of the age, residual life and the total life at t.     

Degenerate triply nonlinear problems with nonhomogeneous boundary conditions

The paper addresses the existence and uniqueness of entropy solutions for the degenerate triply nonlinear problem: b(v) _t − div α(v, ▽g(v)) = f on Q:= (0, T) × Ω with the initial condition b(v(0, ·)) = b(v ₀) on Ω and the nonhomogeneous boundary condition “v = u” on some part of the boundary (0, T) × ∂Ω”. The function g is continuous locally Lipschitz continuous and has a flat region [A ₁, A ₂,] with A ₁ ≤ 0 ≤ A ₂ so that the problem is of parabolic-hyperbolic type.     

Commutators in model spaces

Let θ be an inner function, let K _θ = H ² ⊖ θH ², and let S_θ : K_θ → S_θ be defined by the formula S_θf = P_θzf, where f ∈ K_θ is the orthogonal projection of H² onto K_θ. Consider the set A of all trace class operators L : K_θ → K_θ, L = ∑(·,u_n)v_n, ∑∥u_n∥∥v_n∥ < ∞ (u_n, v_n ∈ K_θ), such that ∑ū_n v_n ∈ H ₀ ¹ . It is shown that trace class commutators of the form XS_θ − S_θX (where X is a bounded linear operator on K_θ) are dense in A in the trace class norm. Bibliography: 2 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 333, 2006, pp. 54–61.     

Degree sequences of graphs and dominance order

Suppose that the graphical partition H(A) = (a₂¹ ≥ ··· ≥ a_n¹) arises from A = (a₁ ≥ ··· ≥ a_n) by deleting the largest summand a₁ from A and reducing the a₁ largest of the remaining summands by one. Let (a_i+1′ ≥ ··· ≥ a_n′) = H′(A) denote the partition obtained by applying the operator H i times. We prove that the dominance order of partitions is preserved when we switch from A to (a₁ ≥ a₂¹ ≥ ··· ≥ a_i+1′ ≥ ···) =: E(A). This generalizes a recent result by Favaron, Mahéo, and Saclé on the residue of a graph. © 1996 John Wiley & Sons, Inc.     

Construction of Some Optimal Ternary Linear Codes and the Uniqueness of [294, 6, 195; 3]-Codes Meeting the Griesmer Bound

Let n_q(k, d) denote the smallest value of n for which there exists an [n, k, d; q]-code. It is known (cf. (J. Combin. Inform. Syst. Sci.18, 1993, 161–191)) that (1) n₃(6, 195) {294, 295}, n₃(6, 194) {293, 294}, n₃(6, 193) {292, 293}, n₃(6, 192) {290, 291}, n₃(6, 191) {289, 290}, n₃(6, 165) {250, 251} and (2) there is a one-to-one correspondence between the set of all nonequivalent [294, 6, 195; 3]-codes meeting the Griesmer bound and the set of all {v₂ + 2v₃ + v₄, v₁ + 2v₂ + v₃; 5, 3}-minihypers, where v_i = (3ⁱ − 1)/(3 − 1) for any integer i ≥ 0. The purpose of this paper is to show that (1) n₃(6, 195) = 294, n₃(6, 194) = 293, n₃(6, 193) = 292, n₃(6, 192) = 290, n₃(6, 191) = 289, n₃(6, 165) = 250 and (2) a [294, 6, 195; 3]-code is unique up to equivalence using a characterization of the corresponding {v₂ + 2v₃ + v₄, v₁ + 2v₂ + v₃; 5, 3}-minihypers.     

Generalized Gaussian quadrature formulas

Existence and uniqueness of canonical points for best L₁-approximation from an Extended Tchebycheff (ET) system, by Hermite interpolating “polynomials” with free nodes of preassigned multiplicities, are proved. The canonical points are shown to coincide with the nodes of a “generalized Gaussian quadrature formula” of the form (*) which is exact for the ET-system. In (*), ∑_{j = 0}^{v_i − 2} ≡ 0 if v_i = 1, the v_i (> 0), I = 1,…, n, are the multiplicities of the free nodes and v₀0, v_{n + 1} 0 of the boundary points in the L₁-approximation problem, ∑_{i = 0}^{n + 1} v_i is the dimension of the ET-system, and σ is the weight in the L₁-norm.The results generalize results on multiple node Gaussian quadrature formulas (v₁,…, v_n all even in (*)) and their relation to best one-sided L₁-approximation. They also generalize results on the orthogonal signature of a Tchebycheff system (v₀ = v_{n + 1} = 0, v_i = 1, I = 1,…, n, in (*)), and its role in best L₁-approximation. Recent works of the authors were the first to treat Gaussian quadrature formulas and orthogonal signatures in a unified way.     

Random markov processes and uniform martingales

It is shown here that a certain generalization of ann-step Markov chain is equivalent to the uniform convergence of the martingale {P(X ₀|X ₋₁ X ₋₂···X _−n)} _n=1 ^∞ . Ergodic and probabilistic properties of this process are explored. This work was initiated at SUNY/Albany.     

On products of k atoms

Let H be an atomic monoid. For k ? \Bbb Nk \in {\Bbb N} let V_k (H){\cal V}_k (H) denote the set of all m ? \Bbb Nm \in {\Bbb N} with the following property: There exist atoms (irreducible elements) u ₁, …, u _k , v ₁, …, v _m ∈ H with u ₁· … · u _k = v ₁ · … · v _m . We show that for a large class of noetherian domains satisfying some natural finiteness conditions, the sets V_k (H){\cal V}_k (H) are almost arithmetical progressions. Suppose that H is a Krull monoid with finite cyclic class group G such that every class contains a prime (this includes the multiplicative monoids of rings of integers of algebraic number fields). We show that, for every k ? \Bbb Nk \in {\Bbb N}, max V_2k+1 (H) = k |G|+ 1{\cal V}_{2k+1} (H) = k \vert G\vert + 1 which settles Problem 38 in [4].     

Terseness: Minimal Idempotent Generating Sets for K(n,r)

Abstract. Let n and r be positive integers with 1 < r < n and let K(n,r) consist of all transformations on X _n = {1,···,n} having image size less than or equal to r . For 1 < r < n , there exist rank-r elements of K(n,r) which are not the product of two rank-r idempotents. With this limitation in mind, we prove that for fixed r , and for all n large enough relative to r , that there exists a minimal idempotent generating set U of K(n,r) such that all rank-r elements of K(n,r) are contained in U ³ . Moreover, for all n> r>1 , there exists a minimal idempotent generating set W for K(n,r) such that not every rank-r element is contained in W ³ .     

Mean-Field Conditions for Percolation on Finite Graphs

Let {G _n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G _n | = n. Denote by p ^t (v, v) the return probability after t steps of the non-backtracking random walk on G _n . We show that if p ^t (v, v) has quasi-random properties, then critical bond-percolation on G _n behaves as it would on a random graph. More precisely, if $\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}$ then the size of the largest component in p-bond-percolation with ${p =\frac{1+O(n^{-1/3})}{d-1}}Let {G _n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G _n | = n. Denote by p ^t (v, v) the return probability after t steps of the non-backtracking random walk on G _n . We show that if p ^t (v, v) has quasi-random properties, then critical bond-percolation on G _n behaves as it would on a random graph. More precisely, if

lim sup  n n1/3 ?t = 1n1/3 tpt(v,v) < ￥,\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}      16. The Smallest Degree Sum That Yields Potentially Kr＋1 - K3-Graphic Sequences   总被引：6，自引：0，他引：6   Meng-xiao Yin 《应用数学学报(英文版)》2006,22(3):451-456 Let a（Kr,＋1 - K3,n） be the smallest even integer such that each n-term graphic sequence п= （d1,d2,…dn） with term sum σ（п） = d1 ＋ d2 ＋…＋ dn 〉 σ（Kr＋1 -K3,n） has a realization containing Kr＋1 - K3 as a subgraph, where Kr＋1 -K3 is a graph obtained from a complete graph Kr＋1 by deleting three edges which form a triangle. In this paper, we determine the value σ（Kr＋1 - K3,n） for r ≥ 3 and n ≥ 3r＋ 5.      17. Branching random walk with a critical branching part      Harry Kesten 《Journal of Theoretical Probability》1995,8(4):921-962 We consider the branching treeT(n) of the first (n+1) generations of a critical branching process, conditioned on survival till time βn for some fixed β>0 or on extinction occurring at timek n withk n /n→β. We attach to each vertexv of this tree a random variableX(v) and define , where π(0,v) is the unique path in the family tree from its root tov. FinallyM n is the maximal displacement of the branching random walkS(·), that isM n =max{S(v):v∈T(n)}. We show that if theX(v), v∈T(n), are i.i.d. with mean 0, then under some further moment conditionn −1/2 M n converges in distribution. In particular {n −1/2 M n } n⩾1 is a tight family. This is closely related to recent results about Aldous' continuum tree and Le Gall's Brownian snake.      18. Van der corput’s difference theorem      T. Kamae  M. Mendes France 《Israel Journal of Mathematics》1978,31(3-4):335-342 We obtain a sufficient condition for a subsetH of positive integers to satisfy that the equidistribution (mod 1) of the sequences (u n+h − u n; n=1, 2, ···) for allh ∈H implies the equidistribution of (u n). Our condition is satisfied, for example, for the following sets: (1)H={n − m; n ∈ I, m ∈ I, n>m}, whereI is any infinite subset of integers; (2)H={| ψ (n)|; ψ(n)≠0,n ∈ Z}, where ψ is a nonconstant polynomial with integral coefficients having at least one integral zero (modq) for allq=2, 3, ···; (3)H={p+1;p is a prime} andH={p − 1;p is a prime}.      19. A note on the largest eigenvalue of a large dimensional sample covariance matrix      Z. D. Bai  Jack W. Silverstein  Y. Q. Yin 《Journal of multivariate analysis》1988,26(2) Let {vij; i, J = 1, 2, …} be a family of i.i.d. random variables with E(v114) = ∞. For positive integers p, n with p = p(n) and p/n → y > 0 as n → ∞, let Mn = (1/n) Vn VnT , where Vn = (vij)1 ≤ i ≤ p, 1 ≤ j ≤ n, and let λmax(n) denote the largest eigenvalue of Mn. It is shown that a.s. This result verifies the boundedness of E(v114) to be the weakest condition known to assure the almost sure convergence of λmax(n) for a class of sample covariance matrices.      20. Pancyclicity of connected circulant graphs      Z. R. Bogdanowicz 《Journal of Graph Theory》1996,22(2):167-174 The circulant Gn(a1, ⋖, ak), where 0 < a1 < ··· < ak < (n + 1)/2, is defined as the vertex-transitive graph that has vertices i ± a1, ···, i ± ak(mod n) adjacent to each vertex i. In this work we show that the connected circulants of degree at least three contain all even cycles. In addition, we prove that the connected circulants of girth three contain cycles of all lengths. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 17–25, 1997

The Smallest Degree Sum That Yields Potentially Kr＋1 - K3-Graphic Sequences

Let a（Kr,＋1 - K3,n） be the smallest even integer such that each n-term graphic sequence п= （d1,d2,…dn） with term sum σ（п） = d1 ＋ d2 ＋…＋ dn 〉 σ（Kr＋1 -K3,n） has a realization containing Kr＋1 - K3 as a subgraph, where Kr＋1 -K3 is a graph obtained from a complete graph Kr＋1 by deleting three edges which form a triangle. In this paper, we determine the value σ（Kr＋1 - K3,n） for r ≥ 3 and n ≥ 3r＋ 5.     

Branching random walk with a critical branching part

We consider the branching treeT(n) of the first (n+1) generations of a critical branching process, conditioned on survival till time βn for some fixed β>0 or on extinction occurring at timek _n withk _n /n→β. We attach to each vertexv of this tree a random variableX(v) and define , where π(0,v) is the unique path in the family tree from its root tov. FinallyM _n is the maximal displacement of the branching random walkS(·), that isM _n =max{S(v):v∈T(n)}. We show that if theX(v), v∈T(n), are i.i.d. with mean 0, then under some further moment conditionn ^−1/2 M _n converges in distribution. In particular {n ^−1/2 M _n } _n⩾1 is a tight family. This is closely related to recent results about Aldous' continuum tree and Le Gall's Brownian snake.     

Van der corput’s difference theorem

We obtain a sufficient condition for a subsetH of positive integers to satisfy that the equidistribution (mod 1) of the sequences (u _n+h − u _n; n=1, 2, ···) for allh ∈H implies the equidistribution of (u _n). Our condition is satisfied, for example, for the following sets: (1)H={n − m; n ∈ I, m ∈ I, n>m}, whereI is any infinite subset of integers; (2)H={| ψ (n)|; ψ(n)≠0,n ∈ Z}, where ψ is a nonconstant polynomial with integral coefficients having at least one integral zero (modq) for allq=2, 3, ···; (3)H={p+1;p is a prime} andH={p − 1;p is a prime}.     

A note on the largest eigenvalue of a large dimensional sample covariance matrix

Let {v_ij; i, J = 1, 2, …} be a family of i.i.d. random variables with E(v₁₁⁴) = ∞. For positive integers p, n with p = p(n) and p/n → y > 0 as n → ∞, let M_n = (1/n) V_n V_n^T , where V_n = (v_ij)_{1 ≤ i ≤ p, 1 ≤ j ≤ n}, and let λ_max(n) denote the largest eigenvalue of M_n. It is shown that a.s. This result verifies the boundedness of E(v₁₁⁴) to be the weakest condition known to assure the almost sure convergence of λ_max(n) for a class of sample covariance matrices.     

Pancyclicity of connected circulant graphs

The circulant G_n(a₁, ⋖, a_k), where 0 < a₁ < ··· < a_k < (n + 1)/2, is defined as the vertex-transitive graph that has vertices i ± a₁, ···, i ± a_k(mod n) adjacent to each vertex i. In this work we show that the connected circulants of degree at least three contain all even cycles. In addition, we prove that the connected circulants of girth three contain cycles of all lengths. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 17–25, 1997