NONBIPARTITE GRAPHS WITH THE REPEATED DEGREE PROPERTY

A graph G has the repeated degree property if there is an integer n su ch that for each graph H with at least n vertices, either H or its com plement contains a copy of G in which two vertices have the same degre e in H. The minimum such number n is the repeated degree number of G. We extend work of Chen, Erdos, Rousseau and Schelp by showing that eve ry graph having two endvertices that share a common neighbor has the r epeated degree property. We also show that all books have the properly in question and give a linear upper bound for their repeated degree n umbers. We say that a graph G has the strongly repeated degree propert y 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, ei ther H or its complement contains a copy of G that in turn contains bo th u and v. We show that a connected graph with at least four vertices has this property iff it is a spanning subgraph of K-2,K-k - e fore s ome k. (C) 1997 John Wiley & Sons, Inc.