共查询到20条相似文献,搜索用时 31 毫秒
1.
For a graph G, we define σ2(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ2(G) ≥ n + k − 1, then for any set of k independent vertices v
1,...,v
k
, G has k vertex-disjoint cycles C
1,..., C
k
of length at most four such that v
i
∈ V(C
i
) for all 1 ≤ i ≤ k. And show if σ2(G) ≥ n + k − 1, then for any set of k independent vertices v
1,...,v
k
, G has k vertex-disjoint cycles C
1,..., C
k
such that v
i
∈ V(C
i
) for all 1 ≤ i ≤ k, V(C
1) ∪...∪ V(C
k
) = V(G), and |C
i
| ≤ 4 for all 1 ≤ i ≤ k − 1.
The condition of degree sum σ2(G) ≥ n + k − 1 is sharp.
Received: December 20, 2006. Final version received: December 12, 2007. 相似文献
2.
Let G=(I
n
,E) be the graph of the n-dimensional cube. Namely, I
n
={0,1}
n
and [x,y]∈E whenever ||x−y||1=1. For A⊆I
n
and x∈A define h
A
(x) =#{y∈I
n
A|[x,y]∈E}, i.e., the number of vertices adjacent to x outside of A. Talagrand, following Margulis, proves that for every set A⊆I
n
of size 2
n−1
we have for a universal constant K independent of n. We prove a related lower bound for graphs: Let G=(V,E) be a graph with . Then , where d(x) is the degree of x. Equality occurs for the clique on k vertices.
Received: January 7, 2000
RID="*"
ID="*" Supported in part by BSF and by the Israeli academy of sciences 相似文献
3.
A tree is called a k-tree if the maximum degree is at most k. We prove the following theorem, by which a closure concept for spanning k-trees of n-connected graphs can be defined. Let k ≥ 2 and n ≥ 1 be integers, and let u and v be a pair of nonadjacent vertices of an n-connected graph G such that deg
G
(u) + deg
G
(v) ≥ |G| − 1 − (k − 2)n, where |G| denotes the order of G. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree. 相似文献
4.
A criterion of normality based on a single holomorphic function 总被引:1,自引:0,他引:1
Let F be a family of functions holomorphic on a domain D ⊂ ℂ Let k ≥ 2 be an integer and let h be a holomorphic function on D, all of whose zeros have multiplicity at most k −1, such that h(z) has no common zeros with any f ∈ F. Assume also that the following two conditions hold for every f ∈ F: (a) f(z) = 0 ⇒ f′(z) = h(z); and (b) f′(z) = h(z) ⇒ |f
(k)(z)| ≤ c, where c is a constant. Then F is normal on D. 相似文献
5.
In this paper we study three-color Ramsey numbers. Let K
i,j
denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G
1, G
2 and G
3, if r(G
1, G
2)≥s(G
3), then r(G
1, G
2, G
3)≥(r(G
1, G
2)−1)(χ(G
3)−1)+s(G
3), where s(G
3) is the chromatic surplus of G
3; (ii) (k+m−2)(n−1)+1≤r(K
1,k
, K
1,m
, K
n
)≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K
k,m
, K
k,m
, K
n
)≤c(n/logn), and r(C
2m
, C
2m
, K
n
)≤c(n/logn)
m/(m−1)
for sufficiently large n.
Received: July 25, 2000 Final version received: July 30, 2002
RID="*"
ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of
education ministry of China, and the foundations of Jiangsu Province
Acknowledgments. The authors are grateful to the referee for his valuable comments.
AMS 2000 MSC: 05C55 相似文献
6.
In 1990 G. T. Chen proved that if G is a 2-connected graph of order n and 2|N(x) ∪ N(y)| + d(x) + d(y) ≥ 2n − 1 for each pair of nonadjacent vertices x, y ∈ V (G), then G is Hamiltonian. In this paper we prove that if G is a 2-connected graph of order n and 2|N(x) ∪ N(y)| + d(x)+d(y) ≥ 2n−1 for each pair of nonadjacent vertices x, y ∈ V (G) such that d(x, y) = 2, then G is Hamiltonian. 相似文献
7.
The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d
G
(x) + d
G
(y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d
G
(u) ≥ k. 相似文献
8.
We assign to each pair of positive integers n and k ⩾ 2 a digraph G(n, k) whose set of vertices is H = {0, 1, ..., n − 1} and for which there is a directed edge from a ∈ H to b ∈ H if a
k
≡ b (mod n). We investigate the structure of G(n, k). In particular, upper bounds are given for the longest cycle in G(n, k). We find subdigraphs of G(n, k), called fundamental constituents of G(n, k), for which all trees attached to cycle vertices are isomorphic. 相似文献
9.
Kewen Zhao 《Monatshefte für Mathematik》2009,20(1):279-293
Let G be a simple graph with n vertices. For any v ? V(G){v \in V(G)} , let N(v)={u ? V(G): uv ? E(G)}{N(v)=\{u \in V(G): uv \in E(G)\}} , NC(G) = min{|N(u) èN(v)|: u, v ? V(G){NC(G)= \min \{|N(u) \cup N(v)|: u, v \in V(G)} and
uv \not ? E(G)}{uv \not \in E(G)\}} , and NC2(G) = min{|N(u) èN(v)|: u, v ? V(G){NC_2(G)= \min\{|N(u) \cup N(v)|: u, v \in V(G)} and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any u, v ? V(G){u, v \in V(G)} , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC
2(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC
2(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC
2(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected. 相似文献
10.
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} . 相似文献
11.
We obtain a new upper bound for the sum Σ
h≤H
Δ
k
(N, h) when 1 ≤ H ≤ N, k ∈ ℕ, k ≥ 3, where Δ
k
(N, h) is the (expected) error term in the asymptotic formula for Σ
N<n≤2N
d
k
(n)d
k
(n + h), and d
k
(n) is the divisor function generated by ζ(s)
k
. When k = 3, the result improves, for H ≥ N
1/2, the bound given in a recent work of Baier, Browning, Marasingha and Zhao, who dealt with the case k = 3. 相似文献
12.
. 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
2.
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 相似文献
13.
Raffaele Mosca 《Graphs and Combinatorics》2001,17(3):517-528
Let G be a graph with n vertices, and denote as γ(G) (as θ(G)) the cardinality of a minimum edge cover (of a minimum clique cover) of G. Let E (let C) be the edge-vertex (the clique-vertex) incidence matrix of G; write then P(E)={x∈ℜ
n
:Ex≤1,x≥0}, P(C)={x∈ℜ
n
:Cx≤1,x≥0}, α
E
(G)=max{1
T
x subject to x∈P(E)}, and α
C
(G)= max{1
T
x subject to x∈P(C)}. In this paper we prove that if α
E
(G)=α
C
(G), then γ(G)=θ(G).
Received: May 20, 1998?Final version received: April 12, 1999 相似文献
14.
Let M be a compact manifold of dimension n, P=P(h) a semiclassical pseudodifferential operator on M, and u=u(h) an L
2 normalized family of functions such that P(h)u(h) is O(h) in L
2(M) as h↓0. Let H⊂M be a compact submanifold of M. In a previous article, the second-named author proved estimates on the L
p
norms, p≥2, of u restricted to H, under the assumption that the u are semiclassically localized and under some natural structural assumptions about the principal symbol of P. These estimates are of the form Ch
−δ(n,k,p) where k=dim H (except for a logarithmic divergence in the case k=n−2, p=2). When H is a hypersurface, i.e., k=n−1, we have δ(n,n−1, 2)=1/4, which is sharp when M is the round n-sphere and H is an equator. 相似文献
15.
For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented.
Received: August 19, 1998 Final version received: May 17, 2000 相似文献
16.
B. Djafari Rouhani H. Khatibzadeh 《Journal of Optimization Theory and Applications》2008,137(2):411-417
Let A be a maximal monotone operator in a real Hilbert space H and let {u
n
} be the sequence in H given by the proximal point algorithm, defined by u
n
=(I+c
n
A)−1(u
n−1−f
n
), ∀
n≥1, with u
0=z, where c
n
>0 and f
n
∈H. We show, among other things, that under suitable conditions, u
n
converges weakly or strongly to a zero of A if and only if lim inf
n→+∞|w
n
|<+∞, where w
n
=(∑
k=1
n
c
k
)−1∑
k=1
n
c
k
u
k
. Our results extend previous results by several authors who obtained similar results by assuming A
−1(0)≠φ. 相似文献
17.
Vincenzo De Filippis 《Proceedings Mathematical Sciences》2010,120(3):285-297
Let R be a prime ring, U the Utumi quotient ring of R, C = Z(U) the extended centroid of R, L a non-central Lie ideal of R, H and G non-zero generalized derivations of R. Suppose that there exists an integer n ≥ 1 such that (H(u)u − uG(u))
n
= 0, for all u ∈ L, then one of the following holds: (1) there exists c ∈ U such that H(x) = xc, G(x) = cx; (2) R satisfies the standard identity s
4 and char (R) = 2; (3) R satisfies s
4 and there exist a, b, c ∈ U, such that H(x) = ax+xc, G(x) = cx+xb and (a − b)
n
= 0. 相似文献
18.
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)!!]. 相似文献
19.
Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s
3(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
3(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 相似文献
20.
A three-valued function f: V → {−1, 0, 1} defined on the vertices of a graph G= (V, E) is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one.
That is, for every υ ∈ V, f(N(υ)) ⩾ 1, where N(υ) consists of every vertex adjacent to υ. The weight of an MTDF is f(V) = Σf(υ), over all vertices υ ∈ V. The minus total domination number of a graph G, denoted γ
t
−(G), equals the minimum weight of an MTDF of G. In this paper, we discuss some properties of minus total domination on a graph G and obtain a few lower bounds for γ
t
−(G). 相似文献