Ramsey Theory and Bandwidth of Graphs |
| |
Authors: | Zoltán Füredi Douglas B. West |
| |
Affiliation: | 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 等数据库收录! |
|