共查询到20条相似文献,搜索用时 546 毫秒
1.
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 相似文献
2.
Ingo Schiermeyer 《Journal of Graph Theory》2003,44(4):251-260
The cycle‐complete graph Ramsey number r(Cm, Kn) is the smallest integer N such that every graph G of order N contains a cycle Cm on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erd?s, Faudree, Rousseau and Schelp that r(Cm, Kn) = (m ? 1) (n ? 1) + 1 for all m ≥ n ≥ 3 (except r(C3, K3) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with m ≥ n2 ? 2n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003 相似文献
3.
J. Harant M. Voigt S. Jendrol B. Randerath Z. Ryj
ek I. Schiermeyer 《Journal of Graph Theory》2001,36(3):131-143
Let G be a K1,r ‐free graph (r ≥ 3) on n vertices. We prove that, for any induced path or induced cycle on k vertices in G (k ≥ 2r − 1 or k ≥ 2r, respectively), the degree sum of its vertices is at most (2r − 2)(n − α) where α is the independence number of G. As a corollary we obtain an upper bound on the length of a longest induced path and a longest induced cycle in a K1,r ‐free graph. Stronger bounds are given in the special case of claw‐free graphs (i.e., r = 3). Sharpness examples are also presented. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 131–143, 2001 相似文献
4.
The tree partition number of an r‐edge‐colored graph G, denoted by tr(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t2(K(n1, n2,…, nk)) of the complete k‐partite graph K(n1, n2,…, nk). In particular, we prove that t2(K(n, m)) = ? (m‐2)/2n? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005 相似文献
5.
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 相似文献
6.
Let ??(n, m) denote the class of simple graphs on n vertices and m edges and let G ∈ ?? (n, m). There are many results in graph theory giving conditions under which G contains certain types of subgraphs, such as cycles of given lengths, complete graphs, etc. For example, Turan's theorem gives a sufficient condition for G to contain a Kk + 1 in terms of the number of edges in G. In this paper we prove that, for m = αn2, α > (k - 1)/2k, G contains a Kk + 1, each vertex of which has degree at least f(α)n and determine the best possible f(α). For m = ?n2/4? + 1 we establish that G contains cycles whose vertices have certain minimum degrees. Further, for m = αn2, α > 0 we establish that G contains a subgraph H with δ(H) ≥ f(α, n) and determine the best possible value of f(α, n). 相似文献
7.
Kazuhide Hirohata 《Journal of Graph Theory》1998,29(3):177-184
For a graph G and an integer k ≥ 1, let ςk(G) = dG(vi): {v1, …, vk} is an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, ς2(G) − s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a (k + s − 1)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, − s} passing through any path of length s. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998 相似文献
8.
The average distance μ(G) of a graph G is the average among the distances between all pairs of vertices in G. For n ≥ 2, the average Steiner n-distance μn(G) of a connected graph G is the average Steiner distance over all sets of n vertices in G. It is shown that for a connected weighted graph G, μn(G) ≤ μk(G) + μn+1−k(G) where 2 ≤ k ≤ n − 1. The range for the average Steiner n-distance of a connected graph G in terms of n and |V(G)| is established. Moreover, for a tree T and integer k, 2 ≤ k ≤ n − 1, it is shown that μn(T) ≤ (n/k)μk(T) and the range for μn(T) in terms of n and |V(T)| is established. Two efficient algorithms for finding the average Steiner n-distance of a tree are outlined. © 1996 John Wiley & Sons, Inc. 相似文献
9.
Let S(r) denote a circle of circumference r. The circular consecutive choosability chcc(G) of a graph G is the least real number t such that for any r≥χc(G), if each vertex v is assigned a closed interval L(v) of length t on S(r), then there is a circular r‐coloring f of G such that f(v)∈L(v). We investigate, for a graph, the relations between its circular consecutive choosability and choosability. It is proved that for any positive integer k, if a graph G is k‐choosable, then chcc(G)?k + 1 ? 1/k; moreover, the bound is sharp for k≥3. For k = 2, it is proved that if G is 2‐choosable then chcc(G)?2, while the equality holds if and only if G contains a cycle. In addition, we prove that there exist circular consecutive 2‐choosable graphs which are not 2‐choosable. In particular, it is shown that chcc(G) = 2 holds for all cycles and for K2, n with n≥2. On the other hand, we prove that chcc(G)>2 holds for many generalized theta graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 178‐197, 2011 相似文献
10.
Let fd (G) denote the minimum number of edges that have to be added to a graph G to transform it into a graph of diameter at most d. We prove that for any graph G with maximum degree D and n > n0 (D) vertices, f2(G) = n − D − 1 and f3(G) ≥ n − O(D3). For d ≥ 4, fd (G) depends strongly on the actual structure of G, not only on the maximum degree of G. We prove that the maximum of fd (G) over all connected graphs on n vertices is n/⌊d/2 ⌋ − O(1). As a byproduct, we show that for the n‐cycle Cn, fd (Cn) = n/(2⌊d/2 ⌋ − 1) − O(1) for every d and n, improving earlier estimates of Chung and Garey in certain ranges. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 161–172, 2000 相似文献
11.
Yuan Jinjiang 《Journal of Graph Theory》1998,28(4):203-213
We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows: (1) For every connected IM-extendable graph G with |V(G)| ≥ 4, the girth g(G) ≤ 4. (2) If G is a connected IM-extendable graph, then |E(G)| ≥ ${3\over 2}|V(G)| - 2$; the equality holds if and only if G ≅ T × K2, where T is a tree. (3) The only 3-regular connected IM-extendable graphs are Cn × K2, for n ≥ 3, and C2n(1, n), for n ≥ 2, where C2n(1, n) is the graph with 2n vertices x0, x1, …, x2n−1, such that xixj is an edge of C2n(1, n) if either |i − j| ≡ 1 (mod 2n) or |i − j| ≡ n (mod 2n). © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 203–213, 1998 相似文献
12.
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. 相似文献
13.
Given graphs H1,…, Hk, let f(H1,…, Hk) be the minimum order of a graph G such that for each i, the induced copies of Hi in G cover V(G). We prove constructively that f(H1, H2) ≤ 2(n(H1) + n(H2) − 2); equality holds when H1 = H 2 = Kn. We prove that f(H1, K n) = n + 2√δ(H1)n + O(1) as n → ∞. We also determine f(K1, m −1, K n) exactly. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 180–190, 2000 相似文献
14.
Michael A. Henning 《Quaestiones Mathematicae》2018,41(5):693-706
A set S of vertices in a graph G is a packing if the vertices in S are pairwise at distance at least 3 apart in G. The packing number of G, denoted by ρ(G), is the maximum cardinality of a packing in G. Favaron [Discrete Math. 158 (1996), 287–293] showed that if G is a connected cubic graph of order n different from the Petersen graph, then ρ(G) ≥ n/8. In this paper, we generalize Favaron’s result. We show that for k ≥ 3, if G is a connected k-regular graph of order n that is not a diameter-2 Moore graph, then ρ(G) ≥ n/(k2 ? 1). 相似文献
15.
(3,k)-Factor-Critical Graphs and Toughness 总被引:1,自引:0,他引:1
A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and k≤n−7.
Revised: September 21, 1998 相似文献
16.
A graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. For a nonnegative integer k, a graph G is called a k-edge-deletable IM-extendable graph, if, for every F⊆E(G) with |F|=k, G−F is IM-extendable. In this paper, we characterize the k-edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer k, if G is ak-edge-deletable IM-extendable graph on 2n vertices, then |E(G)|≥(k+2)n; furthermore, the equality holds if and only if either G≅Kk+2,k+2, or k=4r−2 for some integer r≥3 and G≅C5[N2r], where N2r is the empty graph on 2r vertices and C5[N2r] is the graph obtained from C5 by replacing each vertex with a graph isomorphic to N2r. 相似文献
17.
Graph G is a (k, p)‐graph if G does not contain a complete graph on k vertices Kk, nor an independent set of order p. Given a (k, p)‐graph G and a (k, q)‐graph H, such that G and H contain an induced subgraph isomorphic to some Kk?1‐free graph M, we construct a (k, p + q ? 1)‐graph on n(G) + n(H) + n(M) vertices. This implies that R (k, p + q ? 1) ≥ R (k, p) + R (k, q) + n(M) ? 1, where R (s, t) is the classical two‐color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R (s, t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R (4, 15) ≥ 153, R (6, 7) ≥ 111, R (6, 11) ≥ 253, R (7, 12) ≥ 416, and R (8, 13) ≥ 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231–239, 2004 相似文献
18.
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. 相似文献
19.
Let G be a connected graph of order p ≥ 2, with edge-connectivity κ1(G) and minimum degree δ(G). It is shown her ethat in order to obtain the equality κ1(G) = δ(G), it is sufficient that, for each vertex x of minimum degree in G, the vertices in the neighbourhood N(x) of x have sufficiently large degree sum. This result implies a previous result of Chartrand, which required that δ(G) ≥ [p/2]. 相似文献
20.
We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs Gn,p (above the connectivity threshold) and for random regular graphs Gr,r ≥ 3, the graph Γ(t) undergoes a phase transition in the sense of the well‐known ErdJW‐RSAT1100590x.png ‐Renyi phase transition. Thus for t ≤ (1 ‐ ε)t*, there is a unique giant component, plus components of size O(log n), and for t ≥ (1 + ε)t* all components are of size O(log n). For Gn,p and Gr we give the value of t*, and the size of Γ(t). For Gr, we also give the degree sequence of Γ(t), the size of the giant component (if any) of Γ(t) and the number of tree components of Γ(t) of a given size k = O(log n). We also show that for random digraphs Dn,p above the strong connectivity threshold, there is a similar directed phase transition. Thus for t ≤ (1 ‐ ε)t*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for t ≥ (1 + ε)t* all strongly connected components are of size O(log n). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 相似文献