共查询到20条相似文献,搜索用时 31 毫秒
1.
Conditions for the existence of a graph with given diameter, connectivity, and ball diversity vector
K. L. Rychkov 《Journal of Applied and Industrial Mathematics》2009,3(1):107-116
Given some arbitrary integers d ≥ 2, ? ? 1 and an integer vector $ \bar \tau Given some arbitrary integers d ≥ 2, ϰ ⩾ 1 and an integer vector
= (τ
0, τ
1, …, τ
d
) with τ
0 ⩾ τ
1 ⩾ … ⩾ τ
d
= 1 and τ
d − 1 ⩾ d
2ϰ + 3, the existence is proved of a graph of diameter d and connectivity ϰ whose ball diversity vector is
. Moreover, the nonexistence is proved of a graph of diameter d with connectivity ϰ and ball diversity vector (τ
0, τ
1, …, τ
d
), where τ
0 < (d − 1)ϰ + 2.
Original Russian Text ? K.L. Rychkov, 2007, published in Diskretnyi Analiz i Issledovanie Operatsii, Ser. 1, 2007, Vol. 14,
No. 4, pp. 43–56. 相似文献
2.
Suppose G is a graph and T is a set of non-negative integers that contains 0. A T-coloring of G is an assignment of a non-negative integer f(x) to each vertex x of G such that |f(x)−f(y)|∉T whenever xy∈E(G). The edge span of a T-coloring−f is the maximum value of |f(x) f(y)| over all edges xy, and the T-edge span of a graph G is the minimum value of the edge span of a T-coloring of G. This paper studies the T-edge span of the dth power C
d
n of the n-cycle C
n for T={0, 1, 2, …, k−1}. In particular, we find the exact value of the T-edge span of C
n
d for n≡0 or (mod d+1), and lower and upper bounds for other cases.
Received: May 13, 1996 Revised: December 8, 1997 相似文献
3.
A. J. W. Hilton 《Journal of Graph Theory》2009,60(4):257-268
For integers d≥0, s≥0, a (d, d+s)‐graph is a graph in which the degrees of all the vertices lie in the set {d, d+1, …, d+s}. For an integer r≥0, an (r, r+1)‐factor of a graph G is a spanning (r, r+1)‐subgraph of G. An (r, r+1)‐factorization of a graph G is the expression of G as the edge‐disjoint union of (r, r+1)‐factors. For integers r, s≥0, t≥1, let f(r, s, t) be the smallest integer such that, for each integer d≥f(r, s, t), each simple (d, d+s) ‐graph has an (r, r+1) ‐factorization with x (r, r+1) ‐factors for at least t different values of x. In this note we evaluate f(r, s, t). © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 257‐268, 2009 相似文献
4.
Jan-Ove Larsson 《Israel Journal of Mathematics》1986,55(2):153-161
Isomorphic embeddings ofl
l
m
intol
∞
n
are studied, and ford(n, k)=inf{‖T ‖ ‖T
−1 ‖;T varies over all isomorphic embeddings ofl
1
[klog2n]
intol
∞
n
we have that lim
n→∞
d(n, k)=γ(k)−1,k>1, whereγ(k) is the solution of (1+γ)ln(1+γ)+(1 −γ)ln(1 −γ)=k
−1ln4.
Here [x] denotes the integer part of the real numberx. 相似文献
5.
Artūras Dubickas 《Monatshefte für Mathematik》2009,137(2):271-284
We prove that, for any real numbers ξ ≠ 0 and ν, the sequence of integer parts [ξ2
n
+ ν], n = 0, 1, 2, . . . , contains infinitely many composite numbers. Moreover, if the number ξ is irrational, then the above sequence
contains infinitely many elements divisible by 2 or 3. The same holds for the sequence [ξ( − 2)
n
+ ν
n
], n = 0, 1, 2, . . . , where ν
0, ν
1, ν
2, . . . all lie in a half open real interval of length 1/3. For this, we show that if a sequence of integers x
1, x
2, x
3, . . . satisfies the recurrence relation x
n+d
= cx
n
+ F(x
n+1, . . . , x
n+d-1) for each n ≥ 1, where c ≠ 0 is an integer,
F(z1,...,zd-1) ? \mathbb Z[z1,...,zd-1],{F(z_1,\dots,z_{d-1}) \in \mathbb {Z}[z_1,\dots,z_{d-1}],} and lim
n→ ∞|x
n
| = ∞, then the number |x
n
| is composite for infinitely many positive integers n. The proofs involve techniques from number theory, linear algebra, combinatorics on words and some kind of symbolic computation
modulo 3. 相似文献
6.
A. Dubickas 《Journal of Mathematical Sciences》2006,137(2):4654-4657
Let g and m be two positive integers, and let F be a polynomial with integer coefficients. We show that the recurrent sequence
x0 = g, xn = x
n−1
n
+ F(n), n = 1, 2, 3,…, is periodic modulo m. Then a special case, with F(z) = 1 and with m = p > 2 being a prime number,
is considered. We show, for instance, that the sequence x0 = 2, xn = x
n−1
n
+ 1, n = 1, 2, 3, …, has infinitely many elements divisible by every prime number p which is less than or equal to 211 except
for three prime numbers p = 23, 47, 167 that do not divide xn. These recurrent sequences are related to the construction of transcendental numbers ζ for which the sequences [ζn!], n = 1, 2, 3, …, have some nice divisibility properties. Bibliography: 18 titles.
Published in Zapiski Nauchnykh Seminarov POMI, Vol. 322, 2005, pp. 76–82. 相似文献
7.
We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x1,…,xn and edge set E that satisfies the property that, for any two integers j and k with j < k, xjxk ? E, d(xi) ? j and d(xk) ? K - 1, we have (1) d(xi) + d(xk ? m if j + k ? n and (2) if j + k < n, either m ? n or d(xj) + d(xk) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively. 相似文献
8.
Let d(n), σ
1(n), and φ(n) stand for the number of positive divisors of n, the sum of the positive divisors of n, and Euler’s function, respectively. For each ν ∈, Z, we obtain asymptotic formulas for the number of integers n ⩽ x for which e
n
= 2
v
r for some odd integer m as well as for the number of integers n ⩽ x for which e
n
= 2
v
r for some odd rational number r. Our method also applies when φ(n) is replaced by σ
1(n), thus, improving upon an earlier result of Bateman, Erdős, Pomerance, and Straus, according to which the set of integers
n such that
is an integer is of density 1/2.
Research supported in part by a grant from NSERC.
Research supported by the Applied Number Theory Research Group of the Hungarian Academy of Science and by a grant from OTKA.
Published in Lietuvos Matematikos Rinkinys, Vol. 46, No. 3, pp. 315–331, July–September, 2006. 相似文献
9.
Yasutsugu Fujita 《Periodica Mathematica Hungarica》2009,59(1):81-98
Let n be a nonzero integer. A set of m distinct positive integers is called a D(n)-m-tuple if the product of any two of them increased by n is a perfect square. Let k be a positive integer. In this paper, we show that if {k
2, k
2 + 1, 4k
2 + 1, d} is a D(−k
2)-quadruple, then d = 1, and that if {k
2 − 1, k
2, 4k
2 − 1, d} is a D(k
2)-quadruple, then d = 8k
2(2k
2 − 1). 相似文献
10.
We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(Kr,r,n) such that every n-term graphic sequence π = (d1,d2,...,dn) with term sum σ(π) = d1 + d2 + ... + dn ≥ σ(Kr,r,n) is potentially Kr,r-graphic, where Kr,r is an r × r complete bipartite graph, i.e. π has a realization G containing Kr,r as its subgraph. In this paper, the values σ(Kr,r,n) for even r and n ≥ 4r2 - r - 6 and for odd r and n ≥ 4r2 + 3r - 8 are determined. 相似文献
11.
Aiming at a simultaneous extension of Khintchine(X,X,m,T)(X,\mathcal{X},\mu,T)
and a set
A ? XA\in\mathcal{X}
of positive measure, the set of integers n such that
A T^2nA T^knA)(A)^k+1-\mu(A{\cap} T^{n}A{\cap} T^{2n}A{\cap} \ldots{\cap} T^{kn}A)>\mu(A)^{k+1}-\epsilon
is syndetic. The size of this set, surprisingly enough, depends on the length (k+1) of the arithmetic progression under consideration. In an ergodic system, for k=2 and k=3, this set is syndetic, while for kòf(x)f(Tnx)f(T2nx)? f(Tknx) dm(x)\int{f(x)f(T^{n}x)f(T^{2n}x){\ldots} f(T^{kn}x) \,d\mu(x)}
, where k and n are positive integers and f is a bounded measurable function. We also derive combinatorial consequences of these results, for example showing that for a set of integers E with upper Banach density d*(E)>0 and for all
{n ? \mathbbZ\colon d*(E?(E+n)?(E+2n)?(E+3n)) > d*(E)4-e}\big\{n\in\mathbb{Z}{\colon} d^*\big(E\cap(E+n)\cap(E+2n)\cap(E+3n)\big) > d^*(E)^4-\epsilon\big\} 相似文献
12.
Basudeb Dhara 《Rendiconti del Circolo Matematico di Palermo》2008,57(3):401-410
Let R be a prime ring of char R ≠ = 2 with center Z(R) and with extended centroid C, d a nonzero derivation of R and f(x
1, ..., x
n
) a nonzero multilinear polynomial over C. Suppose that x
s
d(x)x
t
∈ Z(R) for all x ∈ {d(f(x
1, ..., x
n
))|x
1, ..., x
n
∈ ρ}, where ρ is a nonzero right ideal of R and s ≥ 0, t ≥ 0 are fixed integers. If d(ρ)ρ ≠ = 0, then ρ
C = eRC for some idempotent e in the socle of RC and f(x
1, ..., x
n
)
N
is central-valued in eRCe, where N = s + t + 1.
相似文献
13.
Florian Luca 《Monatshefte für Mathematik》2005,146(3):239-256
In [2], it was shown that if a and b are multiplicatively independent integers and ɛ > 0, then the inequality gcd (an − 1,bn − 1) < exp(ɛn) holds for all but finitely many positive integers n. Here, we generalize the above result. In particular, we show that if f(x),f1(x),g(x),g1(x) are non-zero polynomials with integer coefficients, then for every ɛ > 0, the inequality
holds for all but finitely many positive integers n. 相似文献
14.
Morteza Moniri 《Archive for Mathematical Logic》2002,41(1):101-105
For a classical theory T, ℋ(T) denotes the intuitionistic theory of T-normal (i.e. locally T) Kripke structures. S. Buss has asked for a characterization of the theories in the range of ℋ and raised the particular
question of whether HA is an ℋ-theory. We show that T
i
∈ range(ℋ) iff T
i
= ℋ(T). As a corollary, no fragment of HA extending iΠ
1 belongs to the range of ℋ. A. Visser has already proved that HA is not in the range of H by different methods. We provide more examples of theories not in the range of ℋ. We show PA-normality of once-branching Kripke models of HA + MP, where it is not known whether the same holds if MP is dropped.
Received: 15 August 1999 / Published online: 3 October 2001 相似文献
15.
Hiroshi Nakano 《Graphs and Combinatorics》2001,17(4):707-716
Let Γ be a distance-regular graph of diameter d. The height of Γ is defined by h = max{j∣p
d
d,j
≠ 0}. Let e, f be positive integers such that e < f and e + f≤d, and let d = 2e + s for some positive integer s. We show that if k
e
= k
f
, h≤ 2s and the height h is even, then Γ is an antipodal 2-cover.
Received: October 23, 1997 Final version received: July 31, 2000 相似文献
16.
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.
In this paper, we prove that if a, b and c are pairwise coprime positive integers such that a^2+b^2=c^r,a〉b,a≡3 (mod4),b≡2 (mod4) and c-1 is not a square, thena a^x+b^y=c^z has only the positive integer solution (x, y, z) = (2, 2, r).
Let m and r be positive integers with 2|m and 2 r, define the integers Ur, Vr by (m +√-1)^r=Vr+Ur√-1. If a = |Ur|,b=|Vr|,c = m^2+1 with m ≡ 2 (mod 4),a ≡ 3 (mod 4), and if r 〈 m/√1.5log3(m^2+1)-1, then a^x + b^y = c^z has only the positive integer solution (x,y, z) = (2, 2, r). The argument here is elementary. 相似文献
Let m and r be positive integers with 2|m and 2 r, define the integers Ur, Vr by (m +√-1)^r=Vr+Ur√-1. If a = |Ur|,b=|Vr|,c = m^2+1 with m ≡ 2 (mod 4),a ≡ 3 (mod 4), and if r 〈 m/√1.5log3(m^2+1)-1, then a^x + b^y = c^z has only the positive integer solution (x,y, z) = (2, 2, r). The argument here is elementary. 相似文献
18.
József Beck 《Periodica Mathematica Hungarica》2010,60(2):137-242
We prove that the “quadratic irrational rotation” exhibits a central limit theorem. More precisely, let α be an arbitrary real root of a quadratic equation with integer coefficients; say, α = $
\sqrt 2
$
\sqrt 2
. Given any rational number 0 < x < 1 (say, x = 1/2) and any positive integer n, we count the number of elements of the sequence α, 2α, 3α, …, nα modulo 1 that fall into the subinterval [0, x]. We prove that this counting number satisfies a central limit theorem in the following sense. First, we subtract the “expected
number” nx from the counting number, and study the typical fluctuation of this difference as n runs in a long interval 1 ≤ n ≤ N. Depending on α and x, we may need an extra additive correction of constant times logarithm of N; furthermore, what we always need is a multiplicative correction: division by (another) constant times square root of logarithm
of N. If N is large, the distribution of this renormalized counting number, as n runs in 1 ≤ n ≤ N, is very close to the standard normal distribution (bell shaped curve), and the corresponding error term tends to zero as
N tends to infinity. This is the main result of the paper (see Theorem 1.1). The proof is rather complicated and long; it has
many interesting detours and byproducts. For example, the exact determination of the key constant factors (in the additive
and multiplicative norming), which depend on α and x, requires surprisingly deep algebraic tools such as Dedeking sums, the class number of quadratic fields, and generalized
class number formulas. The crucial property of a quadratic irrational is the periodicity of its continued fraction. Periodicity
means self-similarity, which leads us to Markov chains: our basic probabilistic tool to prove the central limit theorem. We
also use a lot of Fourier analysis. Finally, I just mention one byproduct of this research: we solve an old problem of Hardy
and Littlewood on diophantine sums. 相似文献
19.
Consider a general random walk on ℤd together with an i.i.d. random coloring of ℤd. TheT, T
-1-process is the one where time is indexed by ℤ, and at each unit of time we see the step taken by the walk together with the
color of the newly arrived at location. S. Kalikow proved that ifd = 1 and the random walk is simple, then this process is not Bernoulli. We generalize his result by proving that it is not
Bernoulli ind = 2, Bernoulli but not Weak Bernoulli ind = 3 and 4, and Weak Bernoulli ind ≥ 5. These properties are related to the intersection behavior of the past and the future of simple random walk. We obtain
similar results for general random walks on ℤd, leading to an almost complete classification. For example, ind = 1, if a step of sizex has probability proportional to l/|x|α
(x ⊋ 0), then theT, T
-1-process is not Bernoulli when α ≥2, Bernoulli but not Weak Bernoulli when 3/2 ≤α < 2, and Weak Bernoulli when 1 < α < 3/2.
Research partially carried out while a guest of the Department of Mathematics, Chalmers University of Technology, Sweden in
January 1996.
Research supported by grants from the Swedish Natural Science Research Council and from the Royal Swedish Academy of Sciences. 相似文献
20.
Borka Jadrijević 《Periodica Mathematica Hungarica》2009,58(2):155-180
Let c ≥ 3 be a positive integer such that c, 4c + 1, c − 1 are square-free integers relatively prime in pairs. In this paper we find the minimal index and determine all elements
with minimal index in the bicyclic biquadratic field K = ℚ(√(4c + 1)c, √(c − 1)c).
The author was supported by the Ministry of Science, Education and Sports, Republic of Croatia, grant 037-0372781-2821. 相似文献