共查询到20条相似文献,搜索用时 31 毫秒
1.
We prove the following theorem: For a connected noncomplete graph G, let τ(G): = min{dG(u) + dG(v)|dG(u, v) = 2}. Suppose G is a 3-connected noncomplete graph. Then through each edge of G there passes a cycle of length ≥ min{|V(G)|, τ (G) − 1}. © 1997 John Wiley & Sons, Inc. 相似文献
2.
Let G be a connected claw-free graph on n vertices. Let ς3(G) be the minimum degree sum among triples of independent vertices in G. It is proved that if ς3(G) ≥ n − 3 then G is traceable or else G is one of graphs Gn each of which comprises three disjoint nontrivial complete graphs joined together by three additional edges which induce a triangle K3. Moreover, it is shown that for any integer k ≥ 4 there exists a positive integer ν(k) such that if ς3(G) ≥ n − k, n > ν(k) and G is non-traceable, then G is a factor of a graph Gn. Consequently, the problem HAMILTONIAN PATH restricted to claw-free graphs G = (V, E) (which is known to be NP-complete) has linear time complexity O(|E|) provided that ς3(G) ≥ . This contrasts sharply with known results on NP-completeness among dense graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 75–86, 1998 相似文献
3.
Let h ≥ 6 be an integer, let G be a 3-connected graph with ∣V(G)∣ ≥ h − 1, and let x and z be distinct vertices of G. We show that if for any nonadjacent distinct vertices u and v in V(G) − {x, z}, the sum of the degrees of u and v in G is greater than or equal to h, then for any subset Y of V(G) − {x, z} with ∣Y∣ ≤ 2, G contains a path which has x and z as its endvertices, passes through all vertices in Y, and has length at least h − 2. We also show a similar result for cycles in 2-connected graphs. 相似文献
4.
Zhiquan Hu Feng Tian Bing Wei Yoshimi Egawa Kazuhide Hirohata 《Journal of Graph Theory》2002,39(4):265-282
For a connected noncomplete graph G, let μ(G):=min{max {dG(u), dG(v)}:dG(u, v)=2}. A well‐known theorem of Fan says that every 2‐connected noncomplete graph has a cycle of length at least min{|V(G)|, 2μ(G)}. In this paper, we prove the following Fan‐type theorem: if G is a 3‐connected noncomplete graph, then each pair of distinct vertices of G is joined by a path of length at least min{|V(G)|?1, 2μ(G)?2}. As consequences, we have: (i) if G is a 3‐connected noncomplete graph with , then G is Hamilton‐connected; (ii) if G is a (s+2)‐connected noncomplete graph, where s≥1 is an integer, then through each path of length s of G there passes a cycle of length≥min{|V(G)|, 2μ(G)?s}. Several results known before are generalized and a conjecture of Enomoto, Hirohata, and Ota is proved. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 265–282, 2002 DOI 10.1002/jgt.10028 相似文献
5.
Kazuhide Hirohata 《Graphs and Combinatorics》2000,16(3):269-273
Let G be a 2-connected graph with maximum degree Δ (G)≥d, and let x and y be distinct vertices of G. Let W be a subset of V(G)−{x, y} with cardinality at most d−1. Suppose that max{d
G(u), d
G(v)}≥d for every pair of vertices u and v in V(G)−({x, y}∪W) with d
G(u,v)=2. Then x and y are connected by a path of length at least d−|W|.
Received: February 5, 1998 Revised: April 13, 1998 相似文献
6.
Daniel W. Cranston Anja Pruchnewski Zsolt Tuza Margit Voigt 《Journal of Graph Theory》2012,71(1):18-30
The following question was raised by Bruce Richter. Let G be a planar, 3‐connected graph that is not a complete graph. Denoting by d(v) the degree of vertex v, is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), 6} for all v∈V(G)? More generally, we ask for which pairs (r, k) the following question has an affirmative answer. Let r and k be the integers and let G be a K5‐minor‐free r‐connected graph that is not a Gallai tree (i.e. at least one block of G is neither a complete graph nor an odd cycle). Is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), k} for all v∈V(G)? We investigate this question by considering the components of G[Sk], where Sk: = {v∈V(G)|d(v)8k} is the set of vertices with small degree in G. We are especially interested in the minimum distance d(Sk) in G between the components of G[Sk]. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:18–30, 2012 相似文献
7.
An edge of a 5-connected graph is said to be 5-contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no 5-contractible edge is said to be contraction-critically 5-connected. Let V(G) and V5(G) denote the vertex set of a graph G and the set of degree 5 vertices of G, respectively. We prove that each contraction-critically 5-connected graph G has at least |V(G)|/2 vertices of degree 5. We also show that there is a sequence of contraction-critically 5-connected graphs {Gi} such that limi→∞|V5(Gi)|/|V(Gi)|=1/2. 相似文献
8.
《Journal of Combinatorial Theory, Series B》1987,42(3):371-377
It is shown that for k ≥ 3, every k-connected graph G with girth at least 4 contains an induced cycle C such that G − V(C) is (k − 2)-connected. 相似文献
9.
An independent set S of a graph G is said to be essential if S has a pair of vertices that are distance two apart in G. For SV(G) with S≠, let Δ(S)=max{dG(x)|xS}. We prove the following theorem. Let k2 and let G be a k-connected graph. Suppose that Δ(S)d for every essential independent set S of order k. Then G has a cycle of length at least min{|G|,2d}. This generalizes a result of Fan. 相似文献
10.
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. 相似文献
11.
For a graph G, let σ2(G) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| = n = Σki = 1 ai and σ2(G) ≥ n + k − 1, then for any k vertices v1, v2,…, vk in G, there exist vertex‐disjoint paths P1, P2,…, Pk such that |V(Pi)| = ai and vi is an endvertex of Pi for 1 ≤ i ≤ k. In this paper, we verify the conjecture for the cases where almost all ai ≤ 5, and the cases where k ≤ 3. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 163–169, 2000 相似文献
12.
Mark V. Barovich 《Journal of Graph Theory》2000,33(2):55-65
Let G be a 2‐connected graph, let u and v be distinct vertices in V(G), and let X be a set of at most four vertices lying on a common (u, v)‐path in G. If deg(x) ≥ d for all x ∈ V(G) \ {u, v}, then there is a (u, v)‐path P in G with X ⊂ V(P) and |E(P)| ≥ d. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 55–65, 2000 相似文献
13.
Let G be a planar graph on n vertices, let c(G) denote the length of a longest cycle of G, and let w(G) denote the number of components of G. By a well-known theorem of Tutte, c(G) = n (i.e., G is hamiltonian) if G is 4-connected. Recently, Jackson and Wormald showed that c(G) ≥ βnα for some positive constants β and α ≅ 0.2 if G is 3-connected. Now let G have connectivity 2. Then c(G) may be as small as 4, as with K2,n-2, unless we bound w(G − S) for every subset S of V(G) with |S| = 2. Define ξ(G) as the maximum of w(G − S) taken over all 2-element subsets S ⊆ V(G). We give an asymptotically sharp lower bound for the toughness of G in terms of ξ(G), and we show that c(G) ≥ θ ln n for some positive constant θ depending only on ξ(G). In the proof we use a recent result of Gao and Yu improving Jackson and Wormald's result. Examples show that the lower bound on c(G) is essentially best-possible. © 1996 John Wiley & Sons, Inc. 相似文献
14.
Peter J. Slater 《Journal of Graph Theory》1978,2(3):209-222
For S ? V(G) the S-center and S-centroid of G are defined as the collection of vertices u ∈ V(G) that minimize es(u) = max {d(u, v): v ∈ S} and ds(u) = ∑u∈S d(u, v), respectively. This generalizes the standard definition of center and centroid from the special case of S = V(G). For 1 ? k ?|V(G)| and u ∈ V(G) let rk(u) = max {∑s∈S d(u, s): S ? V(G), |S| = k}. The k-centrum of G, denoted C(G; k), is defined to be the subset of vertices u in G for which rk(u) is a minimum. This also generalizes the standard definitions of center and centroid since C(G; 1) is the center and C(G; |V(G)|) is the centroid. In this paper the structure of these sets for trees is examined. Generalizations of theorems of Jordan and Zelinka are included. 相似文献
15.
It is well known that a graph G of order p ≥ 3 is Hamilton-connected if d(u) + d(v) ≥ p + 1 for each pair of nonadjacent vertices u and v. In this paper we consider connected graphs G of order at least 3 for which d(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| + 1 for any path uwv with uv ∉ E(G), where N(x) denote the neighborhood of a vertex x. We prove that a graph G satisfying this condition has the following properties: (a) For each pair of nonadjacent vertices x, y of G and for each integer k, d(x, y) ≤ k ≤ |V(G)| − 1, there is an x − y path of length k. (b) For each edge xy of G and for each integer k (excepting maybe one k η {3,4}) there is a cycle of length k containing xy. Consequently G is panconnected (and also edge pancyclic) if and only if each edge of G belongs to a triangle and a quadrangle. Our results imply some results of Williamson, Faudree, and Schelp. © 1996 John Wiley & Sons, Inc. 相似文献
16.
A graph G = (V, E) is k-edge-connected if for any subset E′ ⊆ E,|E′| < k, G − E′ is connected. A dk-tree T of a connected graph G = (V, E) is a spanning tree satisfying that ∀v ∈ V, dT(v) ≤ + α, where [·] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a dk-tree, and α = 1 for k = 2, α = 2 for k ≥ 3. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 87–95, 1998 相似文献
17.
A digraph G = (V, E) is primitive if, for some positive integer k, there is a u → v walk of length k for every pair u, v of vertices of V. The minimum such k is called the exponent of G, denoted exp(G). The exponent of a vertex u ∈ V, denoted exp(u), is the least integer k such that there is a u → v walk of length k for each v ∈ V. For a set X ⊆ V, exp(X) is the least integer k such that for each v ∈ V there is a X → v walk of length k, i.e., a u → v walk of length k for some u ∈ X. Let F(G, k) : = max{exp(X) : |X| = k} and F(n, k) : = max{F(G, k) : |V| = n}, where |X| and |V| denote the number of vertices in X and V, respectively. Recently, B. Liu and Q. Li proved F(n, k) = (n − k)(n − 1) + 1 for all 1 ≤ k ≤ n − 1. In this article, for each k, 1 ≤ k ≤ n − 1, we characterize the digraphs G such that F(G, k) = F(n, k), thereby answering a question of R. Brualdi and B. Liu. We also find some new upper bounds on the (ordinary) exponent of G in terms of the maximum outdegree of G, Δ+(G) = max{d+(u) : u ∈ V}, and thus obtain a new refinement of the Wielandt bound (n − 1)2 + 1. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 215–225, 1998 相似文献
18.
Tomoki Yamashita 《Discrete Mathematics》2008,308(24):6584-6587
Let G be a graph. For S⊂V(G), let Δk(S) denote the maximum value of the degree sums of the subsets of S of order k. In this paper, we prove the following two results. (1) Let G be a 2-connected graph. If Δ2(S)≥d for every independent set S of order κ(G)+1, then G has a cycle of length at least min{d,|V(G)|}. (2) Let G be a 2-connected graph and X a subset of V(G). If Δ2(S)≥|V(G)| for every independent set S of order κ(X)+1 in G[X], then G has a cycle that includes every vertex of X. This suggests that the degree sum of nonadjacent two vertices is important for guaranteeing the existence of these cycles. 相似文献
19.
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. 相似文献
20.
A Hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v1, v2, …, vk of k distinct vertices of G, there exists a Hamiltonian cycle that encounters v1, v2, …, vk in this order. Define f(k, n) as the smallest integer m for which any graph on n vertices with minimum degree at least m is a k-ordered Hamiltonian graph. In this article, answering a question of Ng and Schultz, we determine f(k, n) if n is sufficiently large in terms of k. Let g(k, n) = − 1. More precisely, we show that f(k, n) = g(k, n) if n ≥ 11k − 3. Furthermore, we show that f(k, n) ≥ g(k, n) for any n ≥ 2k. Finally we show that f(k, n) > g(k, n) if 2k ≤ n ≤ 3k − 6. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 17–25, 1999 相似文献