Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Optimal indexing of the vertices of graphs

Author: Carl H. FitzGerald
Journal: Math. Comp. 28 (1974), 825-831
MSC: Primary 05C99
MathSciNet review: 0379289
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The incidence matrices of various graphs are considered. By reordering the points, the bandwidth can be changed. In the cases of rectangular grids in the plane or cubic grids in three dimensions, the exact, minimum values of the bandwidth are determined.

In certain numerical analysis problems, it is of interest to index the vertices of a graph in such a way that the matrix used to represent an associated system of linear equations is as close to diagonal as possible or, equivalently, to index the vertices of a graph in a way that minimizes the width of the band of nonzero terms in the incidence matrix for that graph. The purpose of this note is to present a few methods of determining the minimum possible width in some cases that arise in the numerical solution of Laplace's equation. Of particular interest are the first proof of Theorem 2 which solves the problem for the common square grid and Theorem 3 which answers the problem for the cubic grid.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 05C99

Retrieve articles in all journals with MSC: 05C99

Additional Information

Keywords: Bandwidth, incidence matrix, grids
Article copyright: © Copyright 1974 American Mathematical Society

American Mathematical Society