Title

Change In Additive Bandwidth When An Edge Is Added

Abstract

Let G = (V, E) be an n-vertex graph and f: V → {1,2,.. ., n} be a bijection. The additive bandwidth of G, denoted B+(G), is given by B+(G) = minf maxuvεE |f(u) + f(v) - (n + 1)|, where the minimum ranges over all possible bijections f. The additive bandwidth cannot decrease when an edge is added, but it can increase to a value which is as much as three times the original additive bandwidth. The actual increase depends on B+(G) and n and is completely determined.

Publication Date

7-1-2003

Publication Title

Ars Combinatoria

Volume

68

Issue

1

Number of Pages

283-317

Document Type

Article

Personal Identifier

scopus

Socpus ID

0042575350 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0042575350

This document is currently not available here.

Share

COinS