John S. Caughman IV
Date of Award
Bachelor of Science (B.S.) in Mathematics and University Honors
Trees (Graph theory), Equivalence relations (Set theory)
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.
In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
Flowerday, Kaelyn, "Unfolding Trees & Symmetrically-Associated Graphs" (2015). University Honors Theses. Paper 210.