Honors Theses

Advisor

R. Sritharan

Department

Computer Science

Publication Date

Spring 4-2016

Document Type

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 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.

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.

Disciplines

Computer Sciences


Share

COinS