Ramsey Theory and Bandwidth of Graphs |
| |
| Authors: | Zoltán Füredi Douglas B West |
| |
| Institution: | Mathematical Institute of the Hungarian Academy of Science, and University of Illinois. e-mail: z-furedi@math.uiuc.edu, US
Department of Mathematics, University of Illinois, Urbana, IL 61801, USA?e-mail: west@math.uiuc.edu, US
|
| |
| Abstract: | The bandwidth of a graph is the minimum, over vertex labelings with distinct integers, of the maximum difference between
labels on adjacent vertices. Kuang and McDiarmid proved that almost all n-vertex graphs have bandwidth . Thus the sum of the bandwidths of a graph and its complement is almost always at least ; we prove that it is always at most 2n−4 log 2
n+o(log n). The proofs involve improving the bounds on the Ramsey and Turán numbers of the “halfgraph”.
Received: September 2, 1998?Final version received: November 29, 1999 |
| |
| Keywords: | , ,Bandwidth, Ramsey number, Turán number, Halfgraph, Random graph |
| 本文献已被 SpringerLink 等数据库收录！ |
|
