On cross-bandwidth |
| |
Authors: | J. Kahn D.J. Kleitman |
| |
Affiliation: | Mathematics Department, Massachusetts Institute of Technology, Cambridge, MA 02139, USA |
| |
Abstract: | The notion of cross-bandwidth is introduced, and it is shown that any graph that is suitably contractible to a k-connected graph has cross-bandwidth at least k. The contracted edges must induce in the original graph a subgraph of maximum degree at most one. This is used to resolve a conjecture of Erdös and Chinn on the bandwidth of certain graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|