首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
For given graphs G1,G2,…,Gk, k≥2, the multicolor Ramsey number, denoted by R(G1,G2,…,Gk), is the smallest integer n such that if we arbitrarily color the edges of a complete graph on n vertices with k colors, there is always a monochromatic copy of Gi colored with i, for some 1≤ik. Let Pk (resp. Ck) be the path (resp. cycle) on k vertices. In the paper we consider the value for numbers of type R(Pi,Pk,Cm) for odd m, km≥3 and when i is odd, and when i is even. In addition, we provide the exact values for Ramsey numbers R(P3,Pk,C4) for all integers k≥3.  相似文献   

2.
The graph Ramsey numberR(G,H) is the smallest integer r such that every 2-coloring of the edges of Kr contains either a red copy of G or a blue copy of H. We find the largest star that can be removed from Kr such that the underlying graph is still forced to have a red G or a blue H. Thus, we introduce the star-critical Ramsey numberr(G,H) as the smallest integer k such that every 2-coloring of the edges of KrK1,r−1−k contains either a red copy of G or a blue copy of H. We find the star-critical Ramsey number for trees versus complete graphs, multiple copies of K2 and K3, and paths versus a 4-cycle. In addition to finding the star-critical Ramsey numbers, the critical graphs are classified for R(Tn,Km), R(nK2,mK2) and R(Pn,C4).  相似文献   

3.
For given graphs G and H, the Ramsey number R(G,H) is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains H. In this paper we investigate the Ramsey number of a disjoint union of graphs . For any natural integer k, we contain a general upper bound, R(kG,H)?R(G,H)+(k-1)|V(G)|. We also show that if m=2n-4, 2n-8 or 2n-6, then R(kSn,Wm)=R(Sn,Wm)+(k-1)n. Furthermore, if |Gi|>(|Gi|-|Gi+1|)(χ(H)-1) and R(Gi,H)=(χ(H)-1)(|Gi|-1)+1, for each i, then .  相似文献   

