Date of Award

11-2015

Document Type

Thesis

Degree Name

Bachelor of Science (B.S.) in Mathematics and University Honors

Department

Mathematics

First Advisor

John S. Caughman IV

Subjects

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

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.

Persistent Identifier

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

Share

COinS