ON CHARACTERIZATIONS AND STRUCTURE OF INTERVAL DIGRAPHS AND UNIT PROBE INTERVAL GRAPHS

Interval graphs and their variations have been studied extensively for the last 50 years from both a theoretical standpoint and due to their importance in applications. In this thesis we will explore several variations of interval graphs and unit interval graphs including interval digraphs, interval bigraphs and probe interval graphs. Interval graphs were mathematically introduced by Hajos [22]. The origin of interval graphs may also be regarded as an application to the research of Benzer in 1959 [1] in his study of the structure of bacterial genes. Many nice characterizations have been found for interval graphs, but the same cannot be said about the various generalizations. The work presented in this thesis will indicate that characterization of the broadest classes of the generalizations poses a very difficult problem and so the focus in this thesis is on subclasses of interval digraphs, interval bigraphs, and probe interval graphs. Interval digraphs were introduced by Sen et al. in [39](1989). In 1998 West gave adjacency matrix characterizations of interval digraphs and unit interval digraphs [42]. So far, in the most generic sense, no forbidden subgraph characterization of interval digraphs has been been found, but those tournaments which are interval digraphs have been characterized in various ways by Brown, Busch and Lundgren in 2007. In this thesis we generalize some of their results to other classes of interval digraphs. A natural extension of interval graphs, called interval bigraphs, were introduced by Harary, Kabell, and McMorris [23] in 1982. Unit and proper interval graphs were iii introduced and characterized by Roberts in 1969 [36]. He proved that the classes of proper interval graphs and unit interval graphs coincide. Proskurowski and Telle [33] extended the idea of proper interval graphs to p-proper interval graphs. Recently Beyerl and Jamison introduced p-improper interval graphs. They focussed on a special case of p-improper interval graphs. Here we generalize and obtain similar results for p-improper interval bigraphs. The probe interval graph was invented in order to aid with the task called physical mapping faced in connection with the human genome project, cf. work of Zhang and Zhang et al. [43], [45], [44]. No generalized characterization of probe interval graphs have been found so far. Li Sheng first characterized probe interval graphs for trees[41]. Following this characterization of cycle-free probe interval graphs, in 2009 Brown, Sheng and Lundgren gave a characterization for cycle-free unit probe interval graphs [15]. Recently Brown and Langley characterized unit probe interval graphs for bipartite graphs [10]. In this thesis we give a characterization of 2-trees that are unit probe interval graphs. In 2005 Pržulj and Corneil found at least 62 distinct minimal forbidden induced subgraphs for probe interval graphs that are 2-trees [34]. More recently Brown, Flesch and Lundgren extended the list to 69 and also gave a characterization [7]. In this thesis we follow the idea of Pržulj and Corneil for the next best case which is for 2-trees. The restriction to 2-trees is a reasonable thing to do because of the progression of the Sheng, Brown-Sheng-Lundgren, and Brown-Langely results, and also because of the Corneil-Pržulj and Brown-Flesch-Lundgren results. We first characterize 2-caterpillars and interior 2-caterpillars in terms of forbidden induced subgraphs and show that 2-trees that are unit probe interval graphs have to be interior 2-caterpillars. Then we look at 2-paths that are unit probe interval graphs and characterize them. Using similar ideas we subsequently characterize interior 2caterpillar which are unit probe interval graphs. Finally we use these results to get a complete characterization of 2-trees which are unit probe interval graphs. iv The form and content of this abstract are approved. I recommend its publication. Approved: J. Richard Lundgren