4.
For a graph G, we define σ2(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ2(G) ≥ n + k − 1, then for any set of k independent vertices v 1,...,v k , G has k vertex-disjoint cycles C 1,..., C k of length at most four such that v i V(C i ) for all 1 ≤ ik. And show if σ2(G) ≥ n + k − 1, then for any set of k independent vertices v 1,...,v k , G has k vertex-disjoint cycles C 1,..., C k such that v i V(C i ) for all 1 ≤ i ≤ k, V(C 1) ∪...∪ V(C k ) = V(G), and |C i | ≤ 4 for all 1 ≤ i ≤ k − 1. The condition of degree sum σ2(G) ≥ n + k − 1 is sharp. Received: December 20, 2006. Final version received: December 12, 2007.  相似文献   

5.
The theory of vertex-disjoint cycles and 2-factor of graphs has important applications in computer science and network communication. For a graph G, let σ 2(G):=min?{d(u)+d(v)|uv ? E(G),uv}. In the paper, the main results of this paper are as follows:
  1. Let k≥2 be an integer and G be a graph of order n≥3k, if σ 2(G)≥n+2k?2, then for any set of k distinct vertices v 1,…,v k , G has k vertex-disjoint cycles C 1,C 2,…,C k of length at most four such that v i V(C i ) for all 1≤ik.
  2. Let k≥1 be an integer and G be a graph of order n≥3k, if σ 2(G)≥n+2k?2, then for any set of k distinct vertices v 1,…,v k , G has k vertex-disjoint cycles C 1,C 2,…,C k such that:
    1. v i V(C i ) for all 1≤ik.
    2. V(C 1)∪???V(C k )=V(G), and
    3. |C i |≤4, 1≤ik?1.
Moreover, the condition on σ 2(G)≥n+2k?2 is sharp.  相似文献   

6.
Given two directed graphs G1, G2, the Ramsey number R(G1,G2) is the smallest integer n such that for any partition {U1,U2} of the arcs of the complete symmetric directed graph K1n, there exists an integer i such that the partial graph generated by Ui contains Gi as a subgraph. In this article, we determine R(P?m,D?n) and R(D?m,D?n) for some values of m and n, where P?m denotes the directed path having m vertices and D?m is obtained from P?m by adding an arc from the initial vertex of P?m to the terminal vertex.  相似文献   

7.
By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then Hn,k, the graph obtained from the star K1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.  相似文献   

8.
We propose a conjecture: for each integer k ≥ 2, there exists N(k) such that if G is a graph of order nN(k) and d(x) + d(y) ≥ n + 2k - 2 for each pair of non-adjacent vertices x and y of G, then for any k independent edges e1, …, ek of G, there exist k vertex-disjoint cycles C1, …, Ck in G such that eiE(Ci) for all i ∈ {1, …, k} and V(C1 ∪ ···∪ Ck) = V(G). If this conjecture is true, the condition on the degrees of G is sharp. We prove this conjecture for the case k = 2 in the paper. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 105–109, 1997  相似文献   

9.
Let k,n be integers with 2≤kn, and let G be a graph of order n. We prove that if max{dG(x),dG(y)}≥(nk+1)/2 for any x,yV(G) with xy and xyE(G), then G has k vertex-disjoint subgraphs H1,…,Hk such that V(H1)∪?∪V(Hk)=V(G) and Hi is a cycle or K1 or K2 for each 1≤ik, unless k=2 and G=C5, or k=3 and G=K1C5.  相似文献   

10.
Letk and s be two positive integers with s≥3. LetG be a graph of ordernsk. Writen =qk + r, 0 ≤rk - 1. Suppose thatG has minimum degree at least (s - l)k. Then G containsk independent cyclesC 1,C 2,...,C k such thatsl(C i ) ≤q for 1 ≤ir arndsl(C i ) ≤q + 1 fork -r <ik, where l(Ci) denotes the length ofC i .  相似文献   

11.
12.
《Discrete Mathematics》2004,274(1-3):125-135
The classical Ramsey number r(m,n) can be defined as the smallest integer p such that in every two-coloring (R,B) of the edges of Kp, β(B)⩾m or β(R)⩾n, where β(G) denotes the independence number of a graph G. We define the upper domination Ramsey number u(m,n) as the smallest integer p such that in every two-coloring (R,B) of the edges of Kp, Γ(B)⩾m or Γ(R)⩾n, where Γ(G) is the maximum cardinality of a minimal dominating set of a graph G. The mixed domination Ramsey number v(m,n) is defined to be the smallest integer p such that in every two-coloring (R,B) of the edges of Kp, Γ(B)⩾m or β(R)⩾n. Since β(G)⩽Γ(G) for every graph G, u(m,n)⩽v(m,n)⩽r(m,n). We develop techniques to obtain upper bounds for upper domination Ramsey numbers of the form u(3,n) and mixed domination Ramsey numbers of the form v(3,n). We show that u(3,3)=v(3,3)=6, u(3,4)=8, v(3,4)=9, u(3,5)=v(3,5)=12 and u(3,6)=v(3,6)=15.  相似文献   

13.
SupposeG n={G 1, ...,G k } is a collection of graphs, all havingn vertices ande edges. By aU-decomposition ofG n we mean a set of partitions of the edge setsE(G t ) of theG i , sayE(G t )== \(\sum\limits_{j = 1}^r {E_{ij} } \) E ij , such that for eachj, all theE ij , 1≦ik, are isomorphic as graphs. Define the functionU(G n) to be the least possible value ofr aU-decomposition ofG n can have. Finally, letU k (n) denote the largest possible valueU(G) can assume whereG ranges over all sets ofk graphs havingn vertices and the same (unspecified) number of edges. In an earlier paper, the authors showed that $$U_2 (n) = \frac{2}{3}n + o(n).$$ In this paper, the value ofU k (n) is investigated fork>2. It turns out rather unexpectedly that the leading term ofU k (n) does not depend onk. In particular we show $$U_k (n) = \frac{3}{4}n + o_k (n),k \geqq 3.$$   相似文献   

14.
An algorithm for the construction of Ramsey graphs with a given automorphism group G is presented. To find a graph on n vertices with no clique of k vertices, Kk, and no independent set of l vertices, ¯Kl, k, ln, with an automorphism group G, a Boolean formula α based on the G-orbits of k-subsets and l-subsets of vertices is constructed from incidence matrices belonging to G. This Boolean formula is satisfiable if and only if the desired graph exists, and each satisfying assignment to α specifies a set of orbits of pairs of vertices whose union gives the edges of such a graph. Finding these assignments is basically equivalent to the conversion of α from CNF to DNF (conjunctive to disjunctive normal form). Though the latter problem is NP-hard, we present an “efficient” method to do the conversion for the formulas that appear in this particular problem. When G is taken to be the dihedral group Dn for n ≤ 101, this method matches all of the previously known cyclic Ramsey graphs, as reported by F. R. K. Chung and C. M. Grinstead [“A Survey of Bounds for Classical Ramsey Numbers,” Journal of Graph Theory, 7 (1983), 25–38], in dramatically smaller computer time when compared to the time required by an exhaustive search. Five new lower bounds for the classical Ramsey numbers are established: R(4, 7) ? 47, R(4, 8) ? 52, R(4, 9) ? 69, R(5,7) ? 76, and R(5, 8) ? 94. Also, some previously known cyclic graphs are shown to be unique up to isomorphism.  相似文献   

15.
The theory of vertex-disjoint cycles and 2-factors of graphs is the extension and generation of the well-known Hamiltonian cycles theory and it has important applications in network communication. In this paper we first prove the following result. Let G=(V 1,V 2;E) be a bipartite graph with |V 1|=|V 2|=n such that n≥2k+1, where k≥1 is an integer. If d(x)+d(y)≥?(4n+2k?1)/3? for each pair of nonadjacent vertices x and y of G with xV 1 and yV 2, then, for any k independent edges e 1,…,e k of G, G contains k vertex-disjoint quadrilaterals C 1,…,C k such that e i E(C i ) for each i∈{1,…,k}. We further show that the degree condition above is sharp. If |V 1|=|V 2|=2k, we give degree conditions that G has a 2-factor with k vertex-disjoint quadrilaterals C 1,…,C k containing specified edges of G.  相似文献   

16.
Let c be a proper k-coloring of a connected graph G and Π=(C1,C2,…,Ck) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple cΠ(v):=(d(v,C1),d(v,C2),…,d(v,Ck)), where d(v,Ci)=min{d(v,x)|xCi},1≤ik. If distinct vertices have distinct color codes, then c is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, denoted by χL(G). In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results, we show that χL(KG(n,2))=n−1 for all n≥5. Then, we prove that χL(KG(n,k))≤n−1, when nk2. Moreover, we present some bounds for the locating chromatic number of odd graphs.  相似文献   

17.
For two given graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer n such that for any graph G of order n, either G contains G1 or the complement of G contains G2. Let Cm denote a cycle of length m and Kn a complete graph of order n. In this paper, it is shown that R(C6,K8)=36.  相似文献   

18.
The Ramsey multiplicity M(G;n) of a graph G is the minimum number of monochromatic copies of G over all 2‐colorings of the edges of the complete graph Kn. For a graph G with a automorphisms, ν vertices, and E edges, it is natural to define the Ramsey multiplicity constant C(G) to be , which is the limit of the fraction of the total number of copies of G which must be monochromatic in a 2‐coloring of the edges of Kn. In 1980, Burr and Rosta showed that 0 ≥ C(G) ≤ 21?E for all graphs G, and conjectured that this upper bound is tight. Counterexamples of Burr and Rosta's conjecture were first found by Sidorenko and Thomason independently. Later, Clark proved that there are graphs G with E edges and 2E?1C(G) arbitrarily small. We prove that for each positive integer E, there is a graph G with E edges and C(G) ≤ E?E/2 + o(E). © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 89–98, 2008  相似文献   

19.
A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7.  相似文献   

20.
If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.Pn will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. Pm × Pn will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(Pm × Pn) = min(m, n).  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号