close

Вход

Забыли?

вход по аккаунту

?

315

код для вставкиСкачать
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.
Документ
Категория
Без категории
Просмотров
2
Размер файла
100 Кб
Теги
315
1/--страниц
Пожаловаться на содержимое документа