Date of Award

11-2015

Document Type

Thesis

Department

Mathematics

First Advisor

John S. Caughman IV

Subjects

Graph theory, Equivalence relations (Set theory), Graph labelings

DOI

10.15760/honors.210

Abstract

An unfolding tree is an object reflecting the connectivity properties of a vector-labelled graph. First introduced in the context of theoretical computer science as a way of describing information flow in a neural net model of graph-structured data, unfolding trees have remained unexplored within graph theory. They give rise to an equivalence relation on the vertices of a graph, one which describes the connective environments of vertices but is not reducible to automorphism group orbits. This thesis formalizes unfolding trees and investigates their properties along with the implications of this vertex relation. This leads to the graph property of symmetric-association; graphs with this property have predictably-behaved unfolding trees. Symmetric-association is presented as a generalization of k-regularity, culminating in a Havel-Hakimi type result featuring a graph transformation that preserves unfolding trees.

Comments

A Thesis Presented to the Department of Mathematics and Statistics Portland State University In Partial Fulfillment of the Requirements for the Degree of Bachelor of Science in Mathematics with Departmental Honors

Persistent Identifier

http://archives.pdx.edu/ds/psu/16446

Share

COinS