Menu
Both the bandwidth and additive bandwidth of a graph supply information about the storage requirements of a representation of the graph. In particular, the bandwidth measures how far \(1\)’s must be from the main diagonal of the graph’s adjacency matrix, while the additive bandwidth yields the same information with respect to the main contradiagonal. Thus, storage can be significantly reduced from that required by the full adjacency matrix if at least one of the two types of bandwidths is small, which is most likely to occur for sparse matrices. Alternatively, one could store a representation of the complement of the graph if one of its two bandwidths is small. We relate the additive bandwidth to other graphical invariants and then concentrate on Nordhaus-Gaddum type results to show that there are graphs for which both the bandwidth and the additive bandwidth of both the graph and its complement are large. In other words, some graphs require near maximum storage.