共查询到20条相似文献,搜索用时 31 毫秒
1.
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. 相似文献
2.
S.C Locke 《Journal of Combinatorial Theory, Series B》1982,32(2):206-222
Let G be a k-connected graph where k≥3. It is shown that if G contains a path L of length l then G also contains a cycle of length at least () l. This result is obtained from a constructive proof that G contains 3k2 ? 7k + 4 cycles which together cover every edge of L at least 2k2 ? 6k + 4 times. 相似文献
3.
Cai Mao-cheng 《Discrete Mathematics》1982,41(3):229-234
Let G be a minimally k-connected graph of order n and size e(G).Mader [4] proved that (i) ; (ii) e(G)?k(n?k) if n?3k?2, and the complete bipartite graph Kk,n?k is the only minimally k-connected graph of order; n and size k(n?k) when k?2 and n?3k?1.The purpose of the present paper is to determine all minimally k-connected graphs of low order and maximal size. For each n such that k+1?n?3k?2 we prove and characterize all minimally k-connected graphs of order n and size . 相似文献
4.
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. 相似文献
5.
Alaa E. Hamza 《Journal of Difference Equations and Applications》2013,19(3):233-253
We suppose that M is a closed subspace of l ∞(J, X), the space of all bounded sequences {x(n)} n?J ? X, where J ? {Z+,Z} and X is a complex Banach space. We define the M-spectrum σM (u) of a sequence u ? l ∞(J,X). Certain conditions will be supposed on both M and σM (u) to insure the existence of u ? M. We prove that if u is ergodic, such that σM (u,) is at most countable and, for every λ ? σM (u), the sequence e?iλnu(n) is ergodic, then u ? M. We apply this result to the operator difference equationu(n + 1) = Au(n) + ψ(n), n ? J,and to the infinite order difference equation Σ r k=1 ak (u(n + k) ? u(n)) + Σ s ? Z?(n ? s)u(s) = h(n), n?J, where ψ?l ∞(Z,X) such that ψ| J ? M, A is the generator of a C 0-semigroup of linear bounded operators {T(t)} t>0 on X, h ? M, ? ? l 1(Z) and ak ?C. Certain conditions will be imposed to guarantee the existence of solutions in the class M. 相似文献
6.
We say that H has an odd complete minor of order at least l if there are l vertex disjoint trees in H such that every two of them are joined by an edge, and in addition, all the vertices of trees are two-colored in such a way that the edges within the trees are bichromatic, but the edges between trees are monochromatic. Gerards and Seymour conjectured that if a graph has no odd complete minor of order l, then it is (l ? 1)-colorable. This is substantially stronger than the well-known conjecture of Hadwiger. Recently, Geelen et al. proved that there exists a constant c such that any graph with no odd K k -minor is ck√logk-colorable. However, it is not known if there exists an absolute constant c such that any graph with no odd K k -minor is ck-colorable. Motivated by these facts, in this paper, we shall first prove that, for any k, there exists a constant f(k) such that every (496k + 13)-connected graph with at least f(k) vertices has either an odd complete minor of size at least k or a vertex set X of order at most 8k such that G–X is bipartite. Since any bipartite graph does not contain an odd complete minor of size at least three, the second condition is necessary. This is an analogous result of Böhme et al. We also prove that every graph G on n vertices has an odd complete minor of size at least n/2α(G) ? 1, where α(G) denotes the independence number of G. This is an analogous result of Duchet and Meyniel. We obtain a better result for the case α(G)= 3. 相似文献
7.
For a graph G whose number of edges is divisible by k, let R(G,Zk) denote the minimum integer r such that for every function f: E(Kr) ? Zk there is a copy G1 of G in Kr so that Σe∈E(G1) f(e) = 0 (in Zk). We prove that for every integer k1 R(Kn, Zk) ≤ n + O(k3 log k) provided n is sufficiently large as a function of k and k divides (). If, in addition, k is an odd prime-power then R(Kn, Zk) ≤ n + 2k - 2 and this is tight if k is a prime that divides n. A related result is obtained for hypergraphs. It is further shown that for every graph G on n vertices with an even number of edges R(G,Z2) ≤ n + 2. This estimate is sharp. © 1993 John Wiley & Sons, Inc. 相似文献
8.
The square G2 of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G2) ≤ 7. Kostochka and Woodall conjectured that for every graph, the list‐chromatic number of G2 equals the chromatic number of G2, that is, χl(G2) = χ(G2) for all G. If true, this conjecture (together with Thomassen's result) implies that every planar graph G with Δ(G) = 3 satisfies χl(G2) ≤ 7. We prove that every connected graph (not necessarily planar) with Δ(G) = 3 other than the Petersen graph satisfies χl(G2) ≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 7, then χl(G2) ≤ 7. Dvo?ák, ?krekovski, and Tancer showed that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 10, then χl(G2) ≤6. We improve the girth bound to show that if G is a planar graph with Δ(G) = 3 and g(G) ≥ 9, then χl(G2) ≤ 6. All of our proofs can be easily translated into linear‐time coloring algorithms. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 65–87, 2008 相似文献
9.
John Konvalina 《Journal of Combinatorial Theory, Series A》1981,31(2):101-107
Let f(n, k) denote the number of ways of selecting k objects from n objects arrayed in a line with no two selected having unit separation (i.e., having exactly one object between them). Then, if (where ). If n < 2(k ? 1), then f(n, k) = 0. In addition, f(n, k) satisfies the recurrence relation f(n, k) = f(n ? 1, k) + f(n ? 3, k ? 1) + f(n ? 4, k ? 2). If the objects are arrayed in a circle, and the corresponding number is denoted by g(n, k), then for n > 3, g(n, k) = f(n ? 2, k) + 2f(n ? 5, k ? 1) + 3f(n ? 6, k ? 2). In particular, if n ? 2k + 1 then . 相似文献
10.
Matthias Kriesell 《Journal of Graph Theory》2001,36(1):35-51
A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and 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. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001 相似文献
11.
We define the complete closure number cc(G) of a graph G of order n as the greatest integer k ≤ 2n ? 3 such that the kth Bondy-Chvátal closure Clk(G) is complete, and give some necessary or sufficient conditions for a graph to have cc(G) = k. Similarly, the complete stability cs(P) of a property P defined on all the graphs of order n is the smallest integer k such that if Clk(G) is complete then G satisfies P. For some properties P, we compare cs(P) with the classical stability s(P) of P and show that cs(P) may be far smaller than s(P). © 1993 John Wiley & Sons, Inc. 相似文献
12.
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 相似文献
13.
Li Hao 《Journal of Graph Theory》1989,13(3):313-322
Ore proved in 1960 that if G is a graph of order n and the sum of the degrees of any pair of nonadjacent vertices is at least n, then G has a hamiltonian cycle. In 1986, Li Hao and Zhu Yongjin showed that if n ? 20 and the minimum degree δ is at least 5, then the graph G above contains at least two edge disjoint hamiltonian cycles. The result of this paper is that if n ? 2δ2, then for any 3 ? l1 ? l2 ? ? ? lk ? n, 1 = k = [(δ - 1)/2], such graph has K edge disjoint cycles with lengths l1, l2…lk, respectively. In particular, when l1 = l2 = ? = lk = n and k = [(δ - 1)/2], the graph contains [(δ - 1)/2] edge disjoint hamiltonian cycles. 相似文献
14.
Tao Jiang 《Journal of Graph Theory》2004,46(3):180-182
Given positive integers n and k, let gk(n) denote the maximum number of edges of a graph on n vertices that does not contain a cycle with k chords incident to a vertex on the cycle. Bollobás conjectured as an exercise in [2, p. 398, Problem 13] that there exists a function n(k) such that gk(n) = (k + 1)n ? (k + 1)2 for all n ≥ n(k). Using an old result of Bondy [ 3 ], we prove the conjecture, showing that n(k) ≤ 3 k + 3. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 180–182, 2004 相似文献
15.
An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G) ? Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. If every induced subgraph H of G satisfies the condition |E(H)| ? 2|V(H)|?1, we say that the graph G satisfies Property A. In this article, we prove that if G satisfies Property A, then a′(G) ? Δ + 3. Triangle‐free planar graphs satisfy Property A. We infer that a′(G) ? Δ + 3, if G is a triangle‐free planar graph. Another class of graph which satisfies Property A is 2‐fold graphs (union of two forests). © 2011 Wiley Periodicals, Inc. J Graph Theory 相似文献
16.
A graph G is degree-continuous if the degrees of every two adjacent vertices of G differ by at most 1. A finite nonempty set S of integers is convex if k S for every integer k with min(S)kmax(S). It is shown that for all integers r > 0 and s 0 and a convex set S with min(S) = r and max(S) = r+s, there exists a connected degree-continuous graph G with the degree set S and diameter 2s+2. The minimum order of a degree-continuous graph with a prescribed degree set is studied. Furthermore, it is shown that for every graph G and convex set S of positive integers containing the integer 2, there exists a connected degree-continuous graph H with the degree set S and containing G as an induced subgraph if and only if max(S)(G) and G contains no r-regular component where r = max(S). 相似文献
17.
《Quaestiones Mathematicae》2013,36(4):383-398
Abstract A set B of vertices of a graph G = (V,E) is a k-maximal independent set (kMIS) if B is independent but for all ?-subsets X of B, where ? ? k—1, and all (? + 1)-subsets Y of V—B, the set (B—X) u Y is dependent. A set S of vertices of C is a k-maximal clique (kMc) of G iff S is a kMIS of [Gbar]. Let βk, (G) (wk(G) respectively) denote the smallest cardinality of a kMIS (kMC) of G—obviously βk(G) = wk([Gbar]). For the sequence m1 ? m2 ?…? mn = r of positive integers, necessary and sufficient conditions are found for a graph G to exist such that wk(G) = mk for k = 1,2,…,n and w(G) = r (equivalently, βk(G) = mk for k = 1,2,…,n and β(G) = r). Define sk(?,m) to be the largest integer such that for every graph G with at most sk(?,m) vertices, βk(G) ? ? or wk(G) ? m. Exact values for sk(?,m) if k ≥ 2 and upper and lower bounds for s1(?,m) are de termined. 相似文献
18.
H. J. Broersma J. Den Van Heuvel H. A. Jung H. J. Veldman 《Journal of Graph Theory》1993,17(3):373-385
For a graph G and an integer k, denote by Vk the set {v ∈ V(G) | d(v) ≥ k}. Veldman proved that if G is a 2-connected graph of order n with n ≤ 3k - 2 and |Vk| ≤ k, then G has a cycle containing all vertices of Vk. It is shown that the upper bound k on |Vk| is close to best possible in general. For the special case k = δ(G), it is conjectured that the condition |Vk| ≤ k can be omitted. Using a variation of Woodall's Hopping Lemma, the conjecture is proved under the additional condition that n ≤ 2δ(G) + δ(G) + 1. This result is an almost-generalization of Jackson's Theorem that every 2-connected k-regular graph of order n with n ≤ 3k is hamiltonian. An alternative proof of an extension of Jackson's Theorem is also presented. © 1993 John Wiley & Sons, Inc. 相似文献
19.
Shichi Yamamoto 《Indagationes Mathematicae》1999,10(4):615
In this paper, we study numerical properties of Chern classes of certain covering manifolds. One of the main results is the following: Let ψ : X → Pn be a finite covering of the n-dimensional complex projective space branched along a hypersurface with only simple normal crossings and suppose X is nonsingular. Let ci(X) be the i-th Chern class of X. Then (i) if the canonical divisor KX is numerically effective, then (−1)kck(X) (k ≥ 2) is numerically positive, and (ii) if X is of general type, then (−1)ncil (X) cir, (X) > 0, where il + … + ir = n. Furthermore we show that the same properties hold for certain Kummer coverings. 相似文献
20.
Ke-Ang Fu 《Proceedings Mathematical Sciences》2010,120(5):611-618
Let {X
n
; n ≥ 1} be a sequence of independent and identically distributed random vectors in ℜ
p
with Euclidean norm |·|, and let X
n
(r) = X
m
if |X
m
| is the r-th maximum of {|X
k
|; k ≤ n}. Define S
n
= Σ
k≤n
X
k
and (r)
S
n
− (X
n
(1) + ... + X
n
(r)). In this paper a generalized strong invariance principle for the trimmed sums (r)
S
n
is derived. 相似文献