The Neighbor Matrix: generalizing the degree sequence
View/Open
Author
Roginski, Jonathan W.
Gera, Ralucca M.
Rye, Eric C.
Date
20151019Metadata
Show full item recordAbstract
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 neighborhood 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 oftused graph statistics and topological descriptors. We also provide proofs of concept for two applications that show potential utility of the neighbor matrix in comparing graphs and identifying topologically significant vertices in a graph.
Description
Approved for public release; distribution is unlimited
Collections
Related items
Showing items related by title, author, creator and subject.

Spectral graph theory of the Hypercube
Florkowski, Stanley F. (Monterey, California. Naval Postgraduate School, 200812);In Graph Theory, every graph can be expressed in terms of certain real, symmetric matrices derived from the graph, most notably the adjacency or Laplacian matrices. Spectral Graph Theory focuses on the set of eigenvalues ... 
A branchandbound algorithm for the solution of sequence dependent routing problems
DeHaemer, Michael Joseph (Monterey, California; Naval Postgraduate School, 197004);A branchandbound algorithm, which finds the optimal route through n nodes when a different cost matrix occurs after each arc in the sequence is traversed, is presented. The route may begin at any node and must pass ... 
Analysis of the necklace algorithm and its applications
Matty, Douglas M. (Monterey, California. Naval Postgraduate School, 199906);A commonly studied problem in the field of cryptography is the Discrete Logarithm Problem. This problem is also referred to as the "distance" problem. Basically, one would like to know where a particular binary ntuple is ...