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 等数据库收录！ |
|
