共查询到20条相似文献,搜索用时 31 毫秒
1.
A graph G is a {d, d+k}-graph, if one vertex has degree d+k and the remaining vertices of G have degree d. In the special case of k = 0, the graph G is d-regular. Let k, p ⩾ 0 and d, n ⩾ 1 be integers such that n and p are of the same parity. If G is a connected {d, d+k{-graph of order n without a matching M of size 2|M| = n − p, then we show in this paper the following: If d = 2, then k ⩾ 2(p + 2) and
If d ⩾ 3 is odd and t an integer with 1 ⩽ t ⩽ p + 2, then
If d ⩾ 4 is even, then
The special case k = p = 0 of this result was done by Wallis [6] in 1981, and the case p = 0 was proved by Caccetta and Mardiyono [2] in 1994. Examples show that the given bounds (i)–(viii) are best possible. 相似文献
(i) | n ⩾ k + p + 6. |
(ii) | n ⩾ d + k + 1 for k ⩾ d(p + 2) |
(iii) | n ⩾ d(p + 3) + 2t + 1 for d(p + 2 −t) + t ⩽ k ⩽ d(p + 3 −t) + t − 3 |
(iv) | n ⩾ d(p + 3) + 2p + 7 for k ⩽ p. |
(v) | n ⩾ d + k + 2 − η for k ⩾ d(p + 3) + p + 4 + η |
(vi) | n ⩾ d + k + p + 2 − 2t = d(p + 4) + p + 6 for k = d(p + 3) + 4 + 2t and p ⩾ 1 |
(vii) | n ⩾ d + k + p + 4 for d(p + 2) ⩽ k ⩽ d(p + 3) + 2 |
(viii) | n ⩾ d(p + 3) + p + 4 for k ⩽ d(p + 2) − 2, where 0 ⩽ t ⩽ 1/2p − 1 and η = 0 for even p and 0 ⩽ t ⩽ 1/2(p − 1) and η = 1 for odd p. |
2.
Let G be a graph with n vertices, m edges and a vertex degree sequence (d
1, d
2,..., d
n
), where d
1 ≥ d
2 ≥ ... ≥ d
n
. The spectral radius and the largest Laplacian eigenvalue are denoted by ϱ(G) and μ(G), respectively. We determine the graphs with
and the graphs with d
n
≥ 1 and
We also present some sharp lower bounds for the Laplacian eigenvalues of a connected graph.
The work was supported by National Nature Science Foundation of China (10201009), Guangdong Provincial Natural Science Foundation
of China (021072) and Com2MaC-KOSEF 相似文献
3.
Dr. Matthias Kriesell 《Combinatorica》2006,26(3):277-314
A non-complete graph G is called an (n,k)-graph if it is n-connected but G—X is not (n−|X|+1)-connected for any X ⊂V (G) with |X|≤k. Mader conjectured that for k≥3 the graph K2k+2−(1−factor) is the unique (2k,k)-graph(up to isomorphism).
Here we prove this conjecture. 相似文献
4.
We present results on total domination in a partitioned graph G = (V, E). Let γ
t
(G) denote the total dominating number of G. For a partition , k ≥ 2, of V, let γ
t
(G; V
i
) be the cardinality of a smallest subset of V such that every vertex of V
i
has a neighbour in it and define the following
We summarize known bounds on γ
t
(G) and for graphs with all degrees at least δ we derive the following bounds for f
t
(G; k) and g
t
(G; k).
相似文献
(i) | For δ ≥ 2 and k ≥ 3 we prove f t (G; k) ≤ 11|V|/7 and this inequality is best possible. |
(ii) | for δ ≥ 3 we prove that f t (G; 2) ≤ (5/4 − 1/372)|V|. That inequality may not be best possible, but we conjecture that f t (G; 2) ≤ 7|V|/6 is. |
(iii) | for δ ≥ 3 we prove f t (G; k) ≤ 3|V|/2 and this inequality is best possible. |
(iv) | for δ ≥ 3 the inequality g t (G; k) ≤ 3|V|/4 holds and is best possible. |
5.
The Hadwiger number η(G) of a graph G is the largest integer n for which the complete graph K
n
on n vertices is a minor of G. Hadwiger conjectured that for every graph G, η(G) ≥ χ(G), where χ(G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product of graphs.
As the main result of this paper, we prove that for any two graphs G
1 and G
2 with η(G
1) = h and η(G
2) = l. We show that the above lower bound is asymptotically best possible when h ≥ l. This asymptotically settles a question of Z. Miller (1978).
As consequences of our main result, we show the following:
Alexandr Kostochka: Research of this author is supported in part by NSF grant DMS-0650784 and grant 06-01-00694 of the Russian
Foundation for Basic Research. 相似文献
1. | Let G be a connected graph. Let be the (unique) prime factorization of G. Then G satisfies Hadwiger’s conjecture if k ≥ 2 log log χ(G) + c′, where c′ is a constant. This improves the 2 log χ(G) + 3 bound in [2]. |
2. | Let G 1 and G 2 be two graphs such that χ(G 1) ≥ χ(G 2) ≥ c log1.5(χ(G 1)), where c is a constant. Then satisfies Hadwiger’s conjecture. |
3. | Hadwiger’s conjecture is true for G d (Cartesian product of G taken d times) for every graph G and every d ≥ 2. This settles a question by Chandran and Sivadasan [2]. (They had shown that the Hadiwger’s conjecture is true for G d if d ≥ 3). |
6.
Jiang Chaowei Yang Xiaorong 《高校应用数学学报(英文版)》2007,22(1):87-94
In the case of Zd (d ≥ 2)-the positive d-dimensional lattice points with partial ordering ≤, {Xk,k ∈ Zd } i.i.d. random variables with mean 0, Sn = ∑k≤nXk and Vn2 = ∑j≤nX2j, the precise asymptotics for ∑n1/|n|(log|n|)dP(|Sn/vn|≥ ε√loglog|n|) and ∑n(logn|)δ/|n|(log|n|)d-1 P(|Sn/Vn| ≥ ε√log n), as ε ↘ 0, is established. 相似文献
7.
Let {X
n
,n ≥ 1} be a sequence of i.i.d. random variables. Let M
n
and m
n
denote the first and the second largest maxima. Assume that there are normalizing sequences a
n
> 0, b
n
and a nondegenerate limit distribution G, such that . Assume also that {d
k
,k ≥ 1} are positive weights obeying some mild conditions. Then for x > y we have
when G(y) > 0 (and to zero when G(y) = 0).
相似文献
8.
Suppose thatX andY are real Banach spaces,U ⊂X is an open bounded set star-shaped with respect to some point,n, k ∈ ℕ,k <n, andMn, k (U,Y) is the sharp constant in the Markov type inequality for derivatives of polynomial mappings. It is proved that for anyM ≥M
n,k
(U, Y) there exists a constantB > 0 such that for any functionf ∈C
n
(U, Y) the following inequality holds:
The constantM =M
n−1,k
(U, Y) is best possible in the sense thatM
n−1,k
(U, Y) = infM, where inf is taken over allM such that for someB > 0 the estimate holds for allf ∈C
n
(U, Y).
Translated fromMatematicheskie Zametki, Vol. 63, No. 3, pp. 332–342, March, 1998.
This research was partially supported by the International Science Foundation under grant No. U92000. and by the State Committee
of the Ukraine for Science and Technology. 相似文献
9.
D. R. Heath-Brown 《Proceedings Mathematical Sciences》1994,104(1):13-29
LetF(x) =F[x1,…,xn]∈ℤ[x1,…,xn] be a non-singular form of degree d≥2, and letN(F, X)=#{xεℤ
n
;F(x)=0, |x|⩽X}, where
. It was shown by Fujiwara [4] [Upper bounds for the number of lattice points on hypersurfaces,Number theory and combinatorics, Japan, 1984, (World Scientific Publishing Co., Singapore, 1985)] thatN(F, X)≪X
n−2+2/n
for any fixed formF. It is shown here that the exponent may be reduced ton - 2 + 2/(n + 1), forn ≥ 4, and ton - 3 + 15/(n + 5) forn ≥ 8 andd ≥ 3. It is conjectured that the exponentn - 2 + ε is admissable as soon asn ≥ 3. Thus the conjecture is established forn ≥ 10. The proof uses Deligne’s bounds for exponential sums and for the number of points on hypersurfaces over finite fields.
However a composite modulus is used so that one can apply the ‘q-analogue’ of van der Corput’s AB process.
Dedicated to the memory of Professor K G Ramanathan 相似文献
10.
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
as that of [8], where d(x) is the degree of x, F(x) is the multiset of all open faces σ in the embedding such that the closure contains x (the multiplicity of σ is the number of times that x is visited along ∂σ), and |σ| is the number of sides of edges bounding the face σ. In this paper, we first show that if the
absolute total curvature ∑
x∈V(G) |Φ
G
(x)| is finite, then G has only finite number of vertices of non-vanishing curvature. Next we present a Gauss-Bonnet formula for embedded infinite
graphs with finite number of accumulation points. At last, for a finite simple graph G with 3 ≤ d
G
(x) < ∞ and Φ
G
(x) > 0 for every x ∈ V(G), we have (i) if G is embedded in a projective plane and #(V(G)) = n ≥ 1722, then G is isomorphic to the projective wheel P
n
; (ii) if G is embedded in a sphere and #(V(G)) = n ≥ 3444, then G is isomorphic to the sphere annulus either A
n
or B
n
; and (iii) if d
G
(x) = 5 for all x ∈ V(G), then there are only 49 possible embedded plane graphs and 16 possible embedded projective plane graphs.
Guantao Chen: The second author was partially supported by NSF DMS-0070514 and NSA-H98230-04-1-0300. 相似文献
11.
Z. Füredi 《Graphs and Combinatorics》1985,1(1):51-56
Letn≥k≥1 be integers and letf(n, k) be the smallest integer for which the following holds: If ℱ is a family of subsets of ann-setX with |ℱ|<f(n,k) then for everyk-coloring ofX there existA
B ∈ ℱ,A∈B, A⊂B such thatB-A is monochromatic. Here it is proven that for a fixedk there exist constantsc
k
andd
k
such that
and
ask→∞. The proofs of both the lower and the upper bounds use probabilistic methods. 相似文献
12.
Albertson [2] has introduced the imbalance of an edge e=uv in a graph G as |dG(u)−dG(v)|. If for a graph G of order n and size m the minimum imbalance of an edge of G equals d, then our main result states that with equality if and only if G is isomorphic to We also prove best-possible upper bounds on the number of edges uv of a graph G such that |dG(u)−dG(v)|≥d for some given d. 相似文献
13.
Hong Lin Xiao-feng Guo 《应用数学学报(英文版)》2007,23(1):155-160
Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!]. 相似文献
14.
In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set ${S \subseteq V(G)}In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set S í V(G){S \subseteq V(G)} of cardinality n(k−1) + c + 2, there exists a vertex set X í S{X \subseteq S} of cardinality k such that the degree sum of vertices in X is at least |V(G)| − c −1. Then G has a spanning tree T with maximum degree at most k+éc/nù{k+\lceil c/n\rceil} and ?v ? V(T)max{dT(v)-k,0} £ c{\sum_{v\in V(T)}\max\{d_T(v)-k,0\}\leq c} . 相似文献
15.
Let (X, Xn; n ≥1) be a sequence of i.i.d, random variables taking values in a real separable Hilbert space (H, ||·||) with covariance operator ∑. Set Sn = X1 + X2 + ... + Xn, n≥ 1. We prove that, for b 〉 -1,
lim ε→0 ε^2(b+1) ∞ ∑n=1 (logn)^b/n^3/2 E{||Sn||-σε√nlogn}=σ^-2(b+1)/(2b+3)(b+1) B||Y|^2b+3
holds if EX=0,and E||X||^2(log||x||)^3bv(b+4)〈∞ where Y is a Gaussian random variable taking value in a real separable Hilbert space with mean zero and covariance operator ∑, and σ^2 denotes the largest eigenvalue of ∑. 相似文献
lim ε→0 ε^2(b+1) ∞ ∑n=1 (logn)^b/n^3/2 E{||Sn||-σε√nlogn}=σ^-2(b+1)/(2b+3)(b+1) B||Y|^2b+3
holds if EX=0,and E||X||^2(log||x||)^3bv(b+4)〈∞ where Y is a Gaussian random variable taking value in a real separable Hilbert space with mean zero and covariance operator ∑, and σ^2 denotes the largest eigenvalue of ∑. 相似文献
16.
Let H be any graph. We determine up to an additive constant the minimum degree of a graph G which ensures that G has a perfect H-packing (also called an H-factor). More precisely, let δ(H,n) denote the smallest integer k such that every graph G whose order n is divisible by |H| and with δ(G)≥k contains a perfect H-packing. We show that
.
The value of χ*(H) depends on the relative sizes of the colour classes in the optimal colourings of H and satisfies χ(H)−1<χ*(H)≤χ(H). 相似文献
17.
Chun-Gil Park 《Bulletin of the Brazilian Mathematical Society》2005,36(3):333-362
Let X and Y be vector spaces. It is shown that a mapping f : X → Y satisfies the functional equation
if and only if the mapping f : X → Y is additive, and prove the Cauchy–Rassias stability of the functional equation (‡) in Banach modules over a unital C*-algebra. Let
and
be unital C*-algebras, Poisson C*-algebras, Poisson JC*-algebras or Lie JC*-algebras. As an application, we show that every almost homomorphism h :
→
of
into
is a homomorphism when h((d + 2)nuy) = h((d + 2)nu)h(y) or h((d + 2)nu ∘ y) = h((d + 2)nu) ∘ h(y) for all unitaries u ∈
, all y ∈
, and n = 0, 1, 2, • • • .
Moreover, we prove the Cauchy–Rassias stability of homomorphisms in C*-algebras, Poisson C*-algebras, Poisson JC*-algebras or Lie JC*-algebras.
Supported by Korea Research Foundation Grant KRF-2004-041-C00023. 相似文献
(‡) |
18.
Wel Dong LIU Zheng Yan LIN 《数学学报(英文版)》2008,24(1):59-74
Let {X, X1, X2,...} be a strictly stationaryφ-mixing sequence which satisfies EX = 0,EX^2(log2{X})^2〈∞and φ(n)=O(1/log n)^Tfor some T〉2.Let Sn=∑k=1^nXk and an=O(√n/(log2n)^γ for some γ〉1/2.We prove that limε→√2√ε^2-2∑n=3^∞1/nP(|Sn|≥ε√ESn^2log2n+an)=√2.The results of Gut and Spataru (2000) are special cases of ours. 相似文献
19.
V. G. Krotov 《Ukrainian Mathematical Journal》2010,62(3):441-451
We prove the following statement, which is a quantitative form of the Luzin theorem on C-property: Let (X, d, μ) be a bounded metric space with metric d and regular Borel measure μ that are related to one another by the doubling condition. Then, for any function f measurable on X, there exist a positive increasing function η ∈ Ω (η(+0) = 0 and η(t)t
−a
decreases for a certain a > 0), a nonnegative function g measurable on X, and a set E ⊂ X, μE = 0 , for which
| f(x) - f(y) | \leqslant [ g(x) + g(y) ]h( d( x,y ) ), x,y ? X | / |
E \left| {f(x) - f(y)} \right| \leqslant \left[ {g(x) + g(y)} \right]\eta \left( {d\left( {x,y} \right)} \right),\,x,y \in {{X} \left/ {E} \right.} 相似文献
20.
Let G be an affine algebraic group and let X be an affine algebraic variety. An action G × X → X is called observable if for any G-invariant, proper, closed subset Y of X there is a nonzero invariant f ∈
\Bbbk\Bbbk [X]
G
such that f|
Y
= 0. We characterize this condition geometrically as follows. The action G × X → X is observable if and only if:
|