The neighbor matrix: generalizing a graph's degree sequence

Authors Jonathan W. Roginski, Ralucca Gera, Erik C. Rye

Publication date 23 February 2018

Full work available at URL https://arxiv.org/abs/1510.06952

adjacency matrix centrality distance graph power graph topology

Vertex degrees (05C07) Distance in graphs (05C12) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: The newly introduced neighborhood matrix extends the power of adjacency and distance matrices to describe the topology of graphs. The adjacency matrix enumerates which pairs of vertices share an edge and it may be summarized by the degree sequence, a list of the adjacency matrix row sums. The distance matrix shows more information, namely the length of shortest paths between vertex pairs. We introduce and explore the neighborhood matrix, which we have found to be an analog to the distance matrix what the degree sequence is to the adjacency matrix. The neighbor matrix includes the degree sequence as its first column and the sequence of all other distances in the graph up to the graph's diameter, enumerating the number of neighbors each vertex has at every distance present in the graph. We prove this matrix to contain eleven oft-used graph statistics and topological descriptors. We also provide insight into two applications that show potential utility of the neighbor matrix in comparing graphs and identifying topologically significant vertices in a graph.

Recommendations

Cited in

(6)

This page was built for publication: The neighbor matrix: generalizing a graph's degree sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604143)