首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 640 毫秒
1.
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 1 = v 1, v = u v(G) = v v(G) , and u i ≠ v i for every 1 < iv(G). A set of hamiltonian paths, {P 1, P 2, . . . , 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 nk ≥ 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.   相似文献   

2.
Given two integers n and k, nk > 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 v1a1v2v3···vt−1vt of distinct vertices v1, v2,⋖, vt and distinct arcs a1, ⋖, at−1 such that vi precedes vt−1 in a, 1 ≤ it − 1. A cycle can be defined analogously. A path or cycle containing all vertices of T (as vi's) is Hamiltonian. T is strong if T has a path from x to y for every choice of distinct x, yV. 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  相似文献   

3.
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 R4n ≡ Qn si determinano i sottogruppi abeliani G per i quali Qn si decompone nella somma diretta di di n sottospazi quaternionali1-dimensionali invarianti per G. Si caratterizzano i sottogruppi abeliani massimali tra quelli del tipo Zp × … × Zp (p numero primo). Entrata in Redazione il 21 Luglio 1976.  相似文献   

4.
 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  相似文献   

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

6.
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.  相似文献   

7.
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 0) 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 1, A 2,] with A 1 ≤ 0 ≤ A 2 so that the problem is of parabolic-hyperbolic type.  相似文献   

8.
Let θ be an inner function, let K θ = H 2θH 2, and let Sθ : Kθ → Sθ be defined by the formula Sθf = Pθzf, where f ∈ Kθ is the orthogonal projection of H2 onto Kθ. Consider the set A of all trace class operators L : Kθ → Kθ, L = ∑(·,un)vn, ∑∥un∥∥vn∥ < ∞ (un, vn ∈ Kθ), such that ∑ūn vnH 0 1 . 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.  相似文献   

9.
Let nq(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) n3(6, 195) {294, 295}, n3(6, 194) {293, 294}, n3(6, 193) {292, 293}, n3(6, 192) {290, 291}, n3(6, 191) {289, 290}, n3(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 {v2 + 2v3 + v4, v1 + 2v2 + v3; 5, 3}-minihypers, where vi = (3i − 1)/(3 − 1) for any integer i ≥ 0. The purpose of this paper is to show that (1) n3(6, 195) = 294, n3(6, 194) = 293, n3(6, 193) = 292, n3(6, 192) = 290, n3(6, 191) = 289, n3(6, 165) = 250 and (2) a [294, 6, 195; 3]-code is unique up to equivalence using a characterization of the corresponding {v2 + 2v3 + v4, v1 + 2v2 + v3; 5, 3}-minihypers.  相似文献   

10.
Suppose that the graphical partition H(A) = (a21 ≥ ··· ≥ an1) arises from A = (a1 ≥ ··· ≥ an) by deleting the largest summand a1 from A and reducing the a1 largest of the remaining summands by one. Let (ai+1′ ≥ ··· ≥ an′) = 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 (a1a21 ≥ ··· ≥ ai+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.  相似文献   

11.
Existence and uniqueness of canonical points for best L1-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 = 0vi − 2 ≡ 0 if vi = 1, the vi (> 0), I = 1,…, n, are the multiplicities of the free nodes and v00, vn + 1 0 of the boundary points in the L1-approximation problem, ∑i = 0n + 1 vi is the dimension of the ET-system, and σ is the weight in the L1-norm.The results generalize results on multiple node Gaussian quadrature formulas (v1,…, vn all even in (*)) and their relation to best one-sided L1-approximation. They also generalize results on the orthogonal signature of a Tchebycheff system (v0 = vn + 1 = 0, vi = 1, I = 1,…, n, in (*)), and its role in best L1-approximation. Recent works of the authors were the first to treat Gaussian quadrature formulas and orthogonal signatures in a unified way.  相似文献   

12.
It is shown here that a certain generalization of ann-step Markov chain is equivalent to the uniform convergence of the martingale {P(X 0|X −1 X −2···X −n)} n=1 . Ergodic and probabilistic properties of this process are explored. This work was initiated at SUNY/Albany.  相似文献   

13.
Let H be an atomic monoid. For k ? \Bbb Nk \in {\Bbb N} let Vk (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 1, …, u k , v 1, …, v m H with u 1· … · u k = v 1 · … · v m . We show that for a large class of noetherian domains satisfying some natural finiteness conditions, the sets Vk (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 V2k+1 (H) = k |G|+ 1{\cal V}_{2k+1} (H) = k \vert G\vert + 1 which settles Problem 38 in [4].  相似文献   

14.
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 ,}  相似文献   

15.
McFadden  Seif 《Semigroup Forum》2008,67(1):31-36
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 3 . 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 3 .  相似文献   

16.
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.
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.
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/ny > 0 as n → ∞, let Mn = (1/n) Vn VnT , where Vn = (vij)1 ≤ ip, 1 ≤ jn, 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.  相似文献   

19.
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 allhH 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}.  相似文献   

20.
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  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号