共查询到20条相似文献,搜索用时 31 毫秒
1.
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 相似文献
2.
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 相似文献
3.
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 相似文献
4.
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 相似文献
5.
Let t(G) be the number of spanning trees of a connected graph G, and let b(G) be the number of bases of the bicircular matroid B(G). In this paper we obtain bounds relating b(G) and t(G), and study in detail the case where G is a complete graph Kn or a complete bipartite graph Kn,m.Received April 25, 2003 相似文献
6.
A classical result of Komlós, Sárközy, and Szemerédi states that every n‐vertex graph with minimum degree at least (1/2 + o(1))n contains every n‐vertex tree with maximum degree . Krivelevich, Kwan, and Sudakov proved that for every n‐vertex graph Gα with minimum degree at least αn for any fixed α > 0 and every n‐vertex tree T with bounded maximum degree, one can still find a copy of T in Gα with high probability after adding O(n) randomly chosen edges to Gα. We extend the latter results to trees with (essentially) unbounded maximum degree; for a given and α > 0, we determine up to a constant factor the number of random edges that we need to add to an arbitrary n‐vertex graph with minimum degree αn in order to guarantee with high probability a copy of any fixed n‐vertex tree with maximum degree at most Δ. 相似文献
7.
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. 相似文献
8.
The critical group C(G) of a graph G is a refinement of the number of spanning trees of the graph and is closely connected with the Laplacian matrix. Let r(G) be the minimum number of generators (i.e., the rank) of the group C(G) and β(G) be the number of independent cycles of G. In this paper, some forbidden induced subgraphs are given for r(G) = n − 3 and all graphs with r(G) = β(G) = n − 3 are characterized. 相似文献
9.
In this paper, we investigate fundamental cycles in a graph G and their relations with graph embeddings. We show that a graph G may be embedded in an orientable surface with genus at least g if and only if for any spanning tree T , there exists a sequence of fundamental cycles C1, C2, . . . , C2g with C2i-1 ∩ C2i≠ф for 1≤ i ≤g. In particular, among β(G) fundamental cycles of any spanning tree T of a graph G, there are exactly 2γM (G) cycles C1, C2, . . . , C2γM (G) such that C2i-1 ∩ C2i≠ф for 1 ≤i≤γM (G), w... 相似文献
10.
A graph G is defined to be semiharmonic if there is a constant μ (necessarily a natural number) such that, for every vertex v, the number of walks of length 3 starting in v equals μdG(v) where dG(v) is the degree of v. We determine all finite semiharmonic trees and monocyclic graphs. 相似文献
11.
12.
Noga Alon 《Random Structures and Algorithms》1990,1(2):175-181
Let C(G) denote the number of spanning trees of a graph G. It is shown that there is a function ?(k) that tends to zero as k tends to infinity such that for every connected, k-regular simple graph G on n vertices C(G) = {k[1 ? δ(G)]}n. where 0 ≤ δ(G) ≤ ?(k). 相似文献
13.
For 0 < p < 1 and q > 0 let Gq(n,p) denote the random graph with vertex set [n]={1,…,n} such that, for each graph G on [n] with e(G) edges and c(G) components, the probability that Gq(n,p)=G is proportional to . The first systematic study of Gq(n,p) was undertaken by 6 , who analyzed the phase transition phenomenon corresponding to the emergence of the giant component. In this paper we describe the structure of Gq(n,p) very close the critical threshold. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 相似文献
14.
Chuan-Min Lee 《Discrete Applied Mathematics》2006,154(3):525-536
In this paper, we show that the clique-transversal number τC(G) and the clique-independence number αC(G) are equal for any distance-hereditary graph G. As a byproduct of proving that τC(G)=αC(G), we give a linear-time algorithm to find a minimum clique-transversal set and a maximum clique-independent set simultaneously for distance-hereditary graphs. 相似文献
15.
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 相似文献
16.
Let G be a bipartite graph, with k|e(G). The zero-sum bipartite Ramsey number B(G, Zk) is the smallest integer t such that in every Zk-coloring of the edges of Kt,t, there is a zero-sum mod k copy of G in Kt,t. In this article we give the first proof that determines B(G, Z2) for all possible bipartite graphs G. In fact, we prove a much more general result from which B(G, Z2) can be deduced: Let G be a (not necessarily connected) bipartite graph, which can be embedded in Kn,n, and let F be a field. A function f : E(Kn,n) → F is called G-stable if every copy of G in Kn,n has the same weight (the weight of a copy is the sum of the values of f on its edges). The set of all G-stable functions, denoted by U(G, Kn,n, F) is a linear space, which is called the Kn,n uniformity space of G over F. We determine U(G, Kn,n, F) and its dimension, for all G, n and F. Utilizing this result in the case F = Z2, we can compute B(G, Z2), for all bipartite graphs G. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 151–166, 1998 相似文献
17.
Johan Jonasson 《Random Structures and Algorithms》2000,16(2):131-142
Consider a simple random walk on a connected graph G=(V, E). Let C(u, v) be the expected time taken for the walk starting at vertex u to reach vertex v and then go back to u again, i.e., the commute time for u and v, and let C(G)=maxu, v∈VC(u, v). Further, let 𝒢(n, m) be the family of connected graphs on n vertices with m edges, , and let 𝒢(n)=∪m𝒢(n, m) be the family of all connected n‐vertex graphs. It is proved that if G∈(n, m) is such that C(G)=maxH∈𝒢(n, m)C(H) then G is either a lollipop graph or a so‐called double‐handled lollipop graph. It is further shown, using this result, that if C(G)=maxH∈𝒢(n)C(H) then G is the full lollipop graph or a full double‐handled lollipop graph with [(2n−1)/3] vertices in the clique unless n≤9 in which case G is the n‐path. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 131–142, 2000 相似文献
18.
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 相似文献
19.
In this work, we obtain good upper bounds for the diameter of any graph in terms of its minimum degree and its order, improving a classical theorem due to Erd¨os, Pach, Pollack and Tuza.We use these bounds in order to study hyperbolic graphs(in the Gromov sense). To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let H(n, δ_0) be the set of graphs G with n vertices and minimum degree δ_0, and J(n, Δ) be the set of graphs G with n vertices and maximum degree Δ. We study the four following extremal problems on graphs: a(n, δ_0) = min{δ(G) | G ∈ H(n, δ_0)}, b(n, δ_0) = max{δ(G) |G ∈ H(n, δ_0)}, α(n, Δ) = min{δ(G) | G ∈ J(n, Δ)} and β(n, Δ) = max{δ(G) | G ∈ J(n, Δ)}. In particular, we obtain bounds for b(n, δ_0) and we compute the precise value of a(n, δ_0), α(n, Δ) andβ(n, Δ) for all values of n, δ_0 and Δ, respectively. 相似文献
20.
Nikolaos Fountoulakis Daniela Kühn Deryk Osthus 《Random Structures and Algorithms》2008,33(2):127-141
Let ccl(G) denote the order of the largest complete minor in a graph G (also called the contraction clique number) and let Gn,p denote a random graph on n vertices with edge probability p. Bollobás, Catlin, and Erd?s (Eur J Combin 1 (1980), 195–199) asymptotically determined ccl(Gn,p) when p is a constant. ?uczak, Pittel and Wierman (Trans Am Math Soc 341 (1994) 721–748) gave bounds on ccl(Gn,p) when p is very close to 1/n, i.e. inside the phase transition. We show that for every ε > 0 there exists a constant C such that whenever C/n < p < 1 ‐ ε then asymptotically almost surely ccl(Gn,p) = (1 ± ε)n/ , where b := 1/(1 ‐ p). If p = C/n for a constant C > 1, then ccl(Gn,p) = Θ( ). This extends the results in (Bollobás, Catlin, and P. Erd?s, Eur J Combin 1 (1980), 195–199) and answers a question of Krivelevich and Sudakov (preprint, 2006). © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 相似文献