Intersection representations of graphs and digraphs

A digraph is an interval digraph if each vertex can be assigned a source interval and a sink interval on the real line such that there is an edge from u to v if and only if the source interval for u intersects the sink interval for v. A digraph is an indifference digraph or unit interval digraph if and only if such a representation can be constructed in which every source and sink interval has unit length. We prove that an interval digraph is a unit interval digraph if and only if its adjacency matrix is free of six forbidden submatrices: three 3 by 4 matrices and their transposes.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Lin, In-Jen

Contributors dc:contributor

• West, Douglas B.

• Mathematics
• Operations Research
• Computer Science

Statement dc:rights

• Copyright 1994 Lin, In-Jen

Language dc:language

eng

Identifier

AAI9416396
(UMI)AAI9416396

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/19205