Back to search

University of Victoria (Canada)

Chronological rectangle digraphs

Abstract

dc:description.abstract

Interval 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 × 4

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web
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.

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Manzer, Joshua Daniel Adrian. Chronological rectangle digraphs. Doctor of Philosophy Ph.D. thesis, 2015. http://hdl.handle.net/1828/6989