An interval graph is the intersection graph of a family of intervals on the real line. Interval graphs are a well-studied class of graphs. Path graphs are a generalization of interval graphs and are defined to be the intersection graphs of a family of paths in a tree. In this thesis, we study path graphs which are representable in a subdivided K1, 3. Our main results are a characterization theorem and a polynomial time algorithm for recognition of this class of graphs. The second section of this thesis provides a bound for a graph parameter, the boxicity of a graph, for intersection graphs of subtrees of subdivided K1, n. Finally, we characterize k-trees that are path graphs.
This item is protected by copyright law (Title 17, U.S. Code) and may only be used for noncommercial, educational, and scholarly purposes.
Ashbrock, Jonathan David, "Results on Some Generalizations of Interval Graphs" (2016). Honors Theses. 82.