Date of Award

11-2015

Document Type

Thesis

Department

Mathematics and Statistics

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.

Comments

An undergraduate honors thesis submitted in partial fulfillment of the requirements for the degree of Bachelor of Science in University Honors and Mathematics

Persistent Identifier

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

Share

COinS