Back to search

North Dakota State University

The Square of Adjacency Matrices

Abstract

dc:description.abstract

It can be shown that any symmetric (0, 1)-matrix A with tr A = 0 can be interpreted as the adjacency matrix of a simple, finite graph. The square of an adjacency matrix A2 = (si1) has the property that Sij represents the number of walks of length two from vertex i to vertex j. With this information, the motivating question behind this paper was to determine what conditions on a matrix S are needed to have S = A(G)2 for some graph G. Structural results imposed by the matrix S include detecting bipartiteness or connectedness, counting four cycles and determining plausible neighborhoods of vertices. Some characterizations will be given and the problem of when S represents several non-isomorphic graphs is also explored.

Degree

thesis:*
Grantor dc:publisher
North Dakota State University
Year dc:date.issued
2011

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kranda, Daniel Joseph

Subjects

dc:subject × 2

Rights

dc:rights
Statement dc:rights
  • NDSU policy 190.6.2

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10365/33250

Chain of custody

source
Harvested from
North Dakota State University
Base URL
library.ndsu.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Kranda, Daniel Joseph. The Square of Adjacency Matrices. North Dakota State University, 2011. https://hdl.handle.net/10365/33250