Determining graph properties from matrix representations
David Kirkpatrick · 1974
An open problem, posed by A. Rosenberg [R], motivates the consideration of representations of graphs and the effect of these representations on the efficiency of algorithms which determine properties of unlabelled graphs. In this paper we investigate three matrix representations of graphs; the (vertex) adjacency matrix, the edge-adjacency matrix, and the incidence matrix. With the exception of one instance of the edge-adjacency matrix, these structures determine an unlabelled graph up to isomorphism and are, as a result, natural candidates for computer representations of graphs.