Nonbipartite Graphs with the Repeated Degree Property Ľubomír Šoltés DEPARTMENT OF MATHEMATICS WEST VIRGINIA UNIVERSITY MORGANTOWN, WV 26506-6310 E-mail: soltes@math.wvu.edu Received May 24, 1995 Abstract: A graph G has the repeated degree property if there is an integer n such that for each graph H with at least n vertices, either H or its complement contains a copy of G in which two vertices have the same degree in H. The minimum such number n is the repeated degree number of G. We extend work of Chen, Erdős, Rousseau and Schelp by showing that every graph having two endvertices that share a common neighbor has the repeated degree property. We also show that all books have the property in question and give a linear upper bound for their repeated degree numbers. We say that a graph G has the strongly repeated degree property if there is an integer n such that for each graph H with at least n vertices and for each two vertices u and v of the same degree in H, either H or its complement contains a copy of G that in turn contains both u and v. We show that a connected graph with at least four vertices has this property c 1997 John Wiley & Sons, Inc. J Graph iff it is a spanning subgraph of K2,k − e fore some k. Theory 26: 17–25, 1997 Keywords: degrees in graphs, edge-colorings, Ramsey numbers 1. GRAPHS WITH LARGE CLIQUES AND THE REPEATED DEGREE PROPERTY The well known Ramsey's theorem guarantees that any sufficiently large complete graph, whose edges are colored red or blue, contains a monochromatic copy of a pre-specified graph G. In c 1997 John Wiley & Sons, Inc. CCC 0364-9024/97/010017-09 18 JOURNAL OF GRAPH THEORY this paper we are concerned with the existence of monochromatic copies of a given graph G such that some two vertices in the copy have the same number of blue edges (in the colored complete graph) incident to them. Such copies of G will be referred to as good copies. A graph G has the repeated degree property if there is an integer n such that each coloring of edges of any complete graph with at least n vertices with blue and red contains a good copy of G. The smallest such an integer n is the repeated degree number, denoted RN (G). The study of graphs with the repeated degree property was initiated by Albertson [1] who proved that a triangle has this property with the repeated degree number six. Albertson and Berman [2] pointed out that if one replaces ‘‘a monochromatic copy’’ with ‘‘a good copy’’ in the statement of Ramsey's theorem, the theorem does not hold. Namely, they showed that the complete graph K4 does not have the repeated degree property by exhibiting an infinite sequence of two-colored complete graphs without a good K4 . Obviously, no member of the infinite sequence contains a good Kk , for k ≥ 4, therefore complete graphs with at least four vertices fail to have the repeated degree property. Thus the question ‘‘Which graphs have the repeated degree property?’’ arises naturally. Some positive answers were obtained by Chen, Erdős, Rousseau and Schelp [3]. They have shown that complete bipartite graphs with at least two vertices and all cycles have the repeated degree property. They also asked whether there exist noncomplete graphs that fail to have the repeated degree property. Until recently, the only nonbipartite graphs that were known to have the repeated degree property were odd cycles [3] and K4 − e [4]. The first result in this section substantially expands the class of graphs known to have the repeated degree property. For instance, it follows from the next result that every graph is an induced subgraph of a graph with the repeated degree property. The theorem also gives an upper bound for RN (G) in terms of the Ramsey number of a graph G, denoted by r(G). A vertex in a graph is said to be an endvertex if its degree is one. Theorem 1.1. Every p-vertex graph G containing two endvertices that share a common neighbor w has the repeated degree property with the repeated degree number RN (G) ≤ r(G − w)(r(G) − 1) + 1. p−1 Before proving Theorem 1.1, we introduce several concepts frequently used in the rest of the paper and a widely used lemma. The neighborhood of a vertex v in a graph G, denoted by G(v), is the set of all vertices in G adjacent to the vertex v. The cardinality of the neighborhood G(v) is the degree deg(v) of the vertex v. The closed neighborhood G[v] of v in G is the set obtained from the neighborhood of v by the addition of the vertex v; thus G[v] = G(u) ∪ {u}. The existence of two vertices of the same degree in a connected graph of order at least two is guaranteed by the Pigeonhole Principle. The following lemma shows that such a pair of vertices can always be found in certain closed neighborhoods. Lemma 1.2. If v is a vertex of maximum and positive degree in a graph, then the closed neighborhood of v contains two vertices of the same degree. Proof. The closed neighborhood of v contains 1 + deg(v) vertices with the degrees between one and deg(v). Thus two of them have the same degree. The degree spread of G, denoted ds(G), is the difference between the maximum and the minimum degree in G. Suppose that K is a complete graph whose edges are colored blue or red. The subgraph induced by the blue edges will be denoted by B, while R will be the subgraph induced by the red edges. The neighborhoods in the graph B or R will be referred to as blue THE REPEATED DEGREE PROPERTY 19 neighborhoods or red neighborhoods. The concepts blue neighbor, blue degree, red neighbor and red degree are defined similarly. If no color is indicated, then we mean blue; thus ‘‘blue degree’’ is the same as ‘‘degree.’’ Similarly, if we say that two vertices are adjacent, then the edge connecting them is blue. Proof of Theorem 1.1. Suppose that the edges of a complete graph K are colored with red and blue in such a way that the graph K contains no good G. We will show that the complete graph has at most r(G − w)(r(G) − 1)/(p − 1) vertices, which proves the theorem. Let n denote the order of K. We will distinguish two cases with respect to the magnitude of the degree spread of B. Case 1. Suppose that the degree spread of B is at most r(G − w) − 1. Hence there are at most r(G − w) distinct degrees in the blue graph. Denote by Vi the set of vertices in K with blue degree i. Thus the vertex set of K is partitioned into the sets Vδ , Vδ+1 , . . . , Vδ+ds(B) . Let U be the union of those p − 1 sets in the partition that have the largest cardinalities. Since the partition has ds(B) + 1 parts, we have |U | ≥ (p − 1)n/(ds(B) + 1). If the cardinality of U is at least r(G), then the subgraph induced by U contains a monochromatic copy G0 of G. Since G0 has p vertices and there are only p − 1 distinct degrees represented in the set U , the copy G0 is good. Hence U contains at most r(G) − 1 vertices. Comparing this upper bound with the previous lower bound for |U | we obtain n≤ r(G) − 1 r(G) − 1 (ds(B) + 1) ≤ r(G − w). p−1 p−1 This completes the proof in Case 1. Case 2. Suppose that the degree spread in B is at least r(G − w). Let u be a vertex of minimum degree δ in B and let v be a vertex of maximum degree δ + ds(B) in B. Let B(v)R(u) denote the set of vertices adjacent to v in blue and to u in red. Next we obtain a lower bound for the cardinality of B(v)R(u). Note that if one deletes the edge vu from the complete graph K, the difference between the blue degrees of the vertices v and u remains the same, hence it is ds(B). Thus there are at least ds(B) vertices in V (K) − {v, u} that are adjacent to v but not adjacent to u (in B). These vertices are in the set B(v)R(u), therefore |B(v)R(u)| ≥ ds(B). (1) Since |B(v)R(u)| ≥ ds(B) ≥ r(G − w), there is a monochromatic copy of G − w in the subgraph induced by B(v)R(u). Because of symmetry we can assume that the copy is blue (otherwise interchange colors and v with u). Since the vertex v is adjacent in blue to all the vertices of the copy, the blue copy of G − w can be extended to a blue copy G∗ of G by the addition of the vertex v and certain edges incident to v. In G∗ , the vertex v plays the role of the vertex w. We will show that G∗ can be modified to a good copy of G by the addition and the removal of at most two blue edges incident with v. By Lemma 1.2, the closed blue neighborhood B[v] of the vertex v contains vertices x1 and x2 with the same blue degree. If x1 and x2 are in the graph G∗ , then we have a good copy of G. If neither x1 nor x2 is in G∗ , then, by the hypothesis, there are two endvertices z1 and z2 in G∗ that are adjacent to the vertex v. Replacing the blue edges vz1 and vz2 with the blue edges vx1 and vx2 we obtain a good copy of G. Finally, if the vertex x1 is not in G∗ but x2 lies in G∗ , let z be a vertex in {z1 , z2 } that is distinct from x2 . Replacing the edge vz with the edge vx1 we obtain a copy of G that contains both x1 and x2 , thus the copy is good. This contradicts the assumption that the colored complete graph does not contain a good copy of G. 20 JOURNAL OF GRAPH THEORY 2. REPEATED DEGREE NUMBERS FOR BOOKS A book Bk is a graph consisting of k triangles sharing a common edge. Albertson [1] has shown that the repeated degree number for the smallest book, that is for a triangle, is six, which is also its Ramsey number. He raised the question whether B2 , the next smallest book, has the repeated degree property. Rousseau and Schelp [4] answered the question affirmatively by showing that RN (B2 ) ≤ 459. We will determine the exact value of RN (B2 ). It follows from a result due to Rousseau and Sheehan [5] that r(B2 ) = 10. We will show that, for B2 , the repeated degree number equals to the Ramsey number. Interestingly enough, one can prove this without knowing the Ramsey number r(B2 ). We will also show that all books have the repeated degree property and give a linear upper bound for their repeated degree numbers. Throughout this section δ represents the minimum degree in the graph B. The symbol B(v)R(u) is a shortened notation for B(v) ∩ R(u), the set of vertices adjacent in blue to the vertex v and adjacent to u in red. The symbols B(v)B(u), R(v)R(u) and R(v)B(u) have a similar meaning. A set S of vertices is a kernel of a complete 2-colored graph K if S = B(v)R(u) for some vertices v and u such that the vertex v has maximum blue degree and the vertex u has minimum blue degree δ. Construct a graph K ∗ by exchanging the colors of the edges in K. Note that a set of vertices is a kernel of K ∗ if and only if it is a kernel of K. Thus the definition of the kernel does not depend on the permutation of colors. A subset S of vertices in a two-colored complete graph K is said to be antiregular if no two vertices in S have the same degree in B. The case when a colored complete graph contains an antiregular kernel is handled by the next lemma. Lemma 2.1. Let K be a two-colored complete graph containing an antiregular kernel. Then K contains a good Bk if and only if it contains a monochromatic Bk (for an integer k ≥ 2). Proof. Since each good subgraph is monochromatic, suppose toward a contradiction that K contains a monochromatic copy of Bk but no good Bk . Thus the k + 2 vertices in a monochromatic copy of Bk have distinct blue degrees. This gives ds(B) ≥ k + 1. (2) Suppose that B(v)R(u) is an antiregular kernel of K guaranteed by the hypothesis with deg(u) = δ and deg(v) = δ + ds(B). Each degree in K belongs to the closed interval [δ, δ + ds(B)]. By (1) the antiregular kernel contains at least ds(B) vertices, thus all degrees in K, but possibly one, are represented in the kernel. In particular, at least one of the numbers δ and δ + ds(B) occurs as the degree of a vertex in the kernel. Without loss of generality suppose that there is a vertex v 0 of degree δ + ds(B) in the kernel; otherwise permute colors. Let u0 be a vertex of minimum degree among the vertices in the kernel B(v)R(u). It is easy to see that the degree of u0 is either δ or δ + 1. We will reach a contradiction by showing that either vv 0 or uu0 is a central edge in a good (blue or red) Bk . Let n be the order of K. Recall that the vertices v and v 0 have the same degree. If the sum deg(v) + deg(v 0 ) is at least n + k, then v and v 0 have at least k common neighbors. Thus we have a good blue Bk with the central edge vv 0 . Otherwise we have 2δ +2ds(B) = deg(v)+deg(v 0 ) ≤ n + k − 1, which gives 2δ + 2ds(B) − k + 1 ≤ n. (3) Moreover, the edge v 0 u is red and if the edge vu is also red, then one can restrict himself to the graph K − u. Since v and v 0 have at most k − 1 common blue neighbors in K − u, the inequality THE REPEATED DEGREE PROPERTY 21 2δ + 2ds(B) ≤ (n − 1) + k − 1 holds. Therefore if the equality equality in (3) holds then the edge uv is blue. Now we give a condition that is necessary to avoid a good red book. If the sum of the cardinalities of R(u) and R(u0 ) is at least n + ds(B), then there are at least ds(B) vertices that lie in both R(u) and R(u0 ). Since there are at most ds(B) + 1 distinct degrees in the colored K, the maximal red book with the central edge uu0 contains two vertices of the same degree. Clearly, it also contains a good Bk as a subgraph, since ds(B) ≥ k + 1 by (2). Hence we may assume that |R(u)| + |R(u0 )| ≤ n + ds(B) − 1. This gives (n − 1 − δ) + (n − 1 − δ − 1) ≤ |R(u)| + |R(u0 )| ≤ n + ds(B) − 1. From this we obtain n ≤ ds(B) + 2δ + 2. (4) Similarly as before, the edge vu0 is blue and if, moreover, the edge vu is blue, then one can consider the graph K − v and show that n ≤ ds(B) + 2δ + 2 − 1. Thus if equality holds in (4) then edge vu is red. From (3) and (4) we have ds(B) ≤ k + 1. By (2), we have the equality ds(B) = k + 1. This implies that the equalities in (3) and (4) hold. But the edge uv is blue in the former case and red in the latter, a contradiction. In the case k = 2, the last lemma holds even for colorings with no antiregular kernels, which yields RN (B2 ) = r(B2 ) = 10. Theorem 2.2. A two-colored complete graph contains a good B2 if and only if it contains a monochromatic B2 . In particular we have RN (B2 ) = r(B2 ). Proof. Suppose toward a contradiction that there is a red-blue edge coloring of the complete graph K with a monochromatic copy B2∗ of B2 and without a good B2 . Since the four vertices of B2∗ have distinct blue degrees, the degree spread of B is at least three. By the previous lemma we can assume that K has no antiregular kernel. Thus suppose that in a kernel B(v)R(u) = {x1 , x2 , . . . , xl }, the vertices x1 and x2 have the same blue degree. From inequality (1) we obtain l ≥ ds(B) ≥ 3. Moreover, at least two of the three edges x1 x2 , x2 x3 and x1 x3 have the same color, say blue. Then there is a good blue B2 with vertex set {v, x1 , x2 , x3 }, so Theorem 2.2 is proved. It is easy to see that if one replaces the book B2 with any of its spanning subgraphs, the last theorem remains valid (with the same proof). Thus Theorem 2.2 holds for any noncomplete graph on four vertices. In fact, one can prove a slightly stronger result. Corollary 2.3. Suppose that G is a graph with at most four vertices and distinct from K1 and K4 and let K be any two-colored complete graph. Then K contains a good copy of G if and only if it contains a monochromatic copy of G. In particular, RN (G) = r(G). By Albertson's result RN (K3 ) = 6, the first statement in Corollary 2.3 holds for subgraphs with three vertices in two-colored complete graphs with at least six vertices. It is left to the reader to verify its validity for two-colored complete graphs with at most five vertices as well as in the case that the graph G has two vertices. This proves the corollary. One direction for a future research is to find other graphs G that satisfy the conclusion of the last corollary. Now we will return to the main problem of this section and show that all books have the repeated degree property. Rousseau and Sheehan [5] have shown that r(Bk ) ≤ 4k + 2 22 JOURNAL OF GRAPH THEORY and that equality occurs for infinitely many values of k. We will prove that the repeated degree numbers for books are also bounded by a linear function of k. Theorem 2.4. The repeated degree number for a book Bk is at most 10k. Proof. Suppose toward a contradiction that there is a red-blue edge coloring of a complete graph K with at least 10k vertices and with no good Bk , for an integer k ≥ 2. Let n denote the order of K. By a result of Rousseau and Sheehan we have n ≥ 10k > 4k + 2 ≥ r(Bk ). Thus K contains a monochromatic Bk and if it contains an antiregular kernel, then it also contains a good Bk by Lemma 2.1. Therefore one may assume that there is no antiregular kernel in K and thus each kernel contains two vertices of the same degree. Suppose that x1 and x2 are vertices of the same degree lying in the kernel B(v)R(u). Moreover, without loss of generality we may assume that edge x1 x2 is blue (otherwise permute colors). Let C denote the set of the vertices in the kernel that are adjacent to both x1 and x2 in red. We will reach a contradiction by calculating the degree spread in C in two ways. Note that x1 has at most k − 1 blue neighbors in the kernel B(v)R(u), since otherwise the neighbors would belong to a blue good Bk with the central edge vx1 . For the same reason, x2 has at most k − 1 blue neighbors in the kernel. Thus |C| ≥ |B(v)R(u)| − 2(k − 1). Counting the contributions of the vertices to the difference between the degree of v and the degree of u one can check that ds(B) = deg(v) − deg(u) = |B(v)R(u)| − |R(v)B(u)|, (5) |C| ≥ ds(B) + |R(v)B(u)| − 2(k − 1). (6) which gives Before giving an upper bound for the cardinality of C, we will prove the following three claims. Claim 1. The degree spread of B satisfies the inequality ds(B) ≥ n−k−1 . 3 (7) Proof of Claim 1. Let Vi denote the set of vertices in K with blue degree i. Thus the vertex set of K can be partitioned into the equivalence classes Vδ , Vδ+1 , . . . , Vδ+ds(B) . Let U be the union of the k + 1 of these classes with the largest cardinality. If the union U contains at least 4k + 2 vertices, then there is a monochromatic Bk in the subgraph induced by U . Since Bk contains k+2 vertices, two of them have the same degree, and, we have a good Bk , a contradiction. This implies that |U | ≤ 4k + 1, hence the average cardinality among the classes in U is at most (4k + 1)/(k + 1) < 4. Hence there is an equivalence class in U that contains at most three vertices. By the definition of U all classes that are not in U contain at most three vertices. Consequently, their union contains at most 3((ds(B) + 1) − (k + 1)) vertices. Hence n = |U | + |V (K) − U | ≤ (4k + 1) + 3((ds(B) + 1) − (k + 1)). This gives (7) and Claim 1 is proved. Claim 2. Each vertex in C has at most k − 1 red neighbors in R(u). THE REPEATED DEGREE PROPERTY 23 Proof of Claim 2. If a vertex c from C has k red neighbors in R(u), then we have a good red Bk with central edge cu and containing the vertices x1 and x2 of the same degree. Claim 3. The set C ∪ {x1 } is antiregular. Proof of Claim 3. By (5) inequality |B(v)R(u)| ≥ ds(B) holds and combining this with Claim 7 and n ≥ 10k one can check that the kernel B(v)R(u) contains at least 2k vertices (in fact more, but 2k is enough). The vertex x1 has at most k − 1 blue neighbors in the kernel B(v)R(u), otherwise one obtains a good blue Bk with the central edge vx1 containing x2 and other k − 1 neighbors of x1 in the kernel. Since |B(v)R(u)| ≥ 2k, vertex x1 has at least k red neighbors in the kernel. For each two vertices c1 and c2 in C there is a red Bk with central edge x1 u containing c1 , c2 and other k − 2 red neighbors of x1 in the kernel. Since the book is not good, its vertices have distinct degrees. This yields that the set C ∪ {x1 } is antiregular. Let vmax and vmin be the vertices of maximum, resp. minimum degree among the vertices in C. Since C is antiregular, from (6) we obtain deg(vmax ) − deg(vmin ) ≥ |C| − 1 ≥ ds(B) + |R(v)B(u)| − 2k + 1. (8) Now we will find an upper bound for the difference between the degrees of vmax and vmin . The vertices u and v do not contribute to the difference in question, thus we only need to estimate the contribution of the sets R(u), R(v)B(u) and B(v)B(u). The set R(v)B(u) contributes at most its cardinality, |R(v)B(u)|. It requires a little more effort to estimate the contribution of the rest, i.e., of the set B(v)B(u)∪ R(u). To estimate the contribution of the set B(v)B(u), we first show that for any vertex c in C, the set B(v)B(c) ∪ {v, c} is antiregular. Let l denote the number of red neighbors of the vertex c in R(u). It follows from Claim 2 that l ≤ k − 1. Since the kernel contains at least 2k vertices, at least k of them are blue neighbors of c. Thus the set B(v)B(c) has at least k vertices and each pair of its vertices lies in a blue book Bk with the central edge vc, which proves that the set B(v)B(c) ∪ {v, c} is antiregular. Thus |B(v)B(c)| ≤ ds(B) − 1. Since the vertex u is not in B(v)B(c), that set is the disjoint union of the sets B(v)B(u)B(c) and B(v)R(u)B(c). The latter set contains at most |B(v)R(u)| − (l + 1) vertices, thus for the cardinality of the former set we have |B(v)B(u)B(c)| + |B(v)R(u)| − (l + 1) ≤ ds(B) − 1 ≤ |B(v)R(u)| − |R(v)B(u)| − 1, where the right equality comes from (5). This gives |B(v)B(u)B(c)| ≤ l − |R(v)B(u)|. (9) By (9), vertex c has at most l − |R(v)B(u)| neighbors in the set B(v)B(u), it has at most |R(v)B(u)| neighbors in the set R(v)B(u) and |R(u)| − 1 − l neighbors in R(u). In summary the degree of c is at most |R(u)| − 1. On the other hand the degree of c is at least |R(u)| − 1 − l from the definition of l. Noting that l ≤ k − 1 we can see that the difference between degrees of any two vertices in C is at most l ≤ k − 1. Comparing this with (8) we obtain k − 1 ≥ deg(vmax ) − deg(vmin ) ≥ ds(B) + |R(v)B(u)| − 2k + 1. (10) 24 JOURNAL OF GRAPH THEORY This gives 3k − 2 ≥ ds(B) and in the view of Claim 1 we obtain 10k − 1 ≥ n, a contradiction has been reached. 3. GRAPHS WITH STRONGLY REPEATED DEGREE PROPERTY A graph G has the strongly repeated degree property if there is an integer n such that for an arbitrary coloring of edges of any complete graph with at least n vertices with blue and red, each pair of vertices of the same degree in the blue graph is contained in a monochromatic copy of G. The smallest such an integer n is the strongly repeated degree number, denoted SN (G). The next theorem characterizes connected graphs with the strongly repeated degree property. Theorem 3.1. A connected graph G with at least two vertices has the strongly repeated degree property if and only if G is K2 , P3 or G is a noncomplete bipartite graph in which one part contains exactly two vertices. Moreover, SN (K2 ) = 2, SN (P3 ) = 3 and for any graph G with at least four vertices having the strongly repeated degree property, SN (G) ≤ 6|V (G)| − 18. Proof. First suppose that G is a connected graph with the strongly repeated degree property and let n ≥ SN (G) be an even number. We will show that G is one of the graphs described in the statement of Theorem 3.1. Color the edges of Kn such that the blue graph is isomorphic to K2,n−2 . Since G has the strongly repeated degree property, the two vertices in blue K2,n−2 of degree n − 2 are contained in a monochromatic copy G∗ of G. If G∗ is red, then G∗ = K2 , since G∗ is connected. If G∗ is blue, then G∗ ⊆ K2,n−2 . Moreover, G∗ is a bipartite graph such that one of the parts contains exactly two vertices. Now we need to show that if G has at least four vertices, then G is not a complete bipartite graph. Suppose toward a contradiction that the complete bipartite graph K2,l has the strongly repeated degree property for some l ≥ 2. Color the edges of Kn such that the blue graph is a spanning subgraph of G consisting of two stars, both on n/2 + 1 vertices, sharing a common edge uv. Since the degrees of u and v are the same, ∗ of K2,l containing u and v. Since the blue graph is a tree, the there is a monochromatic copy K2,l ∗ copy K2,l is red. The vertices u and v are nonadjacent in red, thus they are in the same bipartite ∗ . But they have no common neighbor in the red graph, a contradiction. part of K2,l Next we show that K2 , P3 and each noncomplete bipartite graph in which one part contains exactly two vertices have the strongly repeated degree property and estimate their strongly repeated degree numbers. It is easy to check that SN (K2 ) = 2 and SN (P3 ) = 3. Since a spanning subgraph of a graph with the strongly repeated degree property has that property, it is enough to show that the removal of an edge from K2,l for l ≥ 2 yields a graph whose strongly repeated degree number is at most 6l − 6. For an integer n ≥ 6l − 6, color the edges of Kn with red and blue. Suppose that u and v are two vertices of the same degree in the blue graph. If |R(u)R(v)| ≥ l or |B(u)B(v)| ≥ l, then there is a red or a blue K2,l containing u and v. Thus assume that |R(u)R(v)| ≤ l − 1 and |B(u)B(v)| ≤ l − 1. Since n = 2 + |B(u)B(v)| + |R(u)R(v)| + |B(u)R(v)| + |R(u)B(v)|, the inequality n ≤ 2l + |R(u)B(v)| + |B(u)R(v)| holds. Since u and v have the same degree, |R(u)B(v)| = |B(u)R(v)| ≥ 2l − 3. Thus a vertex x in B(u)R(v) has at least l − 1 neighbors v1 , . . . , vl−1 of the same color in the set R(u)B(v). If necessary, one can exchange colors and the vertices u and v to obtain the coloring in which the edges xv1 , . . . , xvl−1 are blue, x ∈ B(u)R(v), v1 , . . . , vl−1 ∈ R(u)B(v). Since v1 , . . . , vl−1 are adjacent in blue to both x and v, we have a blue copy of K2,l − e with the vertex set {u, x, v1 , . . . , vl−1 , v}. Problem 3.2. Determine SN (K2,l − e) for every positive integer l. THE REPEATED DEGREE PROPERTY 25 4. OPEN PROBLEMS Here we discuss two problems that stem from Corollary 2.3. In addition to graphs described in this corollary, it follows from Lemma 1.2 that for any positive integer p, the existence of a monochromatic star K1,p in a two-colored complete graph guarantees the existence of a good K1,p in the same graph. We suggest to characterize all graphs with this property. Problem 4.1. Characterize graphs G such that for any two-colored complete graph K, the graph K contains a monochromatic copy of G if and only if it contains a good copy of G. Even if there is a two-colored complete graph which contains a monochromatic copy of a graph G but no good copy of G, the repeated degree number of G might equal to its Ramsey number. This leads to the question when the two numbers equal. The next conjecture offers an answer to this question. Conjecture 4.2. For any graph G with the repeated degree property RN (G) = r(G). ACKNOWLEDGMENT The author wishes to thank Richard H. Schelp for many helpful discussions on this topic. References [1] M. O. Albertson, People who know people, Math. Magazine 67 (1994), 278–281. [2] M. O. Albertson and D. M. Berman, Ramsey graphs without repeated degrees, Congress. Numer. 83 (1991), 91–96. [3] P. Erdős, G. Chen, C. C. Rousseau, and R. H. Schelp, Ramsey problems involving degrees in edgecolored complete graphs of vertices belonging to monochromatic subgraphs, Eur. J. Combinatorics 14 (1993), 183–189. [4] C. C. Rousseau and R. H. Schelp, A question of Albertson, (1993) manuscript. [5] C. C. Rousseau and J. Sheehan, On Ramsey numbers for books, J. Graph Theory 2 (1987), 77–87.

1/--страниц