共查询到20条相似文献,搜索用时 31 毫秒
1.
Let Gn,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property Ak, if G contains ⌊(k − 1)/2⌋ edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size ⌊n/2⌋. We prove that, for k ≥ 3, there is a constant Ck such that if 2m ≥ Ckn then Ak occurs in Gn,m,k with probability tending to 1 as n → ∞. © 2000 John Wiley & Sons, Inc. J. Graph Theory 34: 42–59, 2000 相似文献
2.
It was proved by Hell and Zhu that, if G is a series‐parallel graph of girth at least 2⌊(3k − 1)/2⌋, then χc(G) ≤ 4k/(2k − 1). In this article, we prove that the girth requirement is sharp, i.e., for any k ≥ 2, there is a series‐parallel graph G of girth 2⌊(3k − 1)/2⌋ − 1 such that χc(G) > 4k/(2k − 1). © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 185–198, 2000 相似文献
3.
Itai Benjamini Carlos Hoppen Eran Ofek Paweł Prałat Nick Wormald 《Journal of Graph Theory》2011,66(2):115-136
A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance dG(u, v) is at least dC(u, v)?e(n). Let ω(n) be any function tending to infinity with n. We consider a random d‐regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n) = logd?1logd?1n+ ω(n) and |C| = 2logd?1n+ O(ω(n)). Along the way, we obtain results on near‐geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. Copyright © 2010 John Wiley & Sons, Ltd. J Graph Theory 66:115‐136, 2011 相似文献
4.
For two nonisomorphic orientations D and D′ of a graph G, the orientation distance do(D,D′) between D and D′ is the minimum number of arcs of D whose directions must be reversed to produce an orientation isomorphic to D′. The orientation distance graph 𝒟o(G) of G has the set 𝒪(G) of pairwise nonisomorphic orientations of G as its vertex set and two vertices D and D′ of 𝒟0(G) are adjacent if and only if do(D,D′) = 1. For a nonempty subset S of 𝒪(G), the orientation distance graph 𝒟0(S) of S is the induced subgraph 〈S〉 of 𝒟o(G). A graph H is an orientation distance graph if there exists a graph G and a set S⊆ 𝒪(G) such that 𝒟o(S) is isomorphic to H. In this case, H is said to be an orientation distance graph with respect to G. This paper deals primarily with orientation distance graphs with respect to paths. For every integer n ≥ 4, it is shown that 𝒟o(Pn) is Hamiltonian if and only if n is even. Also, the orientation distance graph of a path of odd order is bipartite. Furthermore, every tree is an orientation distance graph with respect to some path, as is every cycle, and for n ≥ 3 the clique number of 𝒟o(Pn) is 2 if n is odd and is 3 otherwise. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 230–241, 2001 相似文献
5.
Let G be a connected graph and let eb(G) and λ(G) denote the number of end‐blocks and the maximum number of disjoint 3‐vertex paths Λ in G. We prove the following theorems on claw‐free graphs: (t1) if G is claw‐free and eb(G) ≤ 2 (and in particular, G is 2‐connected) then λ(G) = ⌊| V(G)|/3⌋; (t2) if G is claw‐free and eb(G) ≥ 2 then λ(G) ≥ ⌊(| V(G) | − eb(G) + 2)/3 ⌋; and (t3) if G is claw‐free and Δ*‐free then λ(G) = ⌊| V(G) |/3⌋ (here Δ* is a graph obtained from a triangle Δ by attaching to each vertex a new dangling edge). We also give the following sufficient condition for a graph to have a Λ‐factor: Let n and p be integers, 1 ≤ p ≤ n − 2, G a 2‐connected graph, and |V(G)| = 3n. Suppose that G − S has a Λ‐factor for every S ⊆ V(G) such that |S| = 3p and both V(G) − S and S induce connected subgraphs in G. Then G has a Λ‐factor. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 175–197, 2001 相似文献
6.
Julia Bttcher Jie Han Yoshiharu Kohayakawa Richard Montgomery Olaf Parczyk Yury Person 《Random Structures and Algorithms》2019,55(4):854-864
We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph Gα on n vertices with δ(Gα) ≥ αn for α > 0 and we add to it the binomial random graph G(n,C/n), then with high probability the graph Gα∪G(n,C/n) contains copies of all spanning trees with maximum degree at most Δ simultaneously, where C depends only on α and Δ. 相似文献
7.
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 相似文献
8.
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 相似文献
9.
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 相似文献
10.
Let Γ be a regular graph with n vertices, diameter D, and d + 1 different eigenvalues λ > λ1 > ··· > λd. In a previous paper, the authors showed that if P(λ) > n − 1, then D ≤ d − 1, where P is the polynomial of degree d − 1 which takes alternating values ± 1 at λ1, …, λd. The graphs satisfying P(λ) = n − 1, called boundary graphs, have shown to deserve some attention because of their rich structure. This paper is devoted to the study of this case and, as a main result, it is shown that those extremal (D = d) boundary graphs where each vertex have maximum eccentricity are, in fact, 2-antipodal distance-regular graphs. The study is carried out by using a new sequence of orthogonal polynomials, whose special properties are shown to be induced by their intrinsic symmetry. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 123–140, 1998 相似文献
11.
12.
Javier Barajas 《Discrete Mathematics》2008,308(8):1355-1365
The distance graph G(D) has the set of integers as vertices and two vertices are adjacent in G(D) if their difference is contained in the set D⊂Z. A conjecture of Zhu states that if the chromatic number of G(D) achieves its maximum value |D|+1 then the graph has a triangle. The conjecture is proven to be true if |D|?3. We prove that the chromatic number of a distance graph with D={a,b,c,d} is five only if either D={1,2,3,4k} or D={a,b,a+b,b-a}. This confirms a stronger version of Zhu's conjecture for |D|=4, namely, if the chromatic number achieves its maximum value then the graph contains K4. 相似文献
13.
If G is a graph on n vertices and r ≥ 2, we let mr(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, E(G). In determining mr(G), we may assume that no two vertices of G have the same neighbor set. For such reducedgraphs G, we prove that mr(G) ≥ log2 (n + r − 1)/r. Furthermore, for each k ≥ 0 and r ≥ 2, there is a unique reduced graph G = G(r, k) with mr(G) = k for which equality holds. We conclude with a short proof of the known eigenvalue bound mr(G) ≥ max{n+ (G, n−(G)/(r − 1)}, and show that equality holds if G = G(r, k). © 1996 John Wiley & Sons, Inc. 相似文献
14.
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 相似文献
15.
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 相似文献
16.
A 1‐factorization of a graph G is a collection of edge‐disjoint perfect matchings whose union is E(G). In this paper, we prove that for any ?>0, an (n,d,λ)‐graph G admits a 1‐factorization provided that n is even, C0 ≤ d ≤ n?1 (where C0=C0(?) is a constant depending only on ?), and λ ≤ d1??. In particular, since (as is well known) a typical random d‐regular graph Gn,d is such a graph, we obtain the existence of a 1‐factorization in a typical Gn,d for all C0 ≤ d ≤ n?1, thereby extending to all possible values of d results obtained by Janson, and independently by Molloy, Robalewska, Robinson, and Wormald for fixed d. Moreover, we also obtain a lower bound for the number of distinct 1‐factorizations of such graphs G, which is better by a factor of 2nd/2 than the previously best known lower bounds, even in the simplest case where G is the complete graph. 相似文献
17.
The matching graph M(G) of a graph G is that graph whose vertices are the maximum matchings in G and where two vertices M1 and M2 of M(G) are adjacent if and only if |M1 − M2| = 1. When M(G) is connected, this graph models a metric space whose metric is defined on the set of maximum matchings in G. Which graphs are matching graphs of some graph is not known in general. We determine several forbidden induced subgraphs of matching graphs and add even cycles to the list of known matching graphs. In another direction, we study the behavior of sequences of iterated matching graphs. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 73–86, 1998 相似文献
18.
A class of antimagic join graphs 总被引:1,自引:0,他引:1
A labeling f of a graph G is a bijection from its edge set E(G) to the set {1, 2, . . . , |E(G)|}, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than K 2 is antimagic. In this paper, we show that if G 1 is an n-vertex graph with minimum degree at least r, and G 2 is an m-vertex graph with maximum degree at most 2r-1 (m ≥ n), then G1 ∨ G2 is antimagic. 相似文献
19.
For a graph property P, the edit distance of a graph G from P, denoted EP(G), is the minimum number of edge modifications (additions or deletions) one needs to apply to G to turn it into a graph satisfying P. What is the furthest graph on n vertices from P and what is the largest possible edit distance from P? Denote this maximal distance by ed(n,P). This question is motivated by algorithmic edge‐modification problems, in which one wishes to find or approximate the value of EP(G) given an input graph G. A monotone graph property is closed under removal of edges and vertices. Trivially, for any monotone property, the largest edit distance is attained by a complete graph. We show that this is a simple instance of a much broader phenomenon. A hereditary graph property is closed under removal of vertices. We prove that for any hereditary graph property P, a random graph with an edge density that depends on P essentially achieves the maximal distance from P, that is: ed(n,P) = EP(G(n,p(P))) + o(n2) with high probability. The proofs combine several tools, including strengthened versions of the Szemerédi regularity lemma, properties of random graphs and probabilistic arguments. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 相似文献
20.
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. 相似文献