共查询到20条相似文献,搜索用时 250 毫秒
1.
The Ramsey number r( H, Kn) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r( K2,m, Kn)( m−1+o(1))( n/log n) 2 and r( C2m, Kn) c( n/log n) m/(m−1) for m fixed and n→∞. Also r( K2,n, Kn)=Θ( n3/log 2 n) and
. 相似文献
2.
For a graph G of size m1 and edge-induced subgraphs F and H of size k (1 km), the subgraph H is said to be obtained from F by an edge jump if there exist four distinct vertices u, v, w, and x in G such that uvE( F), wxE( G)− E( F), and H= F− uv+ wx. The minimum number of edge jumps required to transform F into H is the k-jump distance from F to H. For a graph G of size m1 and an integer k with 1 km, the k-jump graph Jk( G) is that graph whose vertices correspond to the edge-induced subgraphs of size k of G and where two vertices of Jk( G) are adjacent if and only if the k-jump distance between the corresponding subgraphs is 1. All connected graphs G for which J2( G) is planar are determined. 相似文献
3.
The following results are obtained. (i) Let p, d, and k be fixed positive integers, and let G be a graph whose vertex set can be partitioned into parts V1, V2,…, Va such that for each i at most d vertices in V1 … Vi have neighbors in Vi+1 and r( Kk, Vi) p | V( G) |, where Vi denotes the subgraph of G induced by Vi. Then there exists a number c depending only on p, d, and k such that r( Kk, G) c | V( G) |. (ii) Let d be a positive integer and let G be a graph in which there is an independent set I V( G) such that each component of G− I has at most d vertices and at most two neighbors in I. Then r( G, G) c | V( G) |, where c is a number depending only on d. As a special case, r( G, G) 6 | V( G) | for a graph G in which all vertices of degree at least three are independent. The constant 6 cannot be replaced by one less than 4. 相似文献
4.
Cubic bridgeless graphs with chromatic index four are called uncolorable. We introduce parameters measuring the uncolorability of those graphs and relate them to each other. For k=2,3, let ck be the maximum size of a k-colorable subgraph of a cubic graph G=( V, E). We consider r3=| E|− c3 and
. We show that on one side r3 and r2 bound each other, but on the other side that the difference between them can be arbitrarily large. We also compare them to the oddness ω of G, the smallest possible number of odd circuits in a 2-factor of G. We construct cyclically 5-edge connected cubic graphs where r3 and ω are arbitrarily far apart, and show that for each 1 c<2 there is a cubic graph such that ω cr3. For k=2,3, let ζ k denote the largest fraction of edges that can be k-colored. We give best possible bounds for these parameters, and relate them to each other. 相似文献
5.
Let G be a graph of order n, and let a and b be integers such that 1 a< b. Let δ( G) be the minimum degree of G. Then we prove that if δ( G)( k−1) a, n( a+ b)( k( a+ b)−2)/ b, and | NG( x1) NG( x2) NG( xk)| an/( a+ b) for any independent subset { x1, x2,…, xk} of V( G), where k2, then G has an [ a, b]-factor. This result is best possible in some sense. 相似文献
6.
For a 1-dependent stationary sequence { Xn} we first show that if u satisfies p1= p1( u)= P( X1> u)0.025 and n>3 is such that 88 np131, then P{max(X1,…,Xn)u}=ν·μn+O{p13(88n(1+124np13)+561)}, n>3, where ν=1−p2+2p3−3p4+p12+6p22−6p1p2,μ=(1+p1−p2+p3−p4+2p12+3p22−5p1p2)−1 with pk=pk(u)=P{min(X1,…,Xk)>u}, k1 and From this result we deduce, for a stationary T-dependent process with a.s. continuous path { Ys}, a similar, in terms of P{max 0skTYs< u}, k=1,2 formula for P{max 0stYsu}, t>3 T and apply this formula to the process Ys= W( s+1)− W( s), s0, where { W( s)} is the Wiener process. We then obtain numerical estimations of the above probabilities. 相似文献
7.
The following problem is considered: given: an undirected planar graph G=( V, E) embedded in
, distinct pairs of vertices { r1, s1},…,{ rk, sk} of G adjacent to the unbounded face, positive integers b1,…, bk and a function
; find: pairwise vertex-disjoint paths P1,…, Pk such that for each i=1,…, k, Pi is a ri− si-path and the sum of the l-length of all edges in Pi is at most bi. It is shown that the problem is NP-hard in the strong sense. A pseudo-polynomial-time algorithm is given for the case of k=2. 相似文献
8.
The Ramsey number R( G1, G2,…, Gk) is the least integer p so that for any k-edge coloring of the complete graph Kp, there is a monochromatic copy of Gi of color i. In this paper, we derive upper bounds of R( G1, G2,…, Gk) for certain graphs Gi. In particular, these bounds show that R(9,9)6588 and R(10,10)23556 improving the previous best bounds of 6625 and 23854. 相似文献
9.
A graph G with n vertices is said to be embeddable (in its complement) if there is an automorphism φ of Kn such that E( G) ∩ E(φ( G))=. It is known that all trees T with n (≥2) vertices and T K1,n−1 are embeddable. We say that G is 1-embeddable if, for every edge e, there is an automorphism φ of Kn such that E( G) ∩ E(φ( G))={ e};and that it is 2-embeddable if,for every pair e1, e2 of edges, there is an automorphism φ of Kn such that E( G) ∩ E(φ( G))={ e1, e2}. We prove here that all trees with n (3) vertices are 1-embeddable; and that all trees T with n (4) vertices and T K1,n−1 are 2-embeddable. In a certain sense, this result is sharp. 相似文献
10.
Suppose G is a graph. The chromatic Ramsey number rc( G) of G is the least integer m such that there exists a graph F of chromatic number m for which the following is true: for any 2-colouring of the edges of F there is a monochromatic subgraph isomorphic to G. Let Mn = min[ rc( G): χ( G) = n]. It was conjectured by Burr et al. (1976) that Mn = ( n − 1) 2 + 1. This conjecture has been confirmed previously for n 4. In this paper, we shall prove that the conjecture is true for n = 5. We shall also improve the upper bounds for M6 and M7. 相似文献
11.
Let Z denote the set of all integers. The integral sum graph of a finite subset S of Z is the graph ( S, E) with vertex set S and edge set E such that for u, vS, uvE if and only if u+ vS. A graph G is called an integral sum graph if it is isomorphic to the integral sum graph of some finite subset S of Z. The integral sum number of a given graph G, denoted by ζ( G), is the smallest number of isolated vertices which when added to G result in an integral sum graph. Let x denote the least integer not less than the real x. In this paper, we (i) determine the value of ζ( Kn− E( Kr)) for r2 n/3−1, (ii) obtain a lower bound for ζ( Kn− E( Kr)) when 2 r<2 n/3−1 and n5, showing by construction that the bound is sharp when r=2, and (iii) determine the value of ζ( Kr,r) for r2. These results provide partial solutions to two problems posed by Harary (Discrete Math. 124 (1994) 101–108). Finally, we furnish a counterexample to a result on the sum number of Kr,s given by Hartsfiedl and Smyth (Graphs and Matrices, R. Rees (Ed.), Marcel, Dekker, New York, 1992, pp. 205–211). 相似文献
12.
We consider the following model Hr( n, p) of random r-uniform hypergraphs. The vertex set consists of two disjoint subsets V of size | V | = n and U of size | U | = ( r − 1) n. Each r-subset of V × ( r−1U) is chosen to be an edge of H ε Hr( n, p) with probability p = p( n), all choices being independent. It is shown that for every 0 < < 1 if P = ( C ln n)/ nr−1 with C = C() sufficiently large, then almost surely every subset V1 V of size | V1 | = (1 − ) n is matchable, that is, there exists a matching M in H such that every vertex of V1 is contained in some edge of M. 相似文献
13.
Gould et al. (Combinatorics, Graph Theory and Algorithms, Vol. 1, 1999, pp. 387–400) considered a variation of the classical Turán-type extremal problems as follows: For a given graph H, determine the smallest even integer σ( H, n) such that every n-term graphic sequence π=( d1, d2,…, dn) with term sum σ( π)= d1+ d2++ dnσ( H, n) has a realization G containing H as a subgraph. In this paper, for given integers k and ℓ, ℓ7 and 3 kℓ, we completely determine the smallest even integer σ( kCℓ, n) such that each n-term graphic sequence π=( d1, d2,…, dn) with term sum σ( π)= d1+ d2++ dnσ( kCℓ, n) has a realization G containing a cycle of length r for each r, krℓ. 相似文献
14.
A random graph Gn( x) is constructed on independent random points U1,…, Un distributed uniformly on [0,1] d, d1, in which two distinct such points are joined by an edge if the l∞-distance between them is at most some prescribed value 0< x<1. The connectivity distance cn, the smallest x for which Gn( x) is connected, is shown to satisfy For d2, the random graph Gn( x) behaves like a d-dimensional version of the random graphs of Erdös and Rényi, despite the fact that its edges are not independent: cn/ dn→1, a.s., as n→∞, where dn is the largest nearest-neighbor link, the smallest x for which Gn( x) has no isolated vertices. 相似文献
15.
Given a graph G and a positive integer d, an L( d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then | f( u)− f( v)| d; if u and v are not adjacent but there is a two-edge path between them, then | f( u)− f( v)|1. The L( d,1)-number of G, λ d( G), is defined as the minimum m such that there is an L( d,1)-labeling f of G with f( V){0,1,2,…, m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ d( G)Δ 2+( d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ d( G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs. 相似文献
16.
Suppose we are given a family of sets
, where S( j) = ∩ ki=1 Hi( j), and suppose each collection of sets Hi( j1),…, Hi( jk+1) has a lower bound under the partial ordering defined by inclusion, then the maximal size of an independent subcollection of
is k. For example, for a fixed collection of half-spaces H1,…, Hk in
, we define
to be the collection of all sets of the form where χ i, I=1,…, k are points in
. Then the maximal size of an independent collection of such sets us k. This leads to a proof of the bound of 2 d due to Rényi et al. (1951) for the maximum size of an independent family of rectangles in
with sides parallel to the coordinate axes, and to a bound of d+1 for the maximum size of an independent family of simplices in
with sides parallel to given hyperplanes H1,…, Hd+1. 相似文献
17.
In a recent paper, D.J. Kleitman and M.E. Saks gave a proof of Huang's conjecture on alphabetic binary trees. Given a set E = {ei}, I = 0, 1, 2, …, m and assigned positive weights to its elements and supposing the elements are indexed such that w(e0) ≤ w(e1) ≤ … ≤w (em), where w(ei) is the weight of ei, we call the following sequence E* a ‘saw-tooth’ sequence E*=(e0,em,e1,…,ej,em−j,…). Huang's conjecture is: E* is the most expensive sequence for alphabetic binary trees. This paper shows that this property is true for the L-restricted alphabetic binary trees, where L is the maximum length of the leaves and log2(m + 1) ≤L≤m. 相似文献
18.
This paper considers a class of nonlinear difference equations Δ3yn + ƒ(n, yn, yn−r) = 0, n N (n0) . A necessary and sufficient condition for the existence of a bounded nonoscillatory solution is given. 相似文献
19.
The chromatic difference sequence cds( G) of a graph G with chromatic number n is defined by cds( G) = ( a(1), a(2),…, a( n)) if the sum of a(1), a(2),…, a( t) is the maximum number of vertices in an induced t-colorable subgraph of G for t = 1, 2,…, n. The Cartesian product of two graphs G and H, denoted by G□ H, has the vertex set V( G□ H = V( G) x V( H) and its edge set is given by ( x1, y1)( x2, y2) ε E( G□ H) if either x1 = x2 and y1 y2 ε E( H) or y1 = y2 and x1x2 ε E( G). We obtained four main results: the cds of the product of bipartite graphs, the cds of the product of graphs with cds being nondrop flat and first-drop flat, the non-increasing theorem for powers of graphs and cds of powers of circulant graphs. 相似文献
20.
A dominating set for a graph G = ( V, E) is a subset of vertices V′ V such that for all v ε V − V′ there exists some u ε V′ for which { v, u} ε E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let m1 ( G, D) denote the number of edges that have neither endpoint in D, and let m2 ( G, D) denote the number of edges that have at least one endpoint in D. We characterize the possible values that the pair ( m1 ( G, D), m2 ( G, D)) can attain for connected graphs having a given domination number. 相似文献
|