Abstract
dc:description.abstractInterval graphs admit elegant ordering and structural characterizations. A natural digraph analogue of interval graphs, called chronological interval digraphs, has recently been identified and studied. We introduce the class of chronological rectangle digraphs, and show that they are a higher dimensional analogue of chronological interval digraphs. A main goal of this thesis is to establish a foundation of knowledge about this class, including basic properties and an ordering characterization. Our most significant result is a forbidden induced subdigraph characterization for the series-parallel digraphs which are chronological rectangle. We also discuss obtaining chronological rectangle digraphs from orientations of graphs. In addition we introduce the related concept of the chronological interval dimension of a digraph, and determine the digraphs for which it is defined. Unit and proper chronological rectangle digraphs, defined analogously to unit and proper interval graphs, are also introduced and studied.
Degree
thesis:*- Level thesis:degree_level
- Doctor of Philosophy Ph.D.
- Department thesis:degree_department
- Department of Mathematics and Statistics
- Year dc:date.issued
- 2015
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Manzer, Joshua Daniel Adrian
- Advisor dc:contributor.supervisor
-
- Huang, Jing
Subjects
dc:subject × 4Rights
dc:rights- Statement dc:rights
-
- Available to the World Wide Web
- Licence dc:rights.uri
- Language dc:language.iso
- en, English
Identifiers
dc:identifier.*- Dc Identifier Citation
- J. Huang, and J. Manzer. Chronological rectangle digraphs. Electronic Notes in Discrete Mathematics, 50 (2015) 157-162.