Results on Some Generalizations of Interval Graphs

Author(s)

Jonathan David Ashbrock, University of Dayton

Advisor

R. Sritharan

Department

Computer Science

Publication Date

Spring 4-2016

Document Type

Honors Thesis

Abstract

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 K_{1, 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 K_{1, n}. Finally, we characterize k-trees that are path graphs.

Permission Statement

This item is protected by copyright law (Title 17, U.S. Code) and may only be used for noncommercial, educational, and scholarly purposes.

Keywords

Undergraduate research

Disciplines

Computer Sciences

eCommons Citation

Ashbrock, Jonathan David, "Results on Some Generalizations of Interval Graphs" (2016). Honors Theses. 82.
https://ecommons.udayton.edu/uhp_theses/82