Physical Sciences and Mathematics Commons^™

On The Unique Tree Representation Of Graphs, Beverly Jamison

Computer Science Theses & Dissertations

This dissertation investigates classes of graphs which admit tree representations unique up to isomorphism. The definitions of these classes are based on local properties of P₄'s, A template structure theorem is given which illustrates the nature of the local properties. The template theorem is instantiated for three different classes of graphs. Properties specific to each of the classes are used to produce a tree representation which can be used for graph computations, such as efficient resolution of graph isomorphism. Linear time algorithms for the recognition of three classes of graphs and for the construction of their tree representations …