Nonbipartite graphs with the repeated degree property

✍ Scribed by S?olt�s, L?ubomi?r

• Book ID: 101227749
• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 100 KB
• Volume: 26
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199709)26:1<17::aid-jgt3>3.0.co;2-k

✦ Synopsis

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 iff it is a spanning subgraph of K 2,k -e fore some k